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

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