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

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

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

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

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


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

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


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


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


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


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


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


[math]\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 \}.[/math]

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


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


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


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


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


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


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




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


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


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


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


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


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

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


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


[math]f(x_1,x_2,\ldots,x_n)= a_0+ a_1x_1+a_2x_2+\ldots+ a_nx_n[/math]

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


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


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




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


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


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

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


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


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

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


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


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


[math]\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}[/math]
Тогда
[math]\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}[/math]

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


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


[math]\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}[/math]

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


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


[math]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.[/math]
Тогда
[math]\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}[/math]

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


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




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


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


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


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


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


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


[math]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\,.[/math]

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


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


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


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


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


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


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

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


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

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


[math]x^{\alpha_i}= \begin{cases}x,& \text{if}\quad \alpha_i=0,\\ x',& \text{if}\quad \alpha_i=1,\end{cases}[/math] для [math]1 \leqslant i \leqslant n[/math].
Для функции имеем:
[math]\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).[/math]
(1)

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


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


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

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


[math]\widetilde{f}_3(x)= f_3(x^{\gamma_1}, x^{\gamma_2}, \ldots, x^{\gamma_n})[/math], где [math]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}[/math] для [math]1 \leqslant i \leqslant n[/math].

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


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


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


[math]f_4(x_1,x_2,\ldots,x_n)= x_1\cdot \varphi(x_2,\ldots,x_n)+ \psi(x_2,\ldots,x_n),[/math]

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


[math]\widetilde{f}_4(x,y)= x\cdot \widetilde{\varphi}(y)+ \widetilde{\psi}(y)[/math], где [math]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}),[/math]

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

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


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

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


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

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


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


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


[math]\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}[/math]

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


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


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


[math]\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}[/math]

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


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


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


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


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


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

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