Лемма о немонотонной функции

Лемма 4. Если , то из неё путем подстановки констант 0 и 1 и функции можно получить функцию .

Доказательство: Пусть , тогда найдутся 2 набора , такие, что при .

Так как , то .

Пусть наборы и различаются в первых разрядах, где , то есть

Рассмотрим функцию .

так как при .

, это значит, .

Лемма доказана.

3.20. Теорема о полноте в Р₂

Теорема 7. Система функций из полна она целиком не содержится ни в одном из пяти замкнутых классов .

Доказательство: Необходимость . Пусть полна, то есть . Допустим, что , где один из 5 перечисленных классов. Тогда в силу свойств замыкания и замкнутости имеем , противоречие.

Достаточность . Пусть не содержится целиком ни в одном из пяти указанных классов, значит в функции . Итак, из системы выделим подсистему , которая также целиком не содержится ни в одном из пяти указанных классов. Будем считать, что все эти функции зависят от одних и тех же переменных .

I. Построение констант 0 и 1 при помощи функций .

Рассмотрим . Возможны два случая:

а) .

Пусть .

Возьмем ; – вторая константа.

б) .

Пусть .

Рассмотрим . Так как мы имеем , то по лемме 3 мы можем получить константу . Используя константу и можем получить другую константу .

II. Построение функции при помощи констант 0 и 1 и . Это следует из леммы 4.

III. Построение при помощи констант . Это осуществляется на основе лемм 1 и 2.

Таким образом, при помощи формул над (а значит и над ) реализовали функции . .

Теорема доказана полностью.

Из доказательства теоремы 7 следует

Следствие 8. Всякий замкнутый класс функций из такой, что , содержится по крайней мере в одном из классов .