Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

45 достаточно, чтобы она не содержалась целиком ни в одном из пяти замкнутых классов T 0 ,T 1 ,S,M и L . Доказательство. Необходимость. Пусть F – полна, т.е. [F]=P 2 . Предположим, что F содержится в одном из замкнутых классов, который обозначим через F  , т.е. F  F  . Но тогда P 2 =[F]  [F]  =F  – противоречие. Достаточность. Пусть F не содержится ни в одном из пяти замкнутых классов. Тогда из F можно выделить подсистему, содержащую 5 функций f i , f j , f k , f m , f l , которые не содержатся соответственно в классах T 0 ,T 1 ,S,M , L . Пусть эта подсистема будет F  ={f i ,f j ,f k ,f l , f m }. Можно считать, что все эти функции зависят от одинакового числа переменных. 1. Построим при помощи функций f i , f j и f k константы 0 и 1 . Рассмотрим f i  T 0 . Если f i (1,…,1)=1 , то  (x)=f i (x,…,x) есть константа 1, т.к.  (0)=f i (0,…,0)=1 , в силу того, что f i  T 0 и  (1)=f i (1,…,1)=1 . Константу 0 получаем из f j : f j (1,…,1)=0 . Если f i (1,…,1)=0 , то  (x)=f i (x,…,x) есть x , т.к.  (0)=f i (0,…,0)=1 ,  (1)=f i (1,…,1)=0 . Возьмем f k (f k  S) . Из леммы о несамодвойственной функции мы можем получить константу 0 или 1, а т.к. у нас есть функция x , то мы можем получить и вторую константу. 2. Имея константу 0 и 1 и функцию f m (f m  M), мы по лемме о немонотонности функции можем получить функцию x . 3. Имея константы 0 и 1, функцию x и функцию f l (f l  L) мы по лемме о нелинейной функции можем получить функцию x&y . Таким образом, мы при помощи формул над F  (а значит и над F ) получили функции x и x 1 &x 2 , что доказывает достаточность. Ч.т.д.