Полные системы функций (связок)

Система функций является полной, если любая n-арная булева функция может быть записана в виде пропозициональной формулы с использованием только функций входящих в эту систему.

Система {,∨,∧,→,↔} является полной.

Система {,∨,∧} является полной. Именно она и составляет сигнатуру Булевой Алгебры.

Системы {,→}, {|} (штрих шеффера), так же полны.

Вторая система – только И-НЕ является важной для микроэлектроники.

Последняя система позволяет представить булевы функции в виде полиномов (полиномов Жигалкина)

Замкнутый класс – это такое множество функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: [P] = P (то есть, любая функция, которую можно записать с помощью только функций входящих в P так же входит в P).

критерий Поста: Система булевых функций является полной тогда и только тогда, когда он не содержится целиком ни в одном из пяти замкнутых классов:

· монотонные функции

}

· функции, сохраняющие нуль

· функции, сохраняющие единицу

· линейные функции

· самодвойственные функции

Если функции содержатся в одном из классов, то и все композиции также не выходят за пределы этого класса (легко проверить для каждого из классов в отдельности) и поэтому система не является полной.

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