Математическая логика - Системы булевых функций

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

Напомним, что понятие суперпозиции булевых функций обсуждалось в предыдущей лекции (определение 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$ .