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

Для того чтобы система функций была полной, необходимо и достаточно, чтобы она не содержалась целиком ни в одном из классов 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₂, что неверно.