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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Говорят, что множество функций ~Q порождает замкнутый класс ~R (или класс ~R порождается множеством функций ~Q), если ~[Q]=R. Множество функций ~Q называется базисом замкнутого класса ~R, если ~[Q]=R и ~[Q_1]\ne 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^*.

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

Основные классы функций[править | править исходный текст]

  • Функция f(x_1, x_2, \ldots, x_n) называется сохраняющей ноль, если f(0, 0, \ldots,0) = 0. Обозначают, что f \in T_0.
  • Функция f(x_1, x_2, \ldots, x_n) называется сохраняющей единицу, если f(1, 1, \ldots,1) = 1. Обозначают, что f \in 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)}. Обозначают, что f \in S.
  • Функция называется монотонной: (\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). Обозначают, что f \in M.
    • (\beta_1, \beta_2, \ldots, \beta_n) \ge (\alpha_1, \alpha_2, \ldots, \alpha_n)  \Leftrightarrow \forall i (\beta_i \ge \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}). Обозначают, что f \in 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. Для неё

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

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

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

Имея функцию, не сохранающую 1, получим инвертор или конституенту 0[править | править исходный текст]

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

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

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

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

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

Пусть из функций, не принадлежащих классам Т1 или Рассмотрим функцию, не принадлежащую классу 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 и мы имеем конституенту единицы.

Аналогично, если, например, ~ f(0,0,0,1)=f(1,1,1,0)=0, тогда ~ f(x,x,x,\overline{x})=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}.

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

Имеем инвертор и обе конституенты[править | править исходный текст]

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

Имея нелинейную функцию, инвертор и конституенту 1, получим конъюнкцию[править | править исходный текст]

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

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

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

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

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

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

~ f(x_1,x_2,1,1,...,1)= x_1x_2 [ \oplus x_1 ] [ \oplus x_2 ] [ \oplus 1 ],

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

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

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

  • ~ x_1x_2 \oplus x_1 = x_1 \overline{x}_2;
  • ~ x_1x_2 \oplus x_2 = \overline{x}_1 x_2;
  • ~ x_1x_2 \oplus x_1 \oplus x_2 = \overline{\overline{x}_1 \overline{x}}_2.
  • ~ x_1x_2 \oplus 1 = \overline{x_1x}_2;.
  • ~ x_1x_2 \oplus x_1 \oplus 1 = \overline{x_1 \overline{x}}_2;
  • ~ x_1x_2 \oplus x_2 \oplus 1 = \overline{\overline{x}_1 x}_2;
  • ~ x_1x_2 \oplus x_1 \oplus x_2 \oplus 1 = \overline{x}_1 \overline{x}_2.

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

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

Имея конъюнкцию и инвертор, получим дизъюнкцию[править | править исходный текст]

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

~ x_1+ x_2 = \overline{\overline{x}_1 \overline{x}}_2.
  • Теорема доказана.

Следствие[править | править исходный текст]

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

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

Теорема о максимальном числе функций в базисе[править | править исходный текст]

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

Доказательство[править | править исходный текст]

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.

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

Примечания[править | править исходный текст]

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

Литература[править | править исходный текст]

  • С. С. Марченков, «Замкнутые классы булевых функций»
  • Образовательный сайт MiniSoft
  • Фудзисава Т., Касами Т. Математика для радиоинженеров: теория дискретных структур. — М.: Радио и связь, 1984. — 240 с.
  • Алексеев В.Б. Дискретная математика. II семестр. — М.: Изд-во МГУ, 2002. — 44 с.

См. также[править | править исходный текст]