Русская Википедия:Критерий Поста
Шаблон:Другие значения Критерий Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом.
В середине 60-х годов почти одновременно в СССР и во Франции появились работы, где с иных позиций и в более доступной форме излагались результаты Поста. В 80-е годы сразу целому ряду исследователей с использованием различных подходов и различной техники удалось получить достаточно компактные доказательства результатов Поста. Алгебраический подход в изучении замкнутых классов булевых функций (подалгебр итеративной алгебры Поста над множеством <math>\mathsf{B}=\{0,1\}</math>) принадлежит А. И. Мальцеву.
Алгебра Поста и замкнутые классы
Булева функция — это функция типа <math>\mathsf{B}^n\to\mathsf{B}</math>, где <math>\mathsf{B}=\{0,1\}</math>, а <math>n</math> — арность. Количество различных функций арности <math>n</math> равно <math>2^{2^n}</math>, общее же количество различных булевых функций бесконечно. Вместе с тем, очевидно, что многие функции могут быть выражены через другие с использованием оператора суперпозиции. Например, давно известно, что из дизъюнкции и отрицания можно, используя законы де Моргана, получить конъюнкцию. Кроме того, любая булева функция может быть представлена в виде ДНФ, то есть, в терминах конъюнкции, дизъюнкции и отрицания. Возникает естественный вопрос: как определить, будет ли данный набор функций достаточным, чтобы представить любую булеву функцию? Такие наборы называются функционально полными. Теорема Поста даёт ответ на этот вопрос. Поскольку условие теоремы является необходимыми и достаточным, её называют также критерием.
Идея теоремы состоит в том, чтобы рассматривать множество всех булевых функций <math>\mathsf{PA}</math> как алгебру относительно операции суперпозиции. Сейчас она носит имя алгебра Поста. Эта алгебра содержит в качестве своих подалгебр множества функций, замкнутых относительно суперпозиции. Их называют ещё замкнутыми классами. Пусть <math>R</math> — некоторое подмножество <math>\mathsf{PA}</math>. Замыканием <math>[R]</math> множества <math>R</math> называется минимальная подалгебра <math>\mathsf{PA}</math>, содержащая <math>R</math>. Иными словами, замыкание состоит из всех функций, которые являются суперпозициями <math>R</math>. Очевидно, что <math>R</math> будет функционально полно тогда и только тогда, когда <math>[R] = \mathsf{PA}</math>. Таким образом, вопрос, будет ли данный класс функционально полон, сводится к проверке того, совпадает ли его замыкание с <math>\mathsf{PA}</math>.
Оператор <math>[\_]</math> является оператором замыкания. Иными словами, он обладает (среди прочих) свойствами:
- <math>R\subseteq[R]</math> (экстенсивность)
- <math>R_1\subseteq R_2 \Rightarrow [R_1]\subseteq [R_2]</math> (монотонность)
- <math>R=[R]</math> (идемпотентность)
Говорят, что множество функций <math>Q</math> порождает замкнутый класс <math>R</math> (или класс <math>R</math> порождается множеством функций <math>Q</math>), если <math>[Q]=R</math>. Множество функций <math>Q</math> называется базисом замкнутого класса <math>R</math>, если <math>[Q]=R</math> и <math>[Q_1]\ne R</math> для любого подмножества <math>Q_1</math> множества <math>Q</math>, отличного от <math>Q</math>.
Если к подалгебре <math>\mathsf{PA}</math>, не совпадающей с <math>\mathsf{PA}</math> прибавить один элемент, ей не принадлежащий, и образовать замыкание, результатом будет новая подалгебра, содержащая данную. При этом, она совпадёт с <math>\mathsf{PA}</math>, в том и только в том случае, если между исходной подалгеброй, и <math>\mathsf{PA}</math> нет никаких других подалгебр, то есть, если исходная подалгебра была максимальной. Таким образом, для того, чтобы проверить, что данное множество функций <math>R</math> функционально полно, достаточно убедиться, что оно не входит целиком ни в одну из максимальных подалгебр <math>\mathsf{PA}</math>. Оказывается, что таких подалгебр всего пять, и вопрос принадлежности к ним может быть решён просто и эффективно.
Двойственность, монотонность, линейность. Критерий полноты
Ниже приведены некоторые следствия, вытекающие из теорем о двойственных функциях.
- Если <math>R</math> — замкнутый класс, то <math>R^*</math> — также замкнутый класс.
- Множество <math>S</math> образует замкнутый класс.
- Если <math>R = [Q]</math> , то <math>R^* = [~Q^*]</math>. В частности, если <math>Q</math> — базис класса <math>R</math>, то <math>Q^*</math> — базис класса <math>R^*</math>.
Перейдем теперь к выяснению полноты конкретных наборов функций.
Основные классы функций: <math>S,M,L,T_0,T_1</math>
- Функция <math>f(x_1, x_2, \ldots, x_n)</math> называется сохраняющей ноль, если <math>f(0, 0, \ldots,0) = 0</math>. Класс таких функций называется <math>T_0</math>.
- Функция <math>f(x_1, x_2, \ldots, x_n)</math> называется сохраняющей единицу, если <math>f(1, 1, \ldots,1) = 1</math>. Класс таких функций называется <math>T_1</math>.
- Функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения, то есть для самодвойственной функции <math>f(x_1, x_2,\dots,x_n)</math> выполняется тождество <math>f (x_1,x_2,\dots,x_n)=\overline{f(\bar{x}_1,\bar{x}_2,\dots,\bar{x}_n)}</math>. Класс таких функций называется <math>S</math>.
- Функция называется монотонной: <math>(\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>M</math>.
- <math>(\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>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>\alpha_0, \alpha_i \in {0,1} (i \in \overline{1,n})</math>. Класс таких функций называется <math>L</math>.
Теорема о замкнутости основных классов функций
Отметим, что ни один из замкнутых классов <math>S,M,L,T_0,T_1</math> целиком не содержится в объединении остальных четырёх. Это вытекает из следующих соотношений:
- <math>\{\bar{x},xy \oplus xz \oplus yz\}\subset S\setminus(M\cup L\cup T_0\cup T_1)</math>
- <math>\{0,1,x\lor y\}\subset M\setminus(S\cup L\cup T_0\cup T_1)</math>
- <math>\{1,x \oplus y\}\subset L\setminus(S\cup M\cup T_0\cup T_1)</math>
- <math>\{x \oplus y,xy\}\subset T_0\setminus(S\cup M\cup L\cup T_1)</math>
- <math>\{x \oplus y \oplus 1,x\lor y\}\subset T_1\setminus(S\cup M\cup L\cup T_0)</math>
Формулировка критерия
Шаблон:Теорема То есть когда в ней можно реализовать пять функций: несамодвойственную, немонотонную, нелинейную, не сохраняющую 0 и не сохраняющую 1.
Доказательство
Доказательство критерия Поста основано на том, что система функций (И, ИЛИ и НЕ) является полной. Таким образом, любая система, в которой реализуемы эти три функции, также является полной. Докажем, что в системе, удовлетворяющей критерию Поста, всегда можно реализовать конъюнкцию, дизъюнкцию и отрицание.
Имея функцию, не сохраняющую 0, получим инвертор или константу 1
Рассмотрим функцию, не принадлежащую классу Т0. Для неё
- <math>f(0,0, ..., 0)=1.</math>
Эта функция может принадлежать, а может не принадлежать классу Т1.
- В первом случае <math>f(1,1, ..., 1)=1,</math> тогда <math>f(x,x, ..., x)=1,</math> и мы имеем константу единицы.
- Во втором случае <math>f(1,1, ..., 1)=0,</math> тогда <math>f(x,x, ..., x)= \overline{x},</math> и мы имеем инвертор.
Имея функцию, не сохраняющую 1, получим инвертор или константу 0
Рассмотрим функцию, не принадлежащую классу Т1. Для неё
- <math>f(1,1, ..., 1)=0.</math>
Эта функция может принадлежать, а может не принадлежать классу Т0.
- В первом случае <math>f(0,0, ..., 0)=0,</math> тогда <math>f(x,x, ..., x)=0,</math> и мы имеем константу нуля.
- Во втором случае <math>f(0,0, ..., 0)=1,</math> тогда <math>f(x,x, ..., x)= \overline{x},</math> и мы имеем инвертор.
Имея инвертор и несамодвойственную функцию, получим одну из констант
Рассмотрим функцию, не принадлежащую классу S самодвойственных функций. Для неё найдётся такой набор входных переменных X, что
- <math>f(x_1,x_2, ..., x_n)=f(\overline{x}_1,\overline{x}_2, ..., \overline{x}_n).</math>
Пусть, например, <math>f(0,1,0)=f(1,0,1)=1,</math> тогда <math>f(x,\overline{x},x)=1</math> и мы имеем константу 1.
Аналогично, если, например, <math>f(0,0,0,1)=f(1,1,1,0)=0,</math> тогда <math>f(x,x,x,\overline{x})=0</math> и мы имеем константу 0.
В любом случае, имея инвертор и несамодвойственную функцию мы можем получить одну из констант.
Имея инвертор и одну из констант, получим другую константу
Если в одном из вышеперечисленных случаев мы получили инвертор и одну из констант, вторую константу получим с помощью инвертора: <math>\overline{0} = 1</math> или <math>\overline{1} = 0.</math>
Имея немонотонную функцию и обе константы, получим инвертор
Для немонотонной функции обязательно найдётся такой набор входных переменных, что
- <math>f(x_1,x_2, ..., 0, ..., x_n)=1</math> и
- <math>f(x_1,x_2, ..., 1, ..., x_n)=0.</math>
Пусть, например, <math>f(1,1,0)=0</math> и <math>f(1,0,0)=1</math>. Тогда <math>f(1,x,0)=\overline{x}</math>.
В любом случае, имея немонотонную функцию и обе константы, мы можем получить инвертор.
Имеем инвертор и обе константы
В предыдущих подразделах мы перебрали все возможные варианты (см. рисунок) и пришли к выводу, что имея функции, не принадлежащие классам Т0, Т1, S и M, мы всегда можем различными способами получить инвертор и обе константы.
Имея нелинейную функцию, инвертор и константу 1, получим конъюнкцию
Нелинейная функция по определению имеет в полиноме Жегалкина хотя бы один член, содержащий конъюнкцию нескольких переменных. Пусть, например, имеется некоторая нелинейная функция
- <math>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>c (x_1,x_2) = x_1x_2.</math>
Присвоим переменным <math>x_3, x_4, x_5</math> значения 1, получим:
- <math>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>f(x_1,x_2,1,1,...,1)= x_1x_2 [ \oplus x_1 ] [ \oplus x_2 ] [ \oplus 1 ],</math>
где квадратные скобки означают, что выделенный ими член может присутствовать в окончательном выражении, а может и нет.
В простейшем случае при отсутствии других членов сразу получаем конъюнкцию: :<math>f(x_1,x_2,1,1,...,1)= x_1x_2.</math>
Рассмотрим другие варианты.
- <math>x_1x_2 \oplus x_1 = x_1 \overline{x}_2;</math>
- <math>x_1x_2 \oplus x_2 = \overline{x}_1 x_2;</math>
- <math>x_1x_2 \oplus x_1 \oplus x_2 = \overline{\overline{x}_1 \overline{x}}_2.</math>
- <math>x_1x_2 \oplus 1 = \overline{x_1x}_2;</math>.
- <math>x_1x_2 \oplus x_1 \oplus 1 = \overline{x_1 \overline{x}}_2;</math>
- <math>x_1x_2 \oplus x_2 \oplus 1 = \overline{\overline{x}_1 x}_2;</math>
- <math>x_1x_2 \oplus x_1 \oplus x_2 \oplus 1 = \overline{x}_1 \overline{x}_2.</math>
Любое из этих выражений, используя инвертор, можно привести к конъюнкции.
Таким образом, имея нелинейную функцию, инвертор и константу 1 всегда можно получить конъюнкцию.
Имея конъюнкцию и инвертор, получим дизъюнкцию
Имея инвертор и конъюнкцию, всегда можно получить дизъюнкцию:
- <math>x_1+ x_2 = \overline{\overline{x}_1 \overline{x}}_2.</math>
- Теорема доказана.
Следствие
Функция <math>f</math> в одиночку является полной системой тогда и только тогда, когда:
- <math>f(0, 0, ..., 0)=1</math>
- <math>f(1, 1, ..., 1)=0</math>
- <math>f</math> не является самодвойственной
Примерами функций, в одиночку являющихся полной системой, будут штрих Шеффера <math>x|y = \overline{x \operatorname{\&} y}</math> и стрелка Пирса <math>x \downarrow y = \overline{x \vee y}</math>.
Теорема о максимальном числе функций в базисе
Доказательство
1) Докажем, что из любой полной системы функций можно выделить полную подсистему, состоящую не более чем из четырёх функций.
Согласно критерию Поста, в полной системе должны присутствовать пять функций:
- <math>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>f_0 </math>. Возможны два случая:
- <math>f_0 \in T_1,</math> тогда : <math>f_0 \not\in S</math> и система <math>[f_0,f_1,f_M,f_L]</math> полна.
- <math>f_0 \not\in T_1,</math> тогда : <math>f_0 \not\in M, T_1</math> и система <math>[f_0,f_S,f_L]</math> полна.
2) Покажем, что существует базис из четырёх функций. Рассмотрим систему функций <math>\{ 0,1,x \cdot y, x \oplus y \oplus z \}</math>. Эта система полна:
- <math>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>\{ 0,1,x \cdot y \} \subseteq M;</math>
- <math>\{ 0,1,x \oplus y \oplus z \} \subseteq L;</math>
- <math>\{ 0,x \cdot y, x \oplus y \oplus z \} \subseteq T_0;</math>
- <math>\{ 1,x \cdot y, x \oplus y \oplus z \} \subseteq T_1.</math>
Теорема доказана.
Примечания
Литература
Ссылки
См. также
