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

В середине 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^{*}}$ .

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

Основные классы функций: T ₀ , T ₁ , S, M, L

• Функция ${\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.

Доказательство

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

Имея функцию, не сохраняющую 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}},}$ и мы имеем инвертор.

Имея функцию, не сохраняющую 1, получим инвертор или константу 0

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

${\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) Докажем, что из любой полной системы функций можно выделить полную подсистему, состоящую не более чем из четырёх функций.

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

${\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 с.
• Алексеев В. Б. . — М., МГУ, 2002. — 44 с.
• Белоусов А. И., Ткачев С. Б. Дискретная математика. — М. : МГТУ, 2006. — 744 с. — ISBN 5-7038-2886-4 .
• Гиндикин С. Г. Алгебра логики в задачах. — М. : Наука, 1972. — 288 с.

Ссылки

• , mini-soft.ru

См. также

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