Примеры. - Класс всех функций F — замкнутый

- Класс всех функций F — замкнутый. В силу Предложения 4 любое замыкание [C] является

замкнутым классом.

- M = [{0, 1, ∨, &}] — класс монотонных функций.

- L = [{0, 1, +}] — класс линейных функций, состоящих из многочленов Жегалкина вида a0 + a1x1 + · · · + anxn, где ai ∈ B.

Теорема. Класс T_0, состоящий из всех f ∈ F, для которых f(0,..., 0) = 0, является замкнутым.

Док-во. Пусть f, A1,..., An ∈ T_0 и g = f(A1,..., An). Тогда g(0,..., 0) = f(A1(0,..., 0),..., An(0,..., 0)) = f(0,..., 0) = 0, так что g ∈ T_0. Т.к. A1,..., An ∈ замкнутому классу, то g = f(A1,..., An) тоже замкнут.

Теорема. Класс T1, состоящий из всех f ∈ F, для которых f(1,..., 1) = 1, является замкнутым.

Док-во. Пусть f, A1,..., An ∈ T1 и g = f(A1,..., An). Тогда g(1,..., 1) = f(A1(1,..., 1),..., An(1,..., 1)) = f(1,..., 1) = 1, так что g ∈ T1. Т.к. A1,..., An ∈ замкнутому классу, то g = f(A1,..., An) тоже замкнут.

Теорема. Класс S, состоящий из всех f ∈ F, для которых (-f(x1,..., xn)) = f(-x1,...,- xn),

является замкнутым.

Доказательство. Пусть f, A1,..., Ak ∈ S и g = f(A1,..., An).

Тогда (-g(x1,..., xn)) =[- f(A1(x1,..., xn),..., Ak(x1,..., xn))] =

= f([-A1(x1,..., xn)],...,[- Ak(x1,..., xn))] = f(A1(-x1,..., -xn),..., Ak(-x1,..., -xn)) = g(-x1,..., -xn),

так что g ∈ S. Т.к. A1,..., An ∈ замкнутому классу, то g = f(A1,..., An) тоже замкнут.

7. Полные классы функций. Теорема Поста о полноте (доказательство теоремы слева направо).

Определение. Класс функций C ⊆ F называется полным,

если [C] = F. (если замыкание этого класса равно классу всех булевых функций)

Примеры.

- {∨, &, }, {∨, }, {&, }, {1, +, ·}, {|}, {↓} — полные

классы.

- {0, 1, ∨, &}, {0, 1, +} — неполные классы.

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

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

Доказательство. Пусть система функций B является полной. Допустим, что B

содержится в одном из перечисленных замкнутых классов, который обозначим

через A. Тогда [B] ⊆ [A] = A. В силу полноты системы B, класс A содержит

все булевы функции. Противоречие.