Критерий полноты { формулировка } . Лемма о нелинейной функции

Формулировка. Система булевых функций $F$ является полной тогда и только тогда, когда она целиком не принадлежит ни одному из замкнутых классов $~S,M,L,T_0,T_1$.

1. монотонные функции { функция монотонно не убывает по каждому из своих аргументов } ;
2. функции, сохраняющие нуль { функция от нуля даёт ноль } ;
3. функции, сохраняющие единицу { функция от единицы даёт единицу } ;
4. линейные функции { функция представима многочленом, в котором каждый член состоит из одной переменной } ;
5. самодвойственные функции { функция двойственна сама себе } .

Лемма: Суперпозицией нелинейной функции, отрицания и константы $1$ можно получить конъюнкцию.

Доказательство: Пусть $f(x_1, x_2 , ..., x_n)$ — нелинейная функция, тогда полином Жигалкина для нее содержит слагаемое, в котором присутствует произведение каких-то переменных $x_i*x_j$. Пусть для простоты это будет произведение $x_1x_2$. Произведя группировку слагаемых в полиноме Жегалкина для $f$ относительно $x_1x_2, x_1, x_2$, функцию $f$ представим в виде $f(x_1,..., x_n)=x_1*x_2*h_0(x_3,...,x_n)+$ { собрали все слагаемые с $x_1*x_2$ и вынесли $x_1*x_2$ за скобки. В скобках осталась сумма $h_0(x_3,...,x_n)$, в которой переменных $x_1, x_2$ нет } $+ x_1h_1(x_3,..., x_n) + x_2h_2(x_3,..., x_n) + h_3(x_3,..., x_n)$

Функция $h_0(x_3,..., x_n) \neq 0$, в противном случае многочлен Жигалкина слагаемых с произведением $x_1x_2$ не имеет, тогда существует набор $(a_3,..., a_n)$ из $0$ и $1$, для которого $h_0(a_3,..., a_n) = 1$. Пусть на этом наборе $h_1(a_3,..., a_n)=a; h_2(a_3,..., a_n)=b; h_3(a_3,..., a_n)=c$. Тогда функция $g(x_1,x_2)= f(x_1,x_2,a_3,..., a_n)=x_1*x_2+a*x_1+b*x_2+c$. Построим функцию $h(x_1,x_2) = g(x_1+bx_2+a) =(x_1+b)$ $(x_2+a)+a(x_1+b)+b(x_2+a)+c = x_1*x_2+a*x_1+b*x_2+a*b+a*x_1+a*b+b*x_2+a*b+c$ $=_1*x_2+a*b+c=x_1*x_2+d, d=a*b+c$ Если $d=0$, то $h(x_1,x_2)=x_1*x_2$, конъюнкция получена. Если $d=1$, то $h(x_1,x_2)=x_1*x_2+1 \Rightarrow x_1*x_2=\bar { h } (x_1,x_2)$, что и требовалось доказать.