Критерий Поста

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

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

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

Основная статья: Замкнутые классы булевых функций

Булева функция — это функция типа $\mathsf{B}^n\to\mathsf{B}$, где $\mathsf{B}=\{0,1\}$, а $n$ — арность. Количество различных функций арности $n$ равно $2^{2^n}$, общее же количество различных булевых функций бесконечно. Вместе с тем, очевидно, что многие функции могут быть выражены через другие с использованием оператора суперпозиции. Например, давно известно, что из дизъюнкции и отрицания можно, используя законы де Моргана, получить конъюнкцию. Кроме того, любая булева функция (за исключением тождественной единицы) может быть представлена в виде ДНФ, то есть, в терминах конъюнкции, дизъюнкции и отрицания. Возникает естественный вопрос: как определить, будет ли данный набор функций достаточным, чтобы представить любую булеву функцию? Такие наборы называются функционально полными. Теорема Поста даёт ответ на этот вопрос. Поскольку условие теоремы является необходимыми и достаточным, её называют также критерием.

Идея теоремы состоит в том, чтобы рассматривать множество всех булевых функций $\mathsf{PA}$ как алгебру относительно операции суперпозиции. Сейчас она носит имя алгебра Поста. Эта алгебра содержит в качестве своих подалгебр множества функций, замкнутых относительно суперпозиции. Их называют ещё замкнутыми классами. Пусть $~R$ — некоторое подмножество $\mathsf{PA}$. Замыканием $[R]$ множества $~R$ называется минимальная подалгебра $\mathsf{PA}$, содержащая $~R$. Иными словами, замыкание состоит из всех функций, которые являются суперпозициями $~R$. Очевидно, что $~R$ будет функционально полно тогда и только тогда, когда $[R] = \mathsf{PA}$. Таким образом, вопрос, будет ли данный класс функционально полон, сводится к проверке того, совпадает ли его замыкание с $\mathsf{PA}$.

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

• $R\subseteq[R]$    (экстенсивность)
• $R_1\subseteq R_2 \Rightarrow [R_1]\subseteq [R_2]$    (монотонность)
• $~[[R]]=[R]$    (идемпотентность)

Говорят, что множество функций $~Q$ порождает замкнутый класс $~R$ (или класс $~R$ порождается множеством функций $~Q$), если $~[Q]=R$. Множество функций $~Q$ называется базисом замкнутого класса $~R$, если $~[Q]=R$ и $~[Q_1]\ne R$ для любого подмножества $~Q_1$ множества $~Q$, отличного от $~Q$.

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

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

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

• Если $~R$ — замкнутый класс, то $~R^*$ — также замкнутый класс.
• Множество $~S$ образует замкнутый класс.
• Если $R = [Q]$ , то $~R^* = [~Q^*]$. В частности, если $~Q$ — базис класса $~R$, то $~Q^*$ — базис класса $~R^*$.

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

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

• Функция $f(x_1, x_2, \ldots, x_n)$ называется сохраняющей ноль, если $f(0, 0, \ldots,0) = 0$. Обозначают, что $f \in T_0$.
• Функция $f(x_1, x_2, \ldots, x_n)$ называется сохраняющей единицу, если $f(1, 1, \ldots,1) = 1$. Обозначают, что $f \in T_1$.
• Функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения, то есть для самодвойственной функции $~f(x_1, x_2,\dots,x_n)$ выполняется тождество $f (x_1,x_2,\dots,x_n)=\overline{f(\bar{x}_1,\bar{x}_2,\dots,\bar{x}_n)}$. Обозначают, что $f \in S$.
• Функция называется монотонной: $(\beta_1, \beta_2, \ldots, \beta_n) \ge (\alpha_1, \alpha_2, \ldots, \alpha_n) \Rightarrow f(\beta_1, \beta_2, \ldots, \beta_n) \ge f(\alpha_1, \alpha_2, \ldots, \alpha_n)$. Обозначают, что $f \in M$.
  • $(\beta_1, \beta_2, \ldots, \beta_n) \ge (\alpha_1, \alpha_2, \ldots, \alpha_n) \Leftrightarrow \forall i (\beta_i \ge \alpha_i)$
• Функция называется линейной, когда её можно представить полиномом первой степени, то есть $f(x_1, x_2, \ldots, x_n) = \alpha_0 \oplus \alpha_1 x_{1} \oplus \alpha_2 x_{2} \oplus \ldots \oplus \alpha_n x_{n} ;$ $\alpha_0, \alpha_i \in {0,1} (i \in \overline{1,n})$. Обозначают, что $f \in L$.

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

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

1. $\{\bar{x},xy \oplus xz \oplus yz\}\subset S\setminus(M\cup L\cup T_0\cup T_1)$
2. $\{0,1,x\lor y\}\subset M\setminus(S\cup L\cup T_0\cup T_1)$
3. $\{1,x \oplus y\}\subset L\setminus(S\cup M\cup T_0\cup T_1)$
4. $\{x \oplus y,xy\}\subset T_0\setminus(S\cup M\cup L\cup T_1)$
5. $\{x \oplus y \oplus 1,x\lor y\}\subset T_1\setminus(S\cup M\cup L\cup T_0)$

Всякий нетривиальный (отличный от $~P_2$) замкнутый класс булевых функций целиком содержится хотя бы в одном из классов $~S,M,L,T_0,T_1$.

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

Система булевых функций F является полной тогда и только тогда, когда она целиком не принадлежит ни одному из замкнутых классов $~S,M,L,T_0,T_1$.

См. также

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

Литература

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