Теорема о достаточности четырех функций

Из любой полной в Р ₂ системы функций можно выделить полную подсистему, состоящую не более чем из четырех функций.

Доказательство. Пусть – полная система функций, тогда она не лежит целиком ни в одном из классов T ₀, T ₁, L, M, S. Следовательно, в системе есть функции f ₀Ï T ₀, f ₁Ï T ₁, f_L Ï L, f_S Ï S и f_m Ï M. Система { f ₀, f ₁, f_L, f_M, f_S } Í P ₂ и образует полную систему в Р ₂. Рассмотрим функцию f ₀: f ₀(0,..., 0) = 1.

Если f ₀(1,..., 1) = 0, то f ₀Ï T ₁ и f ₀Ï M, тогда { f ₀, f_S, f _L} – полная система из трех функций.

Если f ₀(1,..., 1) = 1, то f ₀Ï S и { f ₀, f ₁, f_L, f_M } образует полную систему из четырех функций.

Пример 19, приведенный выше, показывает, что цифру 4 в общем случае уменьшить нельзя, из полной системы { x ₁ x ₂,0,1, x ₁Å x ₂Å x ₃} нельзя выделить полную подсистему.

Следствие. Базис в Р ₂ может состоять максимум из четырех функций.