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

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

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

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

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

• ${\displaystyle R\subseteq [R]}$ — экстенсивность;
• ${\displaystyle R_{1}\subseteq R_{2}\Rightarrow [R_{1}]\subseteq [R_{2}]}$ — монотонность;
• ${\displaystyle [[R]]=[R]}$ — идемпотентность.

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

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

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

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

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

• Функция ${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})}$ называется сохраняющей ноль, если ${\displaystyle f(0,0,\ldots ,0)=0}$. Класс таких функций называется ${\displaystyle T_{0}}$.
• Функция ${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})}$ называется сохраняющей единицу, если ${\displaystyle f(1,1,\ldots ,1)=1}$. Класс таких функций называется ${\displaystyle T_{1}}$.
• Функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения, то есть для самодвойственной функции ${\displaystyle f(x_{1},x_{2},\dots ,x_{n})}$ выполняется тождество ${\displaystyle f(x_{1},x_{2},\dots ,x_{n})={\overline {f({\bar {x}}_{1},{\bar {x}}_{2},\dots ,{\bar {x}}_{n})}}}$. Класс таких функций называется ${\displaystyle S}$.
• Функция называется монотонной: ${\displaystyle (\beta _{1},\beta _{2},\ldots ,\beta _{n})\geq (\alpha _{1},\alpha _{2},\ldots ,\alpha _{n})\Rightarrow f(\beta _{1},\beta _{2},\ldots ,\beta _{n})\geq f(\alpha _{1},\alpha _{2},\ldots ,\alpha _{n})}$. Класс таких функций называется ${\displaystyle M}$.
  • ${\displaystyle (\beta _{1},\beta _{2},\ldots ,\beta _{n})\geq (\alpha _{1},\alpha _{2},\ldots ,\alpha _{n})\Leftrightarrow \forall i(\beta _{i}\geq \alpha _{i})}$.
• Функция называется линейной, когда её можно представить полиномом Жегалкина первой степени, то есть ${\displaystyle 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};}$ ${\displaystyle \alpha _{0},\alpha _{i}\in \{0,1\}(i\in {\overline {1,n}})}$. Класс таких функций называется ${\displaystyle L}$.

Отметим, что ни один из замкнутых классов ${\displaystyle S,M,L,T_{0},T_{1}}$ целиком не содержится в объединении остальных четырёх. Это вытекает из следующих соотношений:

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

Всякий нетривиальный (отличный от ${\displaystyle P_{2}}$) замкнутый класс булевых функций целиком содержится хотя бы в одном из классов ${\displaystyle S,M,L,T_{0},T_{1}}$.

Система булевых функций F является полной тогда и только тогда, когда она целиком не принадлежит ни одному из замкнутых классов➤ ${\displaystyle S,M,L,T_{0},T_{1}}$.

То есть когда в ней можно реализовать пять функций: несамодвойственную, немонотонную, нелинейную, не сохраняющую 0 и не сохраняющую 1.

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

Рассмотрим функцию, не принадлежащую классу Т₀. Для неё

${\displaystyle f(0,0,...,0)=1}$.

Эта функция может принадлежать, а может не принадлежать классу Т₁.

• В первом случае ${\displaystyle f(1,1,...,1)=1,}$ тогда ${\displaystyle f(x,x,...,x)=1,}$ и мы имеем константу единицы.
• Во втором случае ${\displaystyle f(1,1,...,1)=0,}$ тогда ${\displaystyle f(x,x,...,x)={\overline {x}},}$ и мы имеем инвертор.

Рассмотрим функцию, не принадлежащую классу Т₁. Для неё

${\displaystyle f(1,1,...,1)=0}$.

Эта функция может принадлежать, а может не принадлежать классу Т₀.

• В первом случае ${\displaystyle f(0,0,...,0)=0,}$ тогда ${\displaystyle f(x,x,...,x)=0,}$ и мы имеем константу нуля.
• Во втором случае ${\displaystyle f(0,0,...,0)=1,}$ тогда ${\displaystyle f(x,x,...,x)={\overline {x}},}$ и мы имеем инвертор.

Рассмотрим функцию, не принадлежащую классу S самодвойственных функций. Для неё найдётся такой набор входных переменных X, что

${\displaystyle f(x_{1},x_{2},...,x_{n})=f({\overline {x}}_{1},{\overline {x}}_{2},...,{\overline {x}}_{n})}$.

Пусть, например, ${\displaystyle f(0,1,0)=f(1,0,1)=1,}$ тогда ${\displaystyle f(x,{\overline {x}},x)=1}$ и мы имеем константу 1.

Аналогично, если, например, ${\displaystyle f(0,0,0,1)=f(1,1,1,0)=0,}$ тогда ${\displaystyle f(x,x,x,{\overline {x}})=0}$ и мы имеем константу 0.

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

Если в одном из вышеперечисленных случаев мы получили инвертор и одну из констант, вторую константу получим с помощью инвертора: ${\displaystyle {\overline {0}}=1}$ или ${\displaystyle {\overline {1}}=0.}$

Для немонотонной функции обязательно найдётся такой набор входных переменных, что

${\displaystyle f(x_{1},x_{2},...,0,...,x_{n})=1}$ и

${\displaystyle f(x_{1},x_{2},...,1,...,x_{n})=0}$.

Пусть, например, ${\displaystyle f(1,1,0)=0}$ и ${\displaystyle f(1,0,0)=1}$. Тогда ${\displaystyle f(1,x,0)={\overline {x}}}$.

В любом случае, имея немонотонную функцию и обе константы, мы можем получить инвертор.

Нелинейная функция по определению имеет в полиноме Жегалкина хотя бы один член, содержащий конъюнкцию нескольких переменных. Пусть переменные ${\displaystyle x_{1},x_{2}}$ содержатся в этой конъюнкции, тогда ${\displaystyle f(x_{1},x_{2},x_{3},...,x_{n})=x_{1}x_{2}A(x_{3},...,x_{n})\oplus x_{1}B(x_{3},...,x_{n})\oplus x_{2}C(x_{3},...,x_{n})\oplus D(x_{3},...,x_{n})}$, где ${\displaystyle A,B,C,D}$ — полиномы Жегалкина.

Так как ${\displaystyle A(x_{3},...,x_{n})}$ — не константа 0, ведь ${\displaystyle x_{1}x_{2}}$ содержатся в полиноме Жегалкина функции ${\displaystyle f}$, то ${\displaystyle A(x_{3},...,x_{n})=1}$ на некотором наборе ${\displaystyle \alpha =(x_{3},...,x_{n}).}$

Тогда ${\displaystyle f(x_{1},x_{2},\alpha )=x_{1}x_{2}A(\alpha )\oplus x_{1}B(\alpha )\oplus x_{2}C(\alpha )\oplus D(\alpha )=x_{1}x_{2}\oplus x_{1}b\oplus x_{2}c\oplus d}$, где ${\displaystyle b,c,d\in \{0,1\}.}$

${\displaystyle f(x_{1}\oplus c,x_{2}\oplus b,\alpha )=x_{1}x_{2}\oplus bc\oplus d}$, то есть в зависимости от значения ${\displaystyle bc\oplus d}$ мы получили ${\displaystyle x_{1}x_{2}}$ или ${\displaystyle {\overline {x_{1}x_{2}}}.}$

Таким образом, имея нелинейную функцию, инвертор и константы 1 и 0 можно получить конъюнкцию.

Имея инвертор и конъюнкцию, всегда можно получить дизъюнкцию:

${\displaystyle x_{1}\lor x_{2}={\overline {{\overline {x}}_{1}{\overline {x}}}}_{2}.}$

Теорема доказана.

Функция ${\displaystyle f}$ в одиночку является полной системой тогда и только тогда, когда:

1. ${\displaystyle f(0,0,...,0)=1}$.
2. ${\displaystyle f(1,1,...,1)=0}$.
3. ${\displaystyle f}$ не является самодвойственной.

Примерами функций, в одиночку являющихся полной системой, будут штрих Шеффера ${\displaystyle x|y={\overline {x\operatorname {\&} y}}}$ и стрелка Пирса ${\displaystyle x\downarrow y={\overline {x\vee y}}}$.

Максимальное число функций в базисе алгебры логики равно 4^[1].

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

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

${\displaystyle f_{0}\not \in T_{0};f_{1}\not \in T_{1};f_{S}\not \in S;f_{M}\not \in M;f_{L}\not \in L}$.

Рассмотрим функцию ${\displaystyle f_{0}}$. Возможны два случая:

• ${\displaystyle f_{0}\in T_{1},}$ тогда: ${\displaystyle f_{0}\not \in S}$ и система ${\displaystyle [f_{0},f_{1},f_{M},f_{L}]}$ полна.
• ${\displaystyle f_{0}\not \in T_{1},}$ тогда: ${\displaystyle f_{0}\not \in M,T_{1}}$ и система ${\displaystyle [f_{0},f_{S},f_{L}]}$ полна.

2) Покажем, что существует базис из четырёх функций. Рассмотрим систему функций ${\displaystyle \{0,1,x\cdot y,x\oplus y\oplus z\}}$. Эта система полна:

${\displaystyle 0\not \in T_{1},S;1\not \in T_{0};x\cdot y\not \in L;x\oplus y\oplus z\not \in M}$.

Однако ни одна его подсистема не полна:

• ${\displaystyle \{0,1,x\cdot y\}\subseteq M}$;
• ${\displaystyle \{0,1,x\oplus y\oplus z\}\subseteq L}$;
• ${\displaystyle \{0,x\cdot y,x\oplus y\oplus z\}\subseteq T_{0}}$;
• ${\displaystyle \{1,x\cdot y,x\oplus y\oplus z\}\subseteq T_{1}}$.

Теорема доказана.

• Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит, 2000.
• Фудзисава Т., Касами Т. Математика для радиоинженеров: теория дискретных структур. — М.: Радио и связь, 1984. — 240 с.
• Алексеев В. Б. Дискретная математика (II семестр). — М., МГУ, 2002. — 44 с.
• Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ, 2006. — 744 с. — ISBN 5-7038-2886-4.
• Гиндикин С. Г. Алгебра логики в задачах. — М.: Наука, 1972. — 288 с.

• Учебник по дискретной математике. Суперпозиция функций. Замыкание набора функции.Замкнутые классы функций. Полные наборы. Базисы, mini-soft.ru

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