СВ в 10:54, 25 октября 2026

2026-10-25T10:54:19Z

← Предыдущая		Версия 10:54, 25 октября 2026
Строка 217:		Строка 217:

	[[Файл:p44-01-linear-to-conjunction.svg\|frame\|none\|900px\|alt=Допустимые и запрещённые мономы линейной функции и цепочка получения x ∧ y из нелинейной f\|Рис. 1. Слева — что разрешено в линейной функции: только константа и отдельные переменные. Справа — как из нелинейной <math>f=1\oplus x\oplus xy\oplus xz</math> подстановкой <math>z=0</math> и отрицанием получается <math>\varphi(x,y)=x\wedge y</math>.]]		[[Файл:p44-01-linear-to-conjunction.svg\|frame\|none\|900px\|alt=Допустимые и запрещённые мономы линейной функции и цепочка получения x ∧ y из нелинейной f\|Рис. 1. Слева — что разрешено в линейной функции: только константа и отдельные переменные. Справа — как из нелинейной <math>f=1\oplus x\oplus xy\oplus xz</math> подстановкой <math>z=0</math> и отрицанием получается <math>\varphi(x,y)=x\wedge y</math>.]]

			Конспект: [[Дискретная математика]]

СВ: Новая страница: «{{Определение |definition= Пусть $f(x_1,...,x_n)\in P_2$. Функция $f$ {{---}} линейная, если ее полином Жегалки...»

2026-10-25T10:54:03Z

Новая страница: «{{Определение |definition= Пусть $f(x_1,...,x_n)\in P_2$. Функция $f$ {{---}} линейная, если ее полином Жегалки...»

Новая страница

{{Определение
|definition=
Пусть $f(x_1,...,x_n)\in P_2$.
Функция $f$ {{---}} линейная, если ее полином Жегалкина имеет вид
<math>
f(x_1,...,x_n) = \alpha_0\oplus \alpha_1 x_1\oplus \alpha_2 x_2 \oplus ...\oplus \alpha_n x_n.
</math>
}}

Обозначим $L$ {{---}} класс всех линейных функций.

{{Пример
|content=
$x$ {{---}} линейная функция.

Функция $x\vee y$ не является линейной.
}}
{{Теорема
|statement=Класс функций $L$ замкнут.
|proof=
Рассмотрим суперпозицию ранга 1 от функций из $L$.

a) Пусть $f(x_1,...,x_n)\in L$ и
<math>
g(x_1,...,x_{j-1},x_{j+1},...,x_n, y) = f(x_1,...,x_{j-1},y,x_{j+1},...,x_{n}).
</math>
Если
<math>
f(x_1,...,x_n) = \alpha_0\oplus \alpha_1 x_1\oplus \alpha_2 x_2 \oplus ...\oplus \alpha_n x_n,
</math>
то
<math>
g(x_1,...,x_{j-1},x_{j+1},...,x_n, y) = \alpha_0\oplus \alpha_1 x_1\oplus ...\oplus \alpha_{j-1} x_{j-1}\oplus \alpha_j y \oplus \alpha_{j+1} x_{j+1} \oplus ...\oplus \alpha_n x_n.
</math>

Следовательно
$g(x_1,...,x_{j-1},x_{j+1},...,x_n, y)\in L$.

b) Пусть $f(x_1,...,x_n)\in L$ и $h(y_1, ...,y_m)\in L$ и
<math>
g(x_1,...,x_{j-1},x_{j+1},...,x_n, y_1,...,y_m) = f(x_1,...,x_{j-1},h(y_1,...,y_{m}),x_{j+1},...,x_{n}).
</math>
Пусть
<math>
f(x_1,...,x_n) = \alpha_0\oplus \alpha_1 x_1\oplus \alpha_2 x_2 \oplus ...\oplus \alpha_n x_n
</math>
и
<math>
h(y_1,...,y_m) = \beta_0\oplus \beta_1 y_1\oplus \beta_2 y_2 \oplus ...\oplus \beta_m y_m.
</math>
Тогда
<math>
g(x_1,...,x_{j-1},x_{j+1},...,x_n, y_1,...,y_m) = \alpha_0\oplus \alpha_1 x_1\oplus ...\oplus \alpha_{j-1} x_{j-1}\oplus
\alpha_j (\beta_0\oplus \beta_1 y_1 \oplus ...\oplus \beta_m y_m) \oplus \alpha_{j+1} x_{j+1} \oplus ...\oplus \alpha_n x_n =</math>
<math>(\alpha_0\oplus \alpha_j \beta_0) \oplus
\alpha_1 x_1\oplus ...\oplus
\alpha_{j-1} x_{j-1}\oplus
\alpha_{j+1} x_{j+1} \oplus ...\oplus \alpha_n x_n
\oplus \alpha_j \beta_1 y_1
\oplus ...\oplus \alpha_j \beta_m y_m.
</math>
Если некоторая переменная $x_i$ совпадает с переменной $y_j$, сложим коэффициенты по модулю 2.
Полученный полином Жегалкина линеен.
Следовательно, $g(x_1,...,x_{j-1},x_{j+1},...,x_n, y_1,...,y_m)\in L$.
Таким образом, $[L] = L$.
}}
{{Замечание
|content=
Тождественная функция $f(x)=x$ лежит в классе $L$.

Дизъюнкция $f(x,y) = x \vee y$ не лежит в $L$.

Таким образом, $L\neq \varnothing$ и $L\neq P_2$.
}}
{{Лемма
|about=О нелинейной функции
|statement=
Пусть $f(x_1,...,x_n)\notin L$.
Тогда, подставляя в $f$ вместо аргументов константы, $x$, $y$, $\overline x$, $\overline y$
и, возможно, навешивая отрицание над $f$ можно получить $x\wedge y$.
|proof=
Пусть $f(x_1,...,x_n) = \bigoplus_{I\subseteq \{1,...,n\} } \alpha(I)\bigwedge_{i\in I} x_i$
и $f\notin L$.
Тогда существует $I^*\subseteq \{1,...,n\}$: $|I^*|\geq 2$, $\alpha(I^*)\neq 0$.

Не умаляя общности, положим $\{1,2\}\subseteq I^*$.
<math>
f(x_1,...,x_n) = x_1 x_2 f_{1,2} (x_3,...,x_n) \oplus x_1 f_{1}(x_3,...,x_n) \oplus x_2 f_2 (x_3,...,x_n) \oplus f_0(x_3,...,x_n),
</math>
причем $\exists \alpha_3,...,\alpha_n$: $f_{1,2}(\alpha_3,...,\alpha_n)=1$.

Действительно, такие $\alpha_3,...,\alpha_n$ существуют, поскольку,
если бы $f_{1,2}(\sigma_3,...,\sigma_n)=0$, $\forall \sigma_3,...,\sigma_n\in\{0,1\}$,
то функция $f$ приняла бы вид
<math>
f(x_1,...,x_n) = x_1 f_{1}(x_3,...,x_n)
\oplus x_2 f_2 (x_3,...,x_n)
\oplus f_0(x_3,...,x_n),
</math>
что противоречит нашему предположению, что $\{1,2\}\subseteq I^*$ и $\alpha(I^*)=1$.

Рассмотрим
<math>
\psi(x,y) = f(x,y,\alpha_3,...,\alpha_n) = x y \oplus x f_1 (\alpha_3,...,\alpha_n) \oplus y f_2(\alpha_3,...,\alpha_n) \oplus f_0(\alpha_3,...,\alpha_n) = x y \oplus x \beta \oplus y \gamma \oplus \delta.
</math>

Теперь определим $\varphi(x,y)$, как
$
\varphi(x,y) = \psi(x\oplus \gamma, y\oplus \beta) \oplus \gamma\beta\oplus \delta.
$

Тогда
<math>
\varphi(x,y) = ((x\oplus \gamma)(y\oplus \beta) \oplus (x\oplus \gamma) \beta \oplus (y\oplus \beta) \gamma \oplus \delta) \oplus \gamma\beta\oplus \delta =
x y \oplus x \beta \oplus y \gamma \oplus \gamma \beta \oplus x \beta \oplus\gamma \beta
\oplus y\gamma \oplus \gamma\beta \oplus \delta \oplus \gamma\beta\oplus \delta = x y.
</math>

Таким образом, мы получили функцию $\varphi(x,y) = x\wedge y$, причем
<math>
\varphi(x,y) = f(x\oplus f_2(\alpha_3,...,\alpha_n),y\oplus f_1 (\alpha_3,...,\alpha_n),\alpha_3,...,\alpha_n) \oplus f_1(\alpha_3,...,\alpha_n) f_2 (\alpha_3,...,\alpha_n)\oplus f_0(\alpha_3,...,\alpha_n),
</math>
где добавление к $x$ и $y$ констант $f_2(\alpha_3,...,\alpha_n)$ и $f_1 (\alpha_3,...,\alpha_n)$
равносильно навешиванию отрицания над переменной, если соответствующая константа равна 1, а
добавление константы
$f_1(\alpha_3,...,\alpha_n) f_2 (\alpha_3,...,\alpha_n)\oplus f_0(\alpha_3,...,\alpha_n)$
к $f$ означает возможное навешивание отрицания над этой функцией.
}}
{{Пример
|content=
'''Построение $x\wedge y$ с помощью нелинейной функции'''

Пусть $f(x,y,z) = x\supset (y\oplus z)$.
Построим полином Жегалкина этой функции методом неопределенных коэффициентов.

<math>
f(x,y,z) =
\alpha_0 \oplus \alpha_1 x \oplus \alpha_2 y \oplus \alpha_3 z \oplus \alpha_{1,2} xy
\oplus \alpha_{1,3} x z \oplus \alpha_{2,3} y z \oplus \alpha_{1,2,3} x y z.
</math>

<math>
\begin{array}{ccc|cl}
x & y & z & f(x,y,z)\\
\hline
\begin{array}{c}
0\\
0\\
0\\
0\\
1\\
1\\
1\\
1\\
\end{array}
&
\begin{array}{c}
0\\
0\\
1\\
1\\
0\\
0\\
1\\
1\\
\end{array}
&
\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1\\
\end{array}
&
\begin{array}{c}
1\\
1\\
1\\
1\\
0\\
1\\
1\\
0\\
\end{array}
&
\begin{array}{l}
\alpha_0 = 1\\
\alpha_3 = 0\\
\alpha_2 = 0\\
\alpha_{2,3} = 0\\
\alpha_1 = 1\\
\alpha_{1,3}=1\\
\alpha_{1,2}=1\\
\alpha_{1,2,3} = 0\\
\end{array}
\end{array}
</math>

Таким образом
$f(x,y,z) = 1 \oplus x \oplus x y \oplus x z$ и функция $f$ нелинейна.

Построим функцию $\varphi(x,y)=x\wedge y$. В нашем случае коэффициент при $xy$ не равен нулю; выделим в полиноме Жегалкина переменные $x$ и $y$.
<math>f(x,y,z) = 1 \oplus x \oplus x y \oplus x z = x y\cdot 1 \oplus x\cdot(1\oplus z) \oplus 1</math>
Тогда можно положить $z = 0$ и получим, что $\beta = 1$, $\gamma = 0$, $\delta = 1$
и <math>\varphi(x,y) = f(x\oplus \gamma, y\oplus \beta, 0)\oplus \gamma\beta\oplus \delta = \neg f(x, \overline y, 0)</math>.

Проверим, что $\varphi$ соответствует конъюнкции:
<math>
\varphi(x,y) = \overline {(x\supset (\overline y\oplus 0))}=
\overline{x\supset\overline y} = \overline{\overline x\vee\overline y}
= x\wedge y
</math>.

[[Файл:p44-01-linear-to-conjunction.svg|frame|none|900px|alt=Допустимые и запрещённые мономы линейной функции и цепочка получения x ∧ y из нелинейной f|Рис. 1. Слева — что разрешено в линейной функции: только константа и отдельные переменные. Справа — как из нелинейной <math>f=1\oplus x\oplus xy\oplus xz</math> подстановкой <math>z=0</math> и отрицанием получается <math>\varphi(x,y)=x\wedge y</math>.]]

Линейные функции - История изменений

СВ в 10:54, 25 октября 2026

СВ: Новая страница: «{{Определение |definition= Пусть $f(x_1,...,x_n)\in P_2$. Функция $f$ {{---}} линейная, если ее полином Жегалки...»