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

Определение. Система функций {f₁, f₂,…, f_n} называется полной, если любая булева функция может быть выражена через функции f₁, f₂,…, f_n с помощью композиции (т. е. составления сложных функций).

Теорема 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} полная, то любую переключательную функцию можно представить в виде многочлена с единичными коэффициентами и с переменными, входящими только в первой степени. Такие многочлены называются многочленами Жегалкина.