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

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

1. монотонные функции { функция монотонно не убывает по каждому из своих аргументов } ;

2. функции, сохраняющие нуль { функция от нуля даёт ноль } ;

3. функции, сохраняющие единицу { функция от единицы даёт единицу } ;

4. линейные функции { функция представима многочленом, в котором каждый член состоит из одной переменной } ;

5. самодвойственные функции { функция двойственна сама себе } .

Лемма: { о немонотонной функции } : Суперпозицией констант 0 и 1 и немонотонной функции можно получить отрицание.

Доказательство: Пусть $f(x\_1, x\_2 , ..., x\_n)$ немонотонная функция. Тогда $\exists$ набор $(a\_1, a\_2, ...,a\_n), b = (b\_1, b\_2, ...,b\_n)$ для которых $a \leq b$, но $f(a) > f(b)$. Пусть $i\_1, i\_2, ...,i\_k$ есть все те номера аргументов, для которых $a\_ { ip } < b\_ { ip } , p=1,2, ...,k$. На остальных аргументных местах $j$ имеем $a\_j = b\_j$. В выражении $f(a\_1, a\_2, ...,a\_n)$ заменим нули на местах $i\_1, i\_2, ...,i\_k$ на $x$. В результате получим функцию $g(x)$, для которой $g(0) = f(a) = 1$ и $g(1) = f(b) =0$, то есть для $g(x)$ является отрицанием.

Лемма: функция монотонна $\Longleftrightarrow$ ее сокращенная ДНФ не содержит отрицания.

Следствие: Функция $f$ монотонна $\Longleftrightarrow$ минимальная ДНФ не содержит отрицаний переменных.