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

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

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

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

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

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

Оператор $[\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$.

Если к подалгебре $𝖯𝖠$, не совпадающей с $𝖯𝖠$ прибавить один элемент, ей не принадлежащий, и образовать замыкание, результатом будет новая подалгебра, содержащая данную. При этом, она совпадёт с $𝖯𝖠$, в том и только в том случае, если между исходной подалгеброй, и $𝖯𝖠$ нет никаких других подалгебр, то есть, если исходная подалгебра была максимальной. Таким образом, для того, чтобы проверить, что данное множество функций $R$ функционально полно, достаточно убедиться, что оно не входит целиком ни в одну из максимальных подалгебр $𝖯𝖠$. Оказывается, что таких подалгебр всего пять, и вопрос принадлежности к ним может быть решён просто и эффективно.

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

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

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

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

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

• Функция $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)$.

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

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

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

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

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

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

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

$f(0,0,\mathrm{...},0)=1$.

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

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

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

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

$f(1,1,\mathrm{...},1)=0$.

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

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

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

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

$f(x_1,x_2,\mathrm{...},x_n)=f({\bar{x}}_1,{\bar{x}}_2,\mathrm{...},{\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,\mathrm{...},0,\mathrm{...},x_n)=1$ и

$f(x_1,x_2,\mathrm{...},1,\mathrm{...},x_n)=0$.

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

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

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

Нелинейная функция по определению имеет в полиноме Жегалкина хотя бы один член, содержащий конъюнкцию нескольких переменных. Пусть переменные $x_1,x_2$ содержатся в этой конъюнкции, тогда $f(x_1,x_2,x_3,\mathrm{...},x_n)=x_1{x}_{2}A(x_3,\mathrm{...},x_n)\oplus x_{1}B(x_3,\mathrm{...},x_n)\oplus x_{2}C(x_3,\mathrm{...},x_n)\oplus D(x_3,\mathrm{...},x_n)$, где $A,B,C,D$ — полиномы Жегалкина.

Так как $A(x_3,\mathrm{...},x_n)$ — не константа 0, ведь $x_1{x}_2$ содержатся в полиноме Жегалкина функции $f$, то $A(x_3,\mathrm{...},x_n)=1$ на некотором наборе $\alpha =(x_3,\mathrm{...},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\vee x_2={\overline{{\stackrel{‾}{x}}_1\stackrel{‾}{x}}}_2.$

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

Следствие

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

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

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

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

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

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

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Ссылки

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

См. также

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