Система функций является полной, если любая n-арная булева функция может быть записана в виде пропозициональной формулы с использованием только функций входящих в эту систему.
Система {¬,∨,∧,→,↔} является полной.
Система {¬,∨,∧} является полной. Именно она и составляет сигнатуру Булевой Алгебры.
Системы {¬,→}, {|} (штрих шеффера), так же полны.
Вторая система – только И-НЕ является важной для микроэлектроники.
Последняя система позволяет представить булевы функции в виде полиномов (полиномов Жигалкина)
Замкнутый класс – это такое множество функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: [P] = P (то есть, любая функция, которую можно записать с помощью только функций входящих в P так же входит в P).
критерий Поста: Система булевых функций является полной тогда и только тогда, когда он не содержится целиком ни в одном из пяти замкнутых классов:
· монотонные функции
}
· функции, сохраняющие нуль
· функции, сохраняющие единицу
· линейные функции
· самодвойственные функции
Если функции содержатся в одном из классов, то и все композиции также не выходят за пределы этого класса (легко проверить для каждого из классов в отдельности) и поэтому система не является полной.
Можно показать, что имея функции по крайней мере из 2 разных классов, можно выразить любую другую функцию.