=== Полнота системы, критерий Поста ===
Система булевых {{main|Теорема Поста о полной системе функций называется ''полной'', если можно построить их суперпозицию, тождественную любой другой заранее заданной функции. Говорят ещё, что замыкание данной системы совпадает с множеством <math>P_2</math>.}}
Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:
* Функции, сохраняющие константу <math>T_0</math> и <math>T_1</math>;
* Самодвойственные функции <math>S</math>;
* Монотонные функции <math>M</math>;
* Линейные функции <math>L</math>.
Им было доказано, что любой замкнутый класс булевых функций, не совпадающий с <math>P_2</math>, целиком содержится в одном из этих пяти так называемых ''предполных классов'', но при этом ни один из пяти не содержится целиком в объединении четырёх других. Таким образом критерий Поста для полноты системы сводится к выяснению, не содержится ли вся эта система целиком в одном из предполных классов. Если для каждого класса в системе найдётся функция, не входящая в него, то такая система будет полной, и с помощью входящих в неё функций можно будет получить любую другую булеву функцию.
Заметим, что существуют функции, не входящие ни в один из классов Поста. Любая такая функция сама по себе образует полную систему. В качестве примеров можно назвать штрих Шеффера или стрелку Пирса.
== Представление булевых функций ==
Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций <math>\Sigma = \{f_1,\ldots,f_n\}</math>. Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре <math>\Sigma</math>, который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:
