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

Формулировка. Система булевых функций $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)$, что и требовалось доказать.