Критерий Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом.

В середине 60-х годов почти одновременно в СССР и во Франции появились работы, где с иных позиций и в более доступной форме излагались результаты Поста. В 80-е годы сразу целому ряду исследователей с использованием различных подходов и различной техники удалось получить достаточно компактные доказательства результатов Поста. Алгебраический подход в изучении замкнутых классов булевых функций (подалгебр итеративной алгебры Поста над множеством ) принадлежит А. И. Мальцеву.

Алгебра Поста и замкнутые классы

Булева функция — это функция типа , где , а — арность. Количество различных функций арности равно , общее же количество различных булевых функций бесконечно. Вместе с тем, очевидно, что многие функции могут быть выражены через другие с использованием оператора суперпозиции. Например, давно известно, что из дизъюнкции и отрицания можно, используя законы де Моргана, получить конъюнкцию. Кроме того, любая булева функция (за исключением тождественной единицы) может быть представлена в виде ДНФ, то есть, в терминах конъюнкции, дизъюнкции и отрицания. Возникает естественный вопрос: как определить, будет ли данный набор функций достаточным, чтобы представить любую булеву функцию? Такие наборы называются функционально полными. Теорема Поста даёт ответ на этот вопрос. Поскольку условие теоремы является необходимыми и достаточным, её называют также критерием.

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

Оператор является оператором замыкания. Иными словами, он обладает (среди прочих) свойствами:

•     (экстенсивность)
•     (монотонность)
•     (идемпотентность)

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

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

Двойственность, монотонность, линейность. Критерий полноты

Ниже приведены некоторые следствия, вытекающие из теорем о двойственных функциях.

• Если — замкнутый класс, то — также замкнутый класс.
• Множество образует замкнутый класс.
• Если , то . В частности, если — базис класса , то — базис класса .

Перейдем теперь к выяснению полноты конкретных наборов функций.

Основные классы функций

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

Теорема о замкнутости основных классов функций

Отметим, что ни один из замкнутых классов целиком не содержится в объединении остальных четырёх. Это вытекает из следующих соотношений:

Формулировка критерия

См. также

• Булева функция
• Законы де Моргана
• Алгебра логики
• Стрелка Пирса
• Дискретная математика

Литература

• С. С. Марченков, «Замкнутые классы булевых функций»
• Образовательный сайт MiniSoft