ЯсноПонятно24

Для того чтобы система булевых функций {f,g} была полной, необходимо, чтобы с ее помощью можно было выразить любую булеву функцию.

Функция f задана вектором значений: f = 01110001. Это значит, что f(x,y,z) = x⊕y⊕¬z⊕1.

Функция g задана формулой: g = zy(x⇒¬y¬z) = zy(¬x∨¬y∨z) = zy¬(x∧y∧¬z).

Теперь попробуем выразить с помощью функций f и g функцию AND (логическое умножение): x∧y = f(x,y,0) = x⊕y⊕1, x∧¬y = f(x,¬y,0) = x⊕¬y⊕1, ¬(x∧y) = f(x,y,1) = x⊕y.

Таким образом, мы можем выразить функцию AND с помощью функций f и g. Это означает, что система {f,g} является полной по теореме Поста.