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

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

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

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

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

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

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

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

• $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{P}\mathsf{A}$, не совпадающей с $\mathsf{P}\mathsf{A}$ прибавить один элемент, ей не принадлежащий, и образовать замыкание, результатом будет новая подалгебра, содержащая данную. При этом, она совпадёт с $\mathsf{P}\mathsf{A}$, в том и только в том случае, если между исходной подалгеброй, и $\mathsf{P}\mathsf{A}$ нет никаких других подалгебр, то есть, если исходная подалгебра была максимальной. Таким образом, для того, чтобы проверить, что данное множество функций $R$ функционально полно, достаточно убедиться, что оно не входит целиком ни в одну из максимальных подалгебр $\mathsf{P}\mathsf{A}$. Оказывается, что таких подалгебр всего пять, и вопрос принадлежности к ним может быть решён просто и эффективно.

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

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

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

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

Основные классы функций: $S,M,L,T_0,T_1$

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

• Функция $f(x_1,x_2,\dots ,x_n)$ называется сохраняющей ноль, если $f(0,0,\dots ,0)=0$. Класс таких функций называется $T_0$.
• Функция $f(x_1,x_2,\dots ,x_n)$ называется сохраняющей единицу, если $f(1,1,\dots ,1)=1$. Класс таких функций называется $T_1$.
• Функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения, то есть для самодвойственной функции $f(x_1,x_2,\dots ,x_n)$ выполняется тождество $f(x_1,x_2,\dots ,x_n)=\overline{f({\overline{x}}_1,{\overline{x}}_2,\dots ,{\overline{x}}_n)}$. Класс таких функций называется $S$.
• Функция называется монотонной: $({\beta }_1,{\beta }_2,\dots ,{\beta }_n)\ge ({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n)\Rightarrow f({\beta }_1,{\beta }_2,\dots ,{\beta }_n)\ge f({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n)$. Класс таких функций называется $M$.
  • $({\beta }_1,{\beta }_2,\dots ,{\beta }_n)\ge ({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n)\iff \mathrm{\forall }i({\beta }_i\ge {\alpha }_i)$
• Функция называется линейной, когда её можно представить полиномом Жегалкина первой степени, то есть $f(x_1,x_2,\dots ,x_n)={\alpha }_0\oplus {\alpha }_1{x}_1\oplus {\alpha }_2{x}_2\oplus \dots \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. $\{\overline{x},xy\oplus xz\oplus yz\}\subset S\setminus (M\cup L\cup T_0\cup T_1)$
2. $\{0,1,x\vee 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\vee 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)=\bar{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)=\bar{x},$ и мы имеем инвертор.

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

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

$f(x_1,x_2,...,x_n)=f({\bar{x}}_1,{\bar{x}}_2,...,{\bar{x}}_n).$

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

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

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

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

Если в одном из вышеперечисленных случаев мы получили инвертор и одну из констант, вторую константу получим с помощью инвертора: $\bar{0}=1$ или $\bar{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)=\bar{x}$.

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

Имеем инвертор и обе константы

В предыдущих подразделах мы перебрали все возможные варианты (см. рисунок) и пришли к выводу, что имея функции, не принадлежащие классам Т₀, Т₁, S и M, мы всегда можем различными способами получить инвертор и обе константы.

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

Нелинейная функция по определению имеет в полиноме Жегалкина хотя бы один член, содержащий конъюнкцию нескольких переменных. Пусть, например, имеется некоторая нелинейная функция

$f(x_1,x_2,x_3,x_4,x_5)=1\oplus x_1\oplus x_1{x}_2{x}_3\oplus x_2{x}_3{x}_4\oplus x_2{x}_3{x}_5\oplus x_2{x}_3{x}_4{x}_5.$

Зададимся целью построить на её основе конъюнкцию $c(x_1,x_2)=x_1{x}_2.$

Присвоим переменным $x_3,x_4,x_5$ значения 1, получим:

$f(x_1,x_2,1,1,1)=1\oplus x_1\oplus x_1{x}_2\oplus x_2\oplus x_2\oplus x_2=1\oplus x_1\oplus x_1{x}_2\oplus x_2.$

Очевидно, что в общем случае после такого преобразования получится функция вида

$f(x_1,x_2,1,1,...,1)=x_1{x}_2[\oplus x_1][\oplus x_2][\oplus 1],$

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

В простейшем случае при отсутствии других членов сразу получаем конъюнкцию: :$f(x_1,x_2,1,1,...,1)=x_1{x}_2.$

Рассмотрим другие варианты.

• $x_1{x}_2\oplus x_1=x_1{\bar{x}}_2;$
• $x_1{x}_2\oplus x_2={\bar{x}}_1{x}_2;$
• $x_1{x}_2\oplus x_1\oplus x_2={\overline{{\stackrel{‾}{x}}_1\stackrel{‾}{x}}}_2.$
• $x_1{x}_2\oplus 1={\overline{x_{1}x}}_2;$.
• $x_1{x}_2\oplus x_1\oplus 1={\overline{x_1\stackrel{‾}{x}}}_2;$
• $x_1{x}_2\oplus x_2\oplus 1={\overline{{\stackrel{‾}{x}}_{1}x}}_2;$
• $x_1{x}_2\oplus x_1\oplus x_2\oplus 1={\bar{x}}_1{\bar{x}}_2.$

Любое из этих выражений, используя инвертор, можно привести к конъюнкции.

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

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

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

$x_1+x_2={\overline{{\stackrel{‾}{x}}_1\stackrel{‾}{x}}}_2.$

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

Следствие

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

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

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

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

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

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

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

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

$f_0\in ̸T_0;f_1\in ̸T_1;f_S\in ̸S;f_M\in ̸M;f_L\in ̸L.$

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

• $f_0\in T_1,$ тогда : $f_0\in ̸S$ и система $[f_0,f_1,f_M,f_L]$ полна.
• $f_0\in ̸T_1,$ тогда : $f_0\in ̸M,T_1$ и система $[f_0,f_S,f_L]$ полна.

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

$0\in ̸T_1,S;1\in ̸T_0;x\cdot y\in ̸L;x\oplus y\oplus z\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

См. также

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