Доказательство окончено

Рассмотрим применение доказанной леммы к нелинейным функциям.

Пусть f = x ₁ ® (x ₂ ® x ₃). Тогда полином Жегалкина для f имеет вид

f = x ₁ x ₂ x ₃ + x ₁ x ₂ + 1, т.е. x ₁ x ₂ (x ₃ + 1) + 1.

Полином равен единице при x ₃ = 0. Тогда f (x ₁, x ₂, 0) = x ₁ x ₂ + 1. Поэтому x ₁& x ₂.

Упражнение.

1. Доказать утверждение, обратное утверждению леммы о нелинейной функции.

2. Показать, что всякий из определенных выше классов булевских функций является замкнутым и неполным.

КРИТЕРИЙ ФУНКЦИОНАЛЬНОЙ ПОЛНОТЫ

ТЕОРЕМА 4.9

Класс B Í P ₂ является полной системой тогда и только тогда, когда он целиком не содержится ни в одном из классов Т ₀, Т ₁, S, L, M.