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

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

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

Лемма { о несамодвойственной функции } : Подстановкой функций $x$ и $\bar { x } $ в несомодвойственную функцию можно получить одну из констант.

Доказательство: пусть $f(x_1, x_2 , ..., x_n)$ – несамодвойственна. Тогда $\exists$ набор $(a_1, a_2,…,a_n)$ из $0$ и $1$ для которого $f(a_1, a_2,…,a_n) = f(\bar { a } _1,\bar { a } _2,…,\bar { a } _n)$. Построим функцию $h(x)$, заменив единицы в $f(a_1, a_2,…,a_n)$ на $x$, а нули на $\bar { x } $. Т.к. $\bar { x } = x_0 , x =x_1$ то $h(x) = f(x^ { a_1 } , x^ { a_2 } ,…,x^ { a_n } )$. Заметим, что $0^ { a_i } =\bar { a } _i, 1^ { a_i } = a_i$. Тогда $h(1)= f(1^ { a_1 } , 1^ { a_2 } ,…,1^ { a_n } ) = f(a_1, a_2,…,a_n) = f(\bar { a } _1, \bar { a } _2,…,\bar { a } _n) = f(0^ { a_1 } , 0^ { a_2 } , ... , 0^ { a_n } ) = h(0) \Longrightarrow (0) =h(1) \Longrightarrow h(x) =const$