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

Формулировка. Система булевых функций $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\_1*h\_1(x\_3,..., x\_n) + x\_2*h\_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)$, что и требовалось доказать.