Определение.Система функций {f1, f2,…, fn} называется полной, если любая булева функция может быть выражена через функции f1, f2,…, fn с помощью композиции (т. е. составления сложных функций).
Теорема 3.2. Следующие системы булевых функций полны:
{Ø, Ù, Ú}; {Ø, Ú}; {Ø, Ù}; {Ø, É}; {+, Ù, 1}; {É,Ø};{¯}; {|}.
Доказательство. То, что система функций {Ø, Ù, Ú} является полной, доказано в теореме 3.1. Конъюнкцию можно выразить через операции Ø и Ú, а дизъюнкцию можно выразить через операции Ø и Ù, поэтому полными системами являются {Ø, Ú} и {Ø, Ù}. Полнота системы {+, Ù,1} следует из следующих тождеств: ØX = X+1, XÚY = XÙY + X +Y. Для доказательства полноты системы {É,Ø} воспользуемся равенством fÉg = Øf Ú g. Отсюда получаем f Ú g = Øf Ég, fÙg = Øf Ú Øg = fÉØg. Полнота системы {¯} доказана в §1 данной главы. Полноту системы, состоящей из одного штриха Шеффера, предлагаем доказать читателю.
Рассмотрим систему {+, Ù,1}. Будем вместо Ù писать знак умножения ‰, или вообще опускать, т. е. вместо XÙY писать XY.
Таблица 10
| X | Y | X+Y | XY |
С помощью табл. 10 можно доказать тождества:
1) X+Y = Y + X, XY = YX;
2) (X + Y) +Z = X + (Y + Z), (XY)Z = X(YZ);
3) X + X = 0, XX = X;
4) X(Y + Z) = XY + XZ;
5) 0 + X = X;
6) 0X = 0;
7) 1X = X.
Все правила, за исключением 3, выражают свойства, аналогичные обычным свойствам арифметики сложения и умножения.
Поскольку система {+, Ù, 1} полная, то любую переключательную функцию можно представить в виде многочлена с единичными коэффициентами и с переменными, входящими только в первой степени. Такие многочлены называются многочленами Жегалкина.