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

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

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

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

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

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

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

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

• $R\subseteq <!--\; \subseteq \; -->[R]$$R\subseteq [R]$     (экстенсивность)
• $R_1\subseteq <!--\; \subseteq \; -->R_2\Rightarrow <!--\; \Rightarrow \; -->[R_1]\subseteq <!--\; \subseteq \; -->[R_2]$$R_{1}\subseteq R_{2}\Rightarrow [R_{1}]\subseteq [R_{2}]$     (монотонность)
• $[[R]]=[R]$$[[R]]=[R]$     (идемпотентность)

Говорят, что множество функций $Q$$Q$  порождает замкнутый класс $R$$R$  (или класс $R$$R$  порождается множеством функций $Q$$Q$ ), если $[Q]=R$$[Q]=R$ . Множество функций $Q$$Q$  называется базисом замкнутого класса $R$$R$ , если $[Q]=R$$[Q]=R$  и $[Q_1]\ne <!--\; \ne \; -->R$$[Q_{1}]\neq R$  для любого подмножества $Q_1$$Q_1$  множества $Q$$Q$ , отличного от $Q$$Q$ .

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

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

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

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

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

Основные классы функций: $S,M,L,T_0,T_1$$S,M,L,T_{0},T_{1}$ Править

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

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

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

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

1. $\{\stackrel{¯<!--\; ¯\; -->}{x},xy\oplus <!--\; \oplus \; -->xz\oplus <!--\; \oplus \; -->yz\}\subset <!--\; \subset \; -->S\setminus <!--\; \setminus \; -->(M\cup <!--\; \cup \; -->L\cup <!--\; \cup \; -->T_0\cup <!--\; \cup \; -->T_1)$$\{{\bar {x}},xy\oplus xz\oplus yz\}\subset S\setminus (M\cup L\cup T_{0}\cup T_{1})$ 
2. $\{0,1,x\vee <!--\; \vee \; -->y\}\subset <!--\; \subset \; -->M\setminus <!--\; \setminus \; -->(S\cup <!--\; \cup \; -->L\cup <!--\; \cup \; -->T_0\cup <!--\; \cup \; -->T_1)$$\{0,1,x\lor y\}\subset M\setminus (S\cup L\cup T_{0}\cup T_{1})$ 
3. $\{1,x\oplus <!--\; \oplus \; -->y\}\subset <!--\; \subset \; -->L\setminus <!--\; \setminus \; -->(S\cup <!--\; \cup \; -->M\cup <!--\; \cup \; -->T_0\cup <!--\; \cup \; -->T_1)$$\{1,x\oplus y\}\subset L\setminus (S\cup M\cup T_{0}\cup T_{1})$ 
4. $\{x\oplus <!--\; \oplus \; -->y,xy\}\subset <!--\; \subset \; -->T_0\setminus <!--\; \setminus \; -->(S\cup <!--\; \cup \; -->M\cup <!--\; \cup \; -->L\cup <!--\; \cup \; -->T_1)$$\{x\oplus y,xy\}\subset T_{0}\setminus (S\cup M\cup L\cup T_{1})$ 
5. $\{x\oplus <!--\; \oplus \; -->y\oplus <!--\; \oplus \; -->1,x\vee <!--\; \vee \; -->y\}\subset <!--\; \subset \; -->T_1\setminus <!--\; \setminus \; -->(S\cup <!--\; \cup \; -->M\cup <!--\; \cup \; -->L\cup <!--\; \cup \; -->T_0)$$\{x\oplus y\oplus 1,x\lor y\}\subset T_{1}\setminus (S\cup M\cup L\cup T_{0})$ 

Всякий нетривиальный (отличный от $P_2$$P_2$ ) замкнутый класс булевых функций целиком содержится хотя бы в одном из классов $S,M,L,T_0,T_1$$S,M,L,T_{0},T_{1}$ .

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

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

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

ДоказательствоПравить

 

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

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

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

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

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

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

• В первом случае $f(1,1,...,1)=1,$$f(1,1,...,1)=1,$  тогда $f(x,x,...,x)=1,$$f(x,x,...,x)=1,$  и мы имеем константу единицы.
• Во втором случае $f(1,1,...,1)=0,$$f(1,1,...,1)=0,$  тогда $f(x,x,...,x)=\stackrel{¯<!--\; ¯\; -->}{x},$$f(x,x,...,x)={\overline {x}},$  и мы имеем инвертор.

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

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

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

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

• В первом случае $f(0,0,...,0)=0,$$f(0,0,...,0)=0,$  тогда $f(x,x,...,x)=0,$$f(x,x,...,x)=0,$  и мы имеем константу нуля.
• Во втором случае $f(0,0,...,0)=1,$$f(0,0,...,0)=1,$  тогда $f(x,x,...,x)=\stackrel{¯<!--\; ¯\; -->}{x},$$f(x,x,...,x)={\overline {x}},$  и мы имеем инвертор.

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

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

$f(x_1,x_2,...,x_n)=f({\stackrel{¯<!--\; ¯\; -->}{x}}_1,{\stackrel{¯<!--\; ¯\; -->}{x}}_2,...,{\stackrel{¯<!--\; ¯\; -->}{x}}_n).$$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(0,1,0)=f(1,0,1)=1,$  тогда $f(x,\stackrel{¯<!--\; ¯\; -->}{x},x)=1$$f(x,{\overline {x}},x)=1$  и мы имеем константу 1.

Аналогично, если, например, $f(0,0,0,1)=f(1,1,1,0)=0,$$f(0,0,0,1)=f(1,1,1,0)=0,$  тогда $f(x,x,x,\stackrel{¯<!--\; ¯\; -->}{x})=0$$f(x,x,x,{\overline {x}})=0$  и мы имеем константу 0.

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

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

Если в одном из вышеперечисленных случаев мы получили инвертор и одну из констант, вторую константу получим с помощью инвертора: $\stackrel{¯<!--\; ¯\; -->}{0}=1$${\overline {0}}=1$  или $\stackrel{¯<!--\; ¯\; -->}{1}=0.$${\overline {1}}=0.$ 

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

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

$f(x_1,x_2,...,0,...,x_n)=1$$f(x_{1},x_{2},...,0,...,x_{n})=1$  и

$f(x_1,x_2,...,1,...,x_n)=0.$$f(x_{1},x_{2},...,1,...,x_{n})=0.$ 

Пусть, например, $f(1,1,0)=0$$f(1,1,0)=0$  и $f(1,0,0)=1$$f(1,0,0)=1$ . Тогда $f(1,x,0)=\stackrel{¯<!--\; ¯\; -->}{x}$$f(1,x,0)={\overline {x}}$ .

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

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

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

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

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

$f(x_1,x_2,x_3,x_4,x_5)=1\oplus <!--\; \oplus \; -->x_1\oplus <!--\; \oplus \; -->x_1{x}_2{x}_3\oplus <!--\; \oplus \; -->x_2{x}_3{x}_4\oplus <!--\; \oplus \; -->x_2{x}_3{x}_5\oplus <!--\; \oplus \; -->x_2{x}_3{x}_4{x}_5.$$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.$$c(x_{1},x_{2})=x_{1}x_{2}.$ 

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

$f(x_1,x_2,1,1,1)=1\oplus <!--\; \oplus \; -->x_1\oplus <!--\; \oplus \; -->x_1{x}_2\oplus <!--\; \oplus \; -->x_2\oplus <!--\; \oplus \; -->x_2\oplus <!--\; \oplus \; -->x_2=1\oplus <!--\; \oplus \; -->x_1\oplus <!--\; \oplus \; -->x_1{x}_2\oplus <!--\; \oplus \; -->x_2.$$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 <!--\; \oplus \; -->x_1][\oplus <!--\; \oplus \; -->x_2][\oplus <!--\; \oplus \; -->1],$$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.$$f(x_{1},x_{2},1,1,...,1)=x_{1}x_{2}.$ 

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

• $x_1{x}_2\oplus <!--\; \oplus \; -->x_1=x_1{\stackrel{¯<!--\; ¯\; -->}{x}}_2;$$x_{1}x_{2}\oplus x_{1}=x_{1}{\overline {x}}_{2};$ 
• $x_1{x}_2\oplus <!--\; \oplus \; -->x_2={\stackrel{¯<!--\; ¯\; -->}{x}}_1{x}_2;$$x_{1}x_{2}\oplus x_{2}={\overline {x}}_{1}x_{2};$ 
• $x_1{x}_2\oplus <!--\; \oplus \; -->x_1\oplus <!--\; \oplus \; -->x_2={\stackrel{¯<!--\; ¯\; -->}{{\stackrel{¯<!--\; ¯\; -->}{x}}_1\stackrel{¯<!--\; ¯\; -->}{x}}}_2.$$x_{1}x_{2}\oplus x_{1}\oplus x_{2}={\overline {{\overline {x}}_{1}{\overline {x}}}}_{2}.$ 
• $x_1{x}_2\oplus <!--\; \oplus \; -->1={\stackrel{¯<!--\; ¯\; -->}{x_{1}x}}_2;$$x_{1}x_{2}\oplus 1={\overline {x_{1}x}}_{2};$ .
• $x_1{x}_2\oplus <!--\; \oplus \; -->x_1\oplus <!--\; \oplus \; -->1={\stackrel{¯<!--\; ¯\; -->}{x_1\stackrel{¯<!--\; ¯\; -->}{x}}}_2;$$x_{1}x_{2}\oplus x_{1}\oplus 1={\overline {x_{1}{\overline {x}}}}_{2};$ 
• $x_1{x}_2\oplus <!--\; \oplus \; -->x_2\oplus <!--\; \oplus \; -->1={\stackrel{¯<!--\; ¯\; -->}{{\stackrel{¯<!--\; ¯\; -->}{x}}_{1}x}}_2;$$x_{1}x_{2}\oplus x_{2}\oplus 1={\overline {{\overline {x}}_{1}x}}_{2};$ 
• $x_1{x}_2\oplus <!--\; \oplus \; -->x_1\oplus <!--\; \oplus \; -->x_2\oplus <!--\; \oplus \; -->1={\stackrel{¯<!--\; ¯\; -->}{x}}_1{\stackrel{¯<!--\; ¯\; -->}{x}}_2.$$x_{1}x_{2}\oplus x_{1}\oplus x_{2}\oplus 1={\overline {x}}_{1}{\overline {x}}_{2}.$ 

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

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

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

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

$x_1+x_2={\stackrel{¯<!--\; ¯\; -->}{{\stackrel{¯<!--\; ¯\; -->}{x}}_1\stackrel{¯<!--\; ¯\; -->}{x}}}_2.$$x_{1}+x_{2}={\overline {{\overline {x}}_{1}{\overline {x}}}}_{2}.$ 

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

СледствиеПравить

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

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

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

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

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

ДоказательствоПравить

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

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

$f_0\notin T_0;f_1\notin T_1;f_S\notin S;f_M\notin M;f_L\notin L.$$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}$ . Возможны два случая:

• $f_0\in <!--\; \in \; -->T_1,$$f_{0}\in T_{1},$  тогда : $f_0\notin S$$f_{0}\not \in S$  и система $[f_0,f_1,f_M,f_L]$$[f_{0},f_{1},f_{M},f_{L}]$  полна.
• $f_0\notin T_1,$$f_{0}\not \in T_{1},$  тогда : $f_0\notin M,T_1$$f_{0}\not \in M,T_{1}$  и система $[f_0,f_S,f_L]$$[f_{0},f_{S},f_{L}]$  полна.

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

$0\notin T_1,S;1\notin T_0;x\cdot <!--\; \cdot \; -->y\notin L;x\oplus <!--\; \oplus \; -->y\oplus <!--\; \oplus \; -->z\notin M.$$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 <!--\; \cdot \; -->y\}\subseteq <!--\; \subseteq \; -->M;$$\{0,1,x\cdot y\}\subseteq M;$ 
• $\{0,1,x\oplus <!--\; \oplus \; -->y\oplus <!--\; \oplus \; -->z\}\subseteq <!--\; \subseteq \; -->L;$$\{0,1,x\oplus y\oplus z\}\subseteq L;$ 
• $\{0,x\cdot <!--\; \cdot \; -->y,x\oplus <!--\; \oplus \; -->y\oplus <!--\; \oplus \; -->z\}\subseteq <!--\; \subseteq \; -->T_0;$$\{0,x\cdot y,x\oplus y\oplus z\}\subseteq T_{0};$ 
• $\{1,x\cdot <!--\; \cdot \; -->y,x\oplus <!--\; \oplus \; -->y\oplus <!--\; \oplus \; -->z\}\subseteq <!--\; \subseteq \; -->T_1.$$\{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

См. такжеПравить

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