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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[cbm]\widetilde{f}_4(x,y)= x\cdot \widetilde{\varphi}(y)+ \widetilde{\psi}(y)[/cbm] , где [cbm]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}),[/cbm]
[cbm]y^{\alpha_i}= \begin{cases} 0,& \text{if}\quad \alpha_i=0,\\ y,& \text{if}\quad \alpha_i=1, \end{cases}[/cbm] для [cbm]2\leqslant i\leqslant n[/cbm] .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: