Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]


Системы булевых функций

Системы булевых функций


В теореме 10.5 доказано, что всякая булева функция может быть представлена в виде суперпозиции трех булевых функций: дизъюнкции, конъюнкции и отрицания. В настоящем параграфе тема представления булевых функций в виде суперпозиций функций из некоторой системы развивается и доводится до определенного конца: приводятся необходимые и достаточные условия (теорема 11.4 Поста), которым должна удовлетворять система булевых функций для того, чтобы всякая булева функция могла быть представлена в виде суперпозиции функций из этой системы.


Полные системы булевых функций


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


Определение 11.1. Система булевых функций называется полной, если всякая булева функция является суперпозицией функций из этой системы.


Теорема 11.2. Следующие системы булевых функций являются полными:


\mathsf{1)}~ \{\lor,\cdot,'\};\quad \mathsf{2)}~ \{+,\cdot,'\};\quad \mathsf{3)}~ \{\lor,'\};\quad \mathsf{4)}~ \{\cdot,'\};\quad \mathsf{5)}~ \{\to,'\};\quad \mathsf{6)}~ \{ \mid \};\quad \mathsf{7)}~ \{ \downarrow \}.

Доказательство. Полнота первой системы доказана в теореме 10.5. Это можно использовать для доказательства полноты остальных систем, приведенных в теореме.


В силу полноты системы \{\lor,\cdot,'\} каждая булева функция является суперпозицией дизъюнкции, конъюнкции и отрицания. Если мы сможем выразить дизъюнкцию через функции +,\cdot и {}', то тем самым докажем, что всякую функцию можно выразить через эти функции, т.е. докажем полноту системы функций \{+,\cdot,'\}. Это можно сделать так: x\lor y=x+y+x\cdot y. Предлагается самостоятельно проверить справедливость приведенного тождества.


Аналогично, для проверки полноты системы \{\lor,'\} нужно выразить конъюнкцию через дизъюнкцию и отрицание. Соответствующее тождество известно (см. теорему 9.5, пункт а).


Полнота системы \{\cdot,'\} вытекает из полноты системы \{\lor,\cdot,'\} и тождества теоремы 9.5, пункт б, выражающего дизъюнкцию через конъюнкцию и отрицание, а полнота системы \{\to,'\} — из полноты системы \{\lor,'\} и тождества теоремы 9.5, пункт в, выражающего дизъюнкцию через импликацию.


Наконец система \{ \mid \} полна, потому что каждая функция есть суперпозиция функций \lor и {}', а обе эти функции могут быть выражены через функцию штрих Шеффера (см. теорему 9.5, пункты ж, и). Аналогично, система \{\downarrow\} полна, так как полна система \{\cdot,'\} и справедливы тождества теоремы 9.5, пункты к, м, выражающие функции \cdot и {}' через стрелку Пирса \downarrow.


Итак, теорема доказана.


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




Специальные классы булевых функций


Говорят, что булева функция f(x_1,x_2,\ldots,x_n) сохраняет 0, если f(0,0,\ldots,0)=0. Обозначим P_0 — класс всех булевых функций, сохраняющих 0.


Говорят, что булева функция f(x_1,x_2,\ldots,x_n) сохраняет 1, если f(1,1,\ldots,1)=1. Обозначим P_1 — класс всех булевых функций, сохраняющих 1.


Булева функция f^{\ast}(x_1,x_2,\ldots,x_n) называется двойственной функцией для булевой функции f(x_1,x_2,\ldots,x_n), если f^{\ast}(x_1,x_2,\ldots,x_n)= f'(x'_1,x'_2,\ldots,x'_n) для любых x_1,x_2,\ldots,x_n. Булева функция f называется самодвойственной, если f^{\ast}=f. Класс всех самодвойственных булевых функций обозначим S.


Введем на множестве \{0;1\} отношение порядка, полагая, что 0 \leqslant 0,~ 0 \leqslant 1,~ 1 \leqslant 1. Булева функция f(x_1,x_2,\ldots,x_n) называется монотонной, если для любых


\alpha_1,\alpha_2,\ldots,\alpha_n,~ \beta_1,\beta_2,\ldots,\beta_n\in \{0;1\} из неравенств \alpha_1 \leqslant \beta_1,\alpha_2 \leqslant \beta_2,\ldots,\alpha_n \leqslant \beta_n

немедленно следует, что f(\alpha_1,\alpha_2,\ldots,\alpha_n)= f(\beta_1,\beta_2,\ldots,\beta_n). Класс всех монотонных функций обозначим M.


Наконец, булева функция f(x_1,x_2,\ldots,x_n) называется линейной, если ее можно представить в виде следующего выражения (называемого полиномом Жегалкина степени не выше первой):


f(x_1,x_2,\ldots,x_n)= a_0+ a_1x_1+a_2x_2+\ldots+ a_nx_n

где a_0,a_1,a_2,\ldots,a_n — постоянные, равные либо 0, либо 1. Символом L обозначим класс всех линейных булевых функций.


Введенные классы булевых функций P_0,P_1,S,M,L играют главную роль при описании полных систем булевых функций. В следующей теореме устанавливаются два важных свойства этих классов и одновременно рассматриваются примеры функций, принадлежащих и не принадлежащих каждому из них.


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




Теорема 11.3. Классы P_0,P_1,S,M,L являются собственными замкнутыми классами булевых функций.


Доказательство. Проверим сначала, что все эти классы являются собственными. Укажем функции, которые принадлежат и не принадлежат каждому из рассматриваемых классов, предоставляя читателю проверить самостоятельно данные утверждения. Как классу P_0, так и классу P_1 принадлежит, например, конъюнкция и не принадлежит отрицание. Далее, конъюнкция не является самодвойственной функцией, а отрицание есть функция самодвойственная. (Проверим последнее утверждение. Пусть f(x)=x'. Тогда


f^{\ast}(x)= f'(x')= \bigl(f(x')\bigr)'= (x'')'= x'= f(x), то есть f^{\ast}=f,

а значит, f(x)=x' — самодвойственная функция.) Наконец, к классу монотонных функций принадлежит конъюнкция и не принадлежит импликация, а к классу L линейных функций принадлежит сложение по модулю два (сумма Жегалкина) и не принадлежит конъюнкция.


Покажем теперь замкнутость этих классов. Пусть f_1,f_2,f_3\in P_0, то есть


f(0;0)=f_2(0;0)= f_3(0;0)=0 и g(x_1,x_2)= f_1\bigl(f_2(x_1,x_2), f_3(x_1,x_2)\bigr).

Тогда g(0;0)= f_1\bigl(f_2(0;0), f_3(0;0)\bigr)= f_1(0;0)=0, то есть g\in P_0.


Аналогично проверяется замкнутость класса P_1.


Пусть теперь f_1,f_2,f_3\in S, то есть


\begin{gathered}f'_1(u,v)= f_1(u',v'),~~ f'_2(x'_1,x'_2)= f_2(x_1,x_2),~~ f'_3(x'_1,x'_2)= f_3(x_1,x_2),\\ g(x_1,x_2)= f_1\bigl(f_2(x_1,x_2), f_3(x_1,x_2)\bigr) \end{gathered}
Тогда
\begin{aligned}g^{\ast}(x_1,x_2)&= g'(x'_1,x'_2)= f'_1\bigl(f_2(x'_1,x'_2), f_3(x'_1,x'_2)\bigr)= f_1\bigl(f'_2(x'_1,x'_2), f'_3(x'_1,x'_2)\bigr)=\\ &= f_1\bigl(f_2(x_1,x_2), f_3(x_1,x_2)\bigr)= g(x_1,x_2),\end{aligned}

то есть g^{\ast}=g, и значит g\in S.


Пусть далее f_1,f_2,f_3\in M и \alpha_1 \leqslant \beta_1,~ \alpha_2 \leqslant \beta_2 и g(x_1,x_2)= f_1\bigl(f_2(x_1,x_2), f_3(x_1,x_2)\bigr). Тогда


\begin{gathered} f_2(\alpha_1,\alpha_2) \leqslant f_2(\beta_1,\beta_2),\quad f_3(\alpha_1,\alpha_2) \leqslant f_3(\beta_1,\beta_2),\\ g(\alpha_1,\alpha_2)= f_1\bigl(f_2(\alpha_1,\alpha_2), f_3(\alpha_1,\alpha_2)\bigr) \leqslant f_1\bigl(f_2(\beta_1,\beta_2), f_3(\beta_1,\beta_2)\bigr)= g(\beta_1,\beta_2).\end{gathered}

Следовательно, g\in M.


Наконец, пусть f_1,f_2,f_3\in L, то есть, например,


f_1(x_1,x_2)= a_0+a_1x_1+a_2x_2,\quad f_2(x_1,x_2)= b_0+b_1x_1+b_2x_2,\quad f_3(x_1,x_2)= c_0+c_1x_1+c_2x_2.
Тогда
\begin{aligned}g(x_1,x_2)&= f_1\bigl(f_2(x_1,x_2), f_3(x_1,x_2)\bigr)=\\ &= a_0+a_1\cdot f_2(x_1,x_2)+ a_2\cdot f_3(x_1,x_2)=\\ &= a_0+a_1\cdot (b_0+b_1x_1+b_2x_2)+a_2\cdot (c_0+c_1x_1+c_2x_2)=\\ & = (a_0+a_1b_0+a_2c_0)+ (a_1b_1+a_2c_1)\cdot x_1+ (a_1b_2+a_2c_2)\cdot x_2=\\ &= d_0+d_1x_1+d_2x_2, \end{aligned}

то есть g\in L.Теорема доказана.


Заметим, что, например, функция f(x)=x принадлежит каждому из пяти классов P_0,P_1,S,M,L.




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


Эта теорема доказана американским математиком Э. Постом в 1921 г.


Теорема 11.4 (о полноте системы булевых функций). Система булевых функций \{f_0,f_1,\ldots,f_s,\ldots\} является полной тогда и только тогда, когда в этой системе имеется функция, не принадлежащая классу P_0, имеется функция, не принадлежащая классу P_1, имеется функция, не принадлежащая классу S, имеется функция, не принадлежащая классу M, имеется функция, не принадлежащая классу L.


Доказательство. Необходимость. Пусть система булевых функций \{f_0,f_1,\ldots,f_s,\ldots\} полна. Допустим, что все функции этой системы входят в класс P_0. Поскольку на основании предыдущей теоремы класс P_0 замкнут, то всякая суперпозиция любых функций из данной системы есть функция из класса P_0. Но также по предыдущей теореме класс P_0 не исчерпывает всех булевых функций. Поэтому найдется булева функция (не принадлежащая классу P_0), которая не является суперпозицией функций из системы \{f_0,f_1,\ldots,f_s,\ldots\}, что противоречит полноте этой системы. Следовательно, в системе имеется функция, не принадлежащая классу P_0.


Совершенно аналогично доказываются утверждения о наличии в системе \{f_0,f_1,\ldots, f_s,\ldots\} функций, не принадлежащих классам P_1,S,M,L.


Достаточность. Предположим, что среди функций системы \{f_0,f_1,\ldots,f_s,\ldots\} имеются такие функции f_0,f_1,f_2,f_3,f_4, что


f_0\notin P_0,\quad f_1\notin P_1,\quad f_2\notin S,\quad f_3\notin M,\quad f_4\notin L\,.

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


Начнем с f_0, для которой f_0(0,0,\ldots,0)=1. Введем функцию \widetilde{f}_0(x)= f_0(x,x,\ldots,x). Для нее имеем: \widetilde{f}_0(0)=1, \widetilde{f}_0(1)=0 или 1. Следовательно, \widetilde{f}_0(x)=x' или \widetilde{f}_0(x)=1.


Аналогично, из f_1, для которой f_1(1,1,\ldots,1)=0, строим функцию \widetilde{f}_1(x)= f_1(x,x,\ldots,x). Для нее имеем: \widetilde{f}_1(1)=0, \widetilde{f}_1(0)=0 или 0. Следовательно, \widetilde{f}_1(x)=x' или \widetilde{f}_1(x)=0.


Таким образом, получаем одну из следующих четырех пар функций: x' и x' (1); x' и 0 (2); x' и 1 (3); 0 и 1 (4).


В каждом из случаев (2) и (3) имеем тогда по три функции x',~0,~1 (например, если есть функции x' и 0, то константа 1 получается как 0').


Рассмотрим случай (1). Покажем, что и здесь можно получить обе константы 0 и 1. Для этого привлечем несамодвойственную функцию f_2 (то есть f_2\notin S). Для нее f_2\ne f_2^{\ast}, то есть


f_2\bigl(\alpha_1,\alpha_2,\ldots,\alpha_n\bigr)\ne f'_2\bigl(\alpha'_1,\alpha'_2,\ldots,\alpha'_n \bigr)

для некоторого набора \alpha_1, \alpha_2, \ldots, \alpha_n из нулей и единиц. Следовательно, для этого набора


f_2\bigl(\alpha_1,\alpha_2,\ldots,\alpha_n\bigr)= f_2\bigl(\alpha'_1,\alpha'_2,\ldots,\alpha'_n \bigr).

Построим теперь функцию f_2(x) по следующему правилу: \widetilde{f}_2(x)= f_2(x^{\alpha_1}, x^{\alpha_2},\ldots, x^{\alpha_n}) , где


x^{\alpha_i}= \begin{cases}x,& \text{if}\quad \alpha_i=0,\\ x',& \text{if}\quad \alpha_i=1,\end{cases} для 1 \leqslant i \leqslant n.
Для функции имеем:
\widetilde{f}_2(0)= f_2\bigl(\alpha_1,\alpha_2,\ldots,\alpha_n\bigr)= f_2\bigl(\alpha'_1,\alpha'_2,\ldots,\alpha'_n\bigr)= \widetilde{f}_2(1).
(1)

Следовательно, \widetilde{f}_2(x) — константа. Поскольку в нашем распоряжении имеется отрицание x', то из этой константы (0 или 1) можно получить и другую константу (1 или О соответственно). Итак, в случае (1) имеем функции x',0,1.


Рассмотрим случай (4). Здесь к константам 0 и 1 необходимо получить функцию x'. Для этого привлечем немонотонную функцию f_3 (то есть f_3\notin M). Ее немонотонность означает: найдутся такие наборы из нулей и единиц (\alpha_1,\alpha_2,\ldots,\alpha_n) и (\beta_1,\beta_2,\ldots,\beta_n), что


(\alpha_1,\alpha_2,\ldots,\alpha_n) \leqslant (\beta_1,\beta_2,\ldots,\beta_n), но f(\alpha_1,\alpha_2,\ldots,\alpha_n) > f(\beta_1,\beta_2,\ldots,\beta_n).

Построим функцию \widetilde{f}_3(x) по следующему правилу:


\widetilde{f}_3(x)= f_3(x^{\gamma_1}, x^{\gamma_2}, \ldots, x^{\gamma_n}), где x^{\gamma_i}= \begin{cases}0, &\text{if}\quad \alpha_i=\beta_i=0,\\ 1, &\text{if}\quad \alpha_i=\beta_i=1,\\ x, &\text{if}\quad \alpha_i=0,\, \beta_i=1,\end{cases} для 1 \leqslant i \leqslant n.

Тогда ясно, что \widetilde{f}_3(0)> \widetilde{f}_3(1). Следовательно, должно быть \widetilde{f}_3(0)=1, \widetilde{f}_3(1)=0. Значит, \widetilde{f}_3(x)=x'.


Итак, из данной системы функций с помощью суперпозиций нами сконструированы функции x',0,1.


Рассмотрим теперь еще не использованную нами нелинейную функцию f_4 (то есть f_4\notin L). Предположим, что x_1 — тот ее аргумент, который в разложение в полином Жегалкина функции f_4 входит нелинейно. Это означает, что f_4 может быть представлена в виде


f_4(x_1,x_2,\ldots,x_n)= x_1\cdot \varphi(x_2,\ldots,x_n)+ \psi(x_2,\ldots,x_n),

где \varphi\ne0,~ \varphi\ne1 (в противном случае функция f_4 имела бы два различных представления полиномами Жегалкина, что невозможно). Поэтому, если \varphi(0,\ldots,0)=a, то найдется такой набор \alpha_2,\ldots,\alpha_n, что \varphi(\alpha_2,\ldots,\alpha_n)=a'. Построим функцию \widetilde{f}_4(x,y) по следующему правилу:


\widetilde{f}_4(x,y)= x\cdot \widetilde{\varphi}(y)+ \widetilde{\psi}(y), где x=x_1,~ \widetilde{\varphi}(y)= \varphi(y^{\alpha_2},\ldots,y^{\alpha_n}),~ \widetilde{\psi}(y)= \psi(y^{\alpha_2},\ldots,y^{\alpha_n}),

y^{\alpha_i}= \begin{cases} 0,& \text{if}\quad \alpha_i=0,\\ y,& \text{if}\quad \alpha_i=1, \end{cases} для 2\leqslant i\leqslant n.

Заметим, что мы можем подставлять 0 вместо x_i, так как функция 0 нами уже получена. Тогда ясно, что


\widetilde{\varphi}(0)= \varphi(0,\ldots,0)= a,\qquad \widetilde{\varphi}(1)= \varphi(\alpha_2,\ldots,\alpha_n)=a'.

Следовательно, \widetilde{\varphi}(y)=y или \widetilde{\varphi}(y)=y'. Заметим, что y'=y+1. Значит, \widetilde{\varphi}(y) можно представить в виде \widetilde{\varphi}(y)=y+b_0, где b_0=0 или 1. Кроме того, ясно, что функцию одного аргумента \widetilde{\psi}(y) можно представить в виде линейного полинома Жегалкина: \widetilde{\psi}(y)=b_1y+b_2. Таким образом, \widetilde{f}_4(x,y) имеет вид:


\widetilde{f}_4(x,y)= x(y+b_0)+ (b_1y+b_2)= xy+bx+cy+d\,.

Рассмотрим всевозможные случаи для коэффициентов b,~c,~d.


Если b=c=d=0, то \widetilde{f}_4(x,y)=x\cdot y.


Если b=1, то рассмотрим функцию


\begin{aligned}\widetilde{f}'_4(x,y)&= \widetilde{f}_4(x,y')= xy'+x+cy'+d= x(y+1)+x+c(y+1)+d=\\ &=xy+x+x+cy+c+d=xy+cy+c_1\,.\end{aligned}

(Заметим, что мы можем подставлять y' вместо y, так как функция "отрицание" нами уже получена.)


Если c=c_1=0, то \widetilde{f}'_4(x,y)=x\cdot y.


Если c=1, то рассмотрим функцию


\begin{aligned}\widetilde{f}''_4(x,y)&= \widetilde{f}'_4(x',y)= x'y+y+c_1= (x+1)y+y+c_1=\\ &=xy+y+y+c_1= xy+c_1\,.\end{aligned}

Если в ней c_1=0, то \widetilde{f}''_4(x,y)=x\cdot y.


Если же c_1=1, то \widetilde{f}''_4(x,y)=xy+1= (x\cdot y)'= x\mid y (штрих Шеффера).


Итак, из функций f_0,f_1,f_2,f_3,f_4, имеющихся в данной системе функций, мы получаем с помощью суперпозиций функции x' и x\cdot y или же функцию x\mid y. Поскольку на основании теоремы 11.2 каждая из систем булевых функций \{',\cdot\} и \{\phantom{|} \vline \phantom{|}\} полна, то и данная система булевых функций \{f_0,f_1,\ldots,f_s,\ldots\} полна.


Теорема полностью доказана.

Перейти на форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2018 MathHelpPlanet.com. All rights reserved