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

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

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

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

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

Основная статья: Предполные классы

• Функция $f(x_{1},x_{2},\ldots ,x_{n})$ называется сохраняющей ноль, если $f(0,0,\ldots ,0)=0$. Класс таких функций называется $T_{0}$.
• Функция $f(x_{1},x_{2},\ldots ,x_{n})$ называется сохраняющей единицу, если $f(1,1,\ldots ,1)=1$. Класс таких функций называется $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})}}$. Класс таких функций называется $S$.
• Функция называется монотонной: $(\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})$. Класс таких функций называется $M$.
  • $(\beta _{1},\beta _{2},\ldots ,\beta _{n})\geq (\alpha _{1},\alpha _{2},\ldots ,\alpha _{n})\Leftrightarrow \forall i(\beta _{i}\geq \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}})$. Класс таких функций называется $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}$.

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

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

Порядок перебора вариантов при доказательстве критерия Поста

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

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

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

$f(0,0,...,0)=1$.

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

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

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

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

$f(1,1,...,1)=0$.

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

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

Имея инвертор и несамодвойственную функцию, получим одну из констант

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

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

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

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

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

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

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

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

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

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

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

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

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

Имея нелинейную функцию, инвертор и обе константы, получим конъюнкцию

Нелинейная функция по определению имеет в полиноме Жегалкина хотя бы один член, содержащий конъюнкцию нескольких переменных. Пусть переменные $x_{1},x_{2}$ содержатся в этой конъюнкции, тогда $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})$, где $A,B,C,D$ — полиномы Жегалкина.

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

Тогда $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$, где $b,c,d\in \{0,1\}.$

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

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

Имея конъюнкцию и инвертор, получим дизъюнкцию

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

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

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

Следствие

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

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

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

Теорема о максимальном числе функций в базисе

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

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

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

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

$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$.

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

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

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

$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$.

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

• $\{0,1,x\cdot y\}\subseteq M$;
• $\{0,1,x\oplus y\oplus z\}\subseteq L$;
• $\{0,x\cdot y,x\oplus y\oplus z\}\subseteq T_{0}$;
• $\{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

См. также

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