Булева функция |
4 |
Полные системы булевых функций
Суперпозиция и замкнутые классы функций
Результат вычисления булевой функции может быть использован в качестве одного из аргументов другой функции. Результат такой операции суперпозиции можно рассматривать как новую булеву функцию со своей таблицей истинности. Например, функции 
(суперпозиция конъюнкции, дизъюнкции и двух отрицаний) будет соответствовать следующая таблица:
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
Говорят, что множество функций замкнуто относительно операции суперпозиции, если любая суперпозиция функций из данного множества тоже входит в это же множество. Замкнутые множества функций называют также замкнутыми классами.
В качестве простейших примеров замкнутых классов булевых функций можно назвать множество 
, состоящее из одной тождественной функции, или множество 
, все функции из которого тождественно равны нулю вне зависимости от своих аргументов. Замкнуты также множество функций 
и множество всех унарных функций. А вот объединение замкнутых классов может таковым уже не являться. Например, объединив классы 
и 
, мы с помощью суперпозиции 
сможем получить константу 1, которая в
исходных классах отсутствовала.
Разумеется, множество 
всех возможных булевых функций тоже является замкнутым.
Тождественность и двойственность
Две булевы функции тождественны друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. Тождественность функций f и g можно записать, например, так:
Просмотрев таблицы истинности булевых функций, легко получить такие тождества:
А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:
(законы де Моргана)
(дистрибутивность конъюнкции и дизъюнкции)