Суперпозиция и замкнутые классы функций[править | править исходный текст]

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

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

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

Разумеется, множество всех возможных булевых функций тоже является замкнутым.