Линейные функции

Определение:

Пусть $f(x_1,...,x_n)\in P_2$.

Функция $f$ — линейная, если ее полином Жегалкина имеет вид

[math]\displaystyle{ 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$ — класс всех линейных функций.

Пример

$x$ — линейная функция. Функция $x\vee y$ не является линейной.

Теорема:

Класс функций $L$ замкнут.

Доказательство:

Рассмотрим суперпозицию ранга 1 от функций из $L$.

a) Пусть $f(x_1,...,x_n)\in L$ и [math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ (\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$.

[math]\displaystyle{ \blacksquare }[/math]

Замечание

Тождественная функция $f(x)=x$ лежит в классе $L$.

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

Таким образом, $L\neq \varnothing$ и $L\neq P_2$.

Лемма (О нелинейной функции):

Пусть $f(x_1,...,x_n)\notin L$.

Тогда, подставляя в $f$ вместо аргументов константы, $x$, $y$, $\overline x$, $\overline y$

и, возможно, навешивая отрицание над $f$ можно получить $x\wedge y$.

Доказательство:

Пусть $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\}$: $

[math]\displaystyle{ \blacksquare }[/math]

{{Пример |content= Построение $x\wedge y$ с помощью нелинейной функции

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

[math]\displaystyle{ 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]\displaystyle{ \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]\displaystyle{ 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]\displaystyle{ \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]\displaystyle{ \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].

Рис. 1. Слева — что разрешено в линейной функции: только константа и отдельные переменные. Справа — как из нелинейной [math]\displaystyle{ f=1\oplus x\oplus xy\oplus xz }[/math] подстановкой [math]\displaystyle{ z=0 }[/math] и отрицанием получается [math]\displaystyle{ \varphi(x,y)=x\wedge y }[/math].

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