Полные системы булевых функций

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

Таким образом, в соответствии с определением система функций {∧, ∨, ’} полна. Поскольку дизъюнкцию можно выразить через конъюнкцию и отрицание, система функций {∧, ’} также полна. Точно так же полной является и система функций {∨, ’}, поскольку конъюнкцию можно выразить через дизъюнкцию и отрицание. Отрицание можно выразить через ноль и импликацию, дизъюнкцию – через импликацию и отрицание (см. п. 2.2). Следовательно, отрицание и импликация, ноль и импликация также образуют полные системы функций {’, →}, {0, →}.

Через ⊕ и 1 можно выразить отрицание, так что система функций {1, ⊕, ⋅} также является полной. Последнее означает, что любая булева функция может быть представлена в виде многочлена. При этом ненулевыми коэффициентами при одночленах служат единицы, а одночлены не содержат степеней переменных, поскольку умножение (конъюнкция) идемпотентна. Такие многочлены называют полиномами Жегалкина.

Пример.Вычислим полином Жегалкина для функции

f(x,y,z)=(x→y)∨(z→y)

Имеем:

(x→y)∨(z→y) = (x’∨y)∨(z’∨y) = (xy’)’∨(zy’)’ = (1⊕xy’)∨(1⊕zy’) = (1⊕xy’)⊕(1⊕zy’) ⊕(1⊕xy’) (1⊕zy’) =

= 1⊕xy’⊕1⊕zy’⊕1⊕xy’⊕zy’⊕xy’zy’ =

= (1⊕1) ⊕(xy’⊕xy’) ⊕(zy’⊕zy’) ⊕1⊕xy’z=

= 0⊕0⊕0⊕1⊕xy’z = 1⊕xy’z= 1⊕x(1⊕y)z=1⊕xz⊕xyz.

При выводе использовались равенства x’=1⊕x, x⊕x=0, x∨y=x⊕y⊕xy и др. (см. п. 3.2).􀀀

Существуют полные системы, содержащие всего одну функцию. Отрицание и конъюнкцию можно выразить через стрелку Пирса (см. п. 3.2). Следовательно, стрелка Пирса составляет полную систему функций {↓}. Точно так же отрицание и дизъюнкция выражаются через штрих Шеффера, так что {|} – тоже полная система функций.

Мы видим, что установить полноту системы функций можно, показав, как через функции этой системы выражаются функции какой-нибудь системы, полнота которой уже известна. Доказательство неполноты может оказаться более изощренным.

Пример.Покажем что система функций {⋅,∨} неполна. Действительно, отрицание нельзя выразить через дизъюнкцию и конъюнкцию. Допустим противное, то есть, что отрицание удалось представить в виде x’=f(x,y,…,z), и при этом функция f выражена через конъюнкции и дизъюнкции. Тогда

1=0’=f(0,y,…,z) и 0=1’=f(1,y,…,z).

Но конъюнкция и дизъюнкция монотонны по своим аргументам: если α₁≤α₂ и β₁≤β₂ то α₁∧β₁≤α₂∧β₂ и α₁∨β₁≤α₂∨β₂.

Тем же свойством обладает и любая сложная функция, составленная из конъюнкции и дизъюнкции. Значит,

f(0,y,…,z) ≤ f(1,y,…,z),

что противоречит предполагаемому равенству.􀀀