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

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