Полнота системы, критерий Поста[править | править исходный текст]

Основная статья: Критерий Поста

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

Американский математик Эмиль Постввёл в рассмотрение следующие замкнутые классы булевых функций:

• Функции, сохраняющие константу и ;

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

• Монотонные функции ;

• Линейные функции .

Им было доказано, что любой замкнутый класс булевых функций, не совпадающий с , целиком содержится в одном из этих пяти так называемыхпредполных классов, но при этом ни один из пяти не содержится целиком в объединении четырёх других. Таким образом, критерий Поста для полноты системы сводится к выяснению, не содержится ли вся эта система целиком в одном из предполных классов. Если для каждого класса в системе найдётся функция, не входящая в него, то такая система будет полной, и с помощью входящих в неё функций можно будет получить любую другую булеву функцию. Пост доказал, что множество замкнутых классов булевых функций —счётное множество.

Заметим, что существуют функции, не входящие ни в один из классов Поста. Любая такая функция сама по себе образует полную систему. В качестве примеров можно назвать штрих Шеффераилистрелку Пирса.