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

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

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

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

Возникает вопрос о построении других полных систем булевых функций.

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

Согласно свойству 19° (гл. 1,6) имзем

т. е. дизъюнкция может быть построена с помощью конъюнкции и отрицания. Следовательно, конъюнкция и отрицание составляют полную систему функций. Аналогично получаем, что полную систему составляют дизъюнкция и отрицание.

Полная система может состоять всего из одной функции, например, операции Шеффера. Это следует из того, что через операцию Шеффера можно выразить конъюнкцию, дизъюнкцию и отрицание

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