Лемма о функциях, не сохраняющих T_0 и T_1. Теорема Поста о полноте (доказательство теоремы справа налево)

Лемма. Если f T0 и g T1, то либо ∈ [{f, g}], либо 0, 1 ∈ [{f, g}].

Доказательство. Имеем f(0,..., 0) = 1 и g(1,..., 1) = 0. Если f(1,..., 1) = 0, то f(x,..., x) = x и лемма доказана. Пусть теперь f(1,..., 1) = 1. Тогда f(x,..., x) = 1 и, следовательно, 1 ∈ [{f, g}].

Остается показать, что 0 ∈ [{f, g}]:

Следствие. Если f T0, g T1, p S и q M, то либо, 0, 1 ∈ [{f, g, p}], либо, 0, 1 ∈ [{f, g, q}].

Теорема (критерий Поста). Теорема. Класс функций C ⊆ F является полным тогда и

только тогда, когда C не содержится в классах T0, T1, M, L,S.

Док-во. Обратно, пусть B содержится в одном из пяти вышеперечисленных классов.

Выделим в B систему функций fT0, fT1, f S, f M, f L, не принадлежащих классам

T0, T1, S, M и L соответственно. Не ограничивая общности можно считать, что каждая из этих функций зависит от фиксированного числа переменных x1,..., xn.Покажем, что при помощи функций fT0, fT1 и fS можно получить константы 0 и 1. Если fT0(1,...,1) = 1, то функция ϕ(x) = fT0(x,..., x) тождественно равна 1, поскольку ϕ(0) = 1 = ϕ(1). Константа 0 получается из fT1, поскольку

fT1(1,...,1) = 0. Если же fT0(1,...,1) = 0, то ϕ(x) = fT0(x,..., x) =!x, поскольку ϕ(0) = fT0(0,...,0) = 1 и ϕ(1) = fT(1,...,1) = 0. По лемме 10 при помощи x и fS можно получить константу. Вторая константа получается применением x. при помощи констант 0, 1 и функции fM можно получить!x. Наконец, по лемме 12 при помощи констант 0, 1 и функций!x и fL можно получить x1 & x2. Теперь полнота системы B следует из полноты конъюнкции и отрицания. Неполный класс функций A назовем предполным, если класс A ∪ {f} будет

полным для любой функции f 6∈ A.