Теорема Поста о полноте

Для того чтобы система функций была полной, необходимо и достаточно, чтобы она не содержалась целиком ни в одном из классов T ₀, T ₁, L, S, M.

Доказательство. Докажем необходимость этого условия. Пусть система

N = { f ₁, f ₂,... f_s,...} полна в Р ₂, покажем, что тогда она не лежит целиком в Q, где через Q обозначим любой из классов T ₀, T ₁, L, S, M. Докажем от противного, пусть N Í Q, очевидно, [ N ] Í [ Q ] = Q, но [ N ] = P ₂, т.к. N – полна в Р ₂, отсюда Р ₂= Q, но это не так. Необходимость доказана.

Докажем достаточность. Пусть F = { f ₀, f ₁, f_L, f_m, f_s }, где f ₀Ï T ₀, f ₁Ï T ₁, f_L Ï L, f_s Ï S и f_m Ï M. Покажем, что суперпозицией функций системы F можно получить полную систему G = { x ₁& x ₂, }.

1. Пусть g (x) = f ₀(x, …, x). Тогда g (0) = f (0, …, 0) = 1. Далее возможны два случая:

g (1) = 1. Тогда g (x) º 1. Функция h (x) = f ₁(g (x), …, g (x)) = f ₁(1, …, 1) = 0, т.е. h (x) º 0. Получили константы 0 и 1;

g(1) = 0. Тогда g (x) = . По лемме о несамодвойственной функции суперпозицией над { f_s, } можно получить одну из констант, например, 0. Тогда f ₀(0, …, 0) = 1 есть другая константа.

В обоих случаях получили обе константы.

2. По лемме о немонотонной функции суперпозицией над { f_m, 0, 1} можно получить отрицание.

3. По лемме о нелинейной функции суперпозицией над { f_L, 1, } можно получить конъюнкцию. Теорема доказана.

Следствие. Всякий замкнутый класс функций из Р ₂, не совпадающий с Р ₂ содержится, по крайней мере, в одном из замкнутых классов T ₀, T ₁, L, S, M. Действительно, если N не является подмножеством Q, то [ N ] = P ₂, что неверно.