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

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

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

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

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

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

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

[math]\displaystyle{ R\subseteq[R] }[/math] (экстенсивность)
[math]\displaystyle{ R_1\subseteq R_2 \Rightarrow [R_1]\subseteq [R_2] }[/math] (монотонность)
[math]\displaystyle{ [[R]]=[R] }[/math] (идемпотентность)

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

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

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

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

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

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

Основные классы функций: [math]\displaystyle{ S,M,L,T_0,T_1 }[/math]

Функция [math]\displaystyle{ f(x_1, x_2, \ldots, x_n) }[/math] называется сохраняющей ноль, если [math]\displaystyle{ f(0, 0, \ldots,0) = 0 }[/math]. Класс таких функций называется [math]\displaystyle{ T_0 }[/math].
Функция [math]\displaystyle{ f(x_1, x_2, \ldots, x_n) }[/math] называется сохраняющей единицу, если [math]\displaystyle{ f(1, 1, \ldots,1) = 1 }[/math]. Класс таких функций называется [math]\displaystyle{ T_1 }[/math].
Функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения, то есть для самодвойственной функции [math]\displaystyle{ f(x_1, x_2,\dots,x_n) }[/math] выполняется тождество [math]\displaystyle{ f (x_1,x_2,\dots,x_n)=\overline{f(\bar{x}_1,\bar{x}_2,\dots,\bar{x}_n)} }[/math]. Класс таких функций называется [math]\displaystyle{ S }[/math].
Функция называется монотонной: [math]\displaystyle{ (\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) }[/math]. Класс таких функций называется [math]\displaystyle{ M }[/math].
- [math]\displaystyle{ (\beta_1, \beta_2, \ldots, \beta_n) \ge (\alpha_1, \alpha_2, \ldots, \alpha_n) \Leftrightarrow \forall i (\beta_i \ge \alpha_i) }[/math]
Функция называется линейной, когда её можно представить полиномом Жегалкина первой степени, то есть [math]\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} ; }[/math] [math]\displaystyle{ \alpha_0, \alpha_i \in {0,1} (i \in \overline{1,n}) }[/math]. Класс таких функций называется [math]\displaystyle{ L }[/math].

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

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

[math]\displaystyle{ \{\bar{x},xy \oplus xz \oplus yz\}\subset S\setminus(M\cup L\cup T_0\cup T_1) }[/math]
[math]\displaystyle{ \{0,1,x\lor y\}\subset M\setminus(S\cup L\cup T_0\cup T_1) }[/math]
[math]\displaystyle{ \{1,x \oplus y\}\subset L\setminus(S\cup M\cup T_0\cup T_1) }[/math]
[math]\displaystyle{ \{x \oplus y,xy\}\subset T_0\setminus(S\cup M\cup L\cup T_1) }[/math]
[math]\displaystyle{ \{x \oplus y \oplus 1,x\lor y\}\subset T_1\setminus(S\cup M\cup L\cup T_0) }[/math]

Всякий нетривиальный (отличный от [math]\displaystyle{ P_2 }[/math]) замкнутый класс булевых функций целиком содержится хотя бы в одном из классов [math]\displaystyle{ S,M,L,T_0,T_1 }[/math].

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

Система булевых функций F является полной тогда и только тогда, когда она целиком не принадлежит ни одному из замкнутых классов^[⇦] [math]\displaystyle{ S,M,L,T_0,T_1 }[/math].

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

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

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

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

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

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

[math]\displaystyle{ f(0,0, ..., 0)=1. }[/math]

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

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

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

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

[math]\displaystyle{ f(1,1, ..., 1)=0. }[/math]

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

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

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

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

[math]\displaystyle{ f(x_1,x_2, ..., x_n)=f(\overline{x}_1,\overline{x}_2, ..., \overline{x}_n). }[/math]

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

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

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

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

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

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

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

[math]\displaystyle{ f(x_1,x_2, ..., 0, ..., x_n)=1 }[/math] и

[math]\displaystyle{ f(x_1,x_2, ..., 1, ..., x_n)=0. }[/math]

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

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

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

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

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

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

[math]\displaystyle{ f(x_1,x_2,x_3,x_4,x_5)=1 \oplus x_1 \oplus x_1x_2x_3 \oplus x_2x_3x_4 \oplus x_2x_3x_5 \oplus x_2x_3x_4x_5. }[/math]

Зададимся целью построить на её основе конъюнкцию [math]\displaystyle{ c (x_1,x_2) = x_1x_2. }[/math]

Присвоим переменным [math]\displaystyle{ x_3, x_4, x_5 }[/math] значения 1, получим:

[math]\displaystyle{ f(x_1,x_2,1,1,1)=1 \oplus x_1 \oplus x_1x_2 \oplus x_2 \oplus x_2 \oplus x_2 = 1 \oplus x_1 \oplus x_1x_2 \oplus x_2. }[/math]

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

[math]\displaystyle{ f(x_1,x_2,1,1,...,1)= x_1x_2 [ \oplus x_1 ] [ \oplus x_2 ] [ \oplus 1 ], }[/math]

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

В простейшем случае при отсутствии других членов сразу получаем конъюнкцию: :[math]\displaystyle{ f(x_1,x_2,1,1,...,1)= x_1x_2. }[/math]

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

[math]\displaystyle{ x_1x_2 \oplus x_1 = x_1 \overline{x}_2; }[/math]
[math]\displaystyle{ x_1x_2 \oplus x_2 = \overline{x}_1 x_2; }[/math]
[math]\displaystyle{ x_1x_2 \oplus x_1 \oplus x_2 = \overline{\overline{x}_1 \overline{x}}_2. }[/math]
[math]\displaystyle{ x_1x_2 \oplus 1 = \overline{x_1x}_2; }[/math].
[math]\displaystyle{ x_1x_2 \oplus x_1 \oplus 1 = \overline{x_1 \overline{x}}_2; }[/math]
[math]\displaystyle{ x_1x_2 \oplus x_2 \oplus 1 = \overline{\overline{x}_1 x}_2; }[/math]
[math]\displaystyle{ x_1x_2 \oplus x_1 \oplus x_2 \oplus 1 = \overline{x}_1 \overline{x}_2. }[/math]

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

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

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

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

[math]\displaystyle{ x_1+ x_2 = \overline{\overline{x}_1 \overline{x}}_2. }[/math]

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

Следствие

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

[math]\displaystyle{ f(0, 0, ..., 0)=1 }[/math]
[math]\displaystyle{ f(1, 1, ..., 1)=0 }[/math]
[math]\displaystyle{ f }[/math] не является самодвойственной

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

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

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

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

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

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

[math]\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. }[/math]

Рассмотрим функцию [math]\displaystyle{ f_0 }[/math]. Возможны два случая:

[math]\displaystyle{ f_0 \in T_1, }[/math] тогда : [math]\displaystyle{ f_0 \not\in S }[/math] и система [math]\displaystyle{ [f_0,f_1,f_M,f_L] }[/math] полна.
[math]\displaystyle{ f_0 \not\in T_1, }[/math] тогда : [math]\displaystyle{ f_0 \not\in M, T_1 }[/math] и система [math]\displaystyle{ [f_0,f_S,f_L] }[/math] полна.

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

[math]\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. }[/math]

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

[math]\displaystyle{ \{ 0,1,x \cdot y \} \subseteq M; }[/math]
[math]\displaystyle{ \{ 0,1,x \oplus y \oplus z \} \subseteq L; }[/math]
[math]\displaystyle{ \{ 0,x \cdot y, x \oplus y \oplus z \} \subseteq T_0; }[/math]
[math]\displaystyle{ \{ 1,x \cdot y, x \oplus y \oplus z \} \subseteq T_1. }[/math]

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

Примечания

↑ Алексеев В.Б. (2002), с. 12.

Литература

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

Ссылки

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

См. также

[alexeev_12-1] Алексеев В.Б. (2002), с. 12.

[1]