Булеви функции - основни понятия и дефиниции - част II

Сега ще се спрем на комутативност, асоциативност и дистрибутивност при някои от двоичните функции на две променливи:

1) ${\bf x_1.x_2=x_2.x_1}$ т.е. конюнкцията изпълнява комутативния закон

Доказателство: Доказателството на този факт е елементарен, тъй като от таблицата за истинност (виж тук) можем да видим, че при $x_1=0$ и $x_2=1$ конюнкцията има стойност $0$. Същата тази стойност има и при $x_1=1$ и $x_2=0$ или казано с други думи $0.1=1.0=0$.

2) ${\bf x_1\lor x_2=x_2\lor x_1}$ т.е. дизюнкцията изпълнява комутативния закон.

Доказателство: Доказателството и на това твърдение следва непосредствено от таблицата за истинност. В нея сме записали, че $0\lor 1=1$ и $1\lor 0=1$. 

3) ${\bf x_1+x_2=x_2+x_1}$ - изключващото или (сума по модул $2$) удовлетворява комутативния закон.
Доказателство: По аналогичен начин на горните две функции.

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

В сила са още и свойствата:

4) ${\bf x_1.(x_2.x_3)=(x_1.x_2).x_3}$ - асоциативност на конюнкцията

5) ${\bf x_1\lor (x_2\lor x_3)=(x_1\lor x_2)\lor x_3}$ - асоциативност на дизюнкцията

6) ${\bf x_1+(x_2+x_3)=(x_1+x_2)+x_3}$ - асоциативност на изключващото или

7) ${\bf x_1.(x_2\lor x_3)=x_1.x_2\lor x_1.x_3}$ - дистрибутивен закон

8) ${\bf x_1.(x_2+x_3)=x_1.x_2+x_1.x_3}$ - дистрибутивен закон

Когато изчисляваме изрази с двоични функции е задължително познаването на приоритета им. Както добре знаем от "класическата математика" например умножението има по-висок приоритет от събирането. Ако не спазваме това правило бихме допускали грешки при пресмятанията. Същото е и при изрази с двоични функции. За това е нужно да спазваме следния приоритет:

1) скоби;

2) отрицание;

3) конюнкция;

4) дизюнкция и изключващо или (в този случай се смята в посока от ляво надясно);

5) всички останали функции;

1 Задача Да се пресметне изразът $1\downarrow(\overline{0}\lor 1+\overline{0}(1+\overline{0}))$.

Решение: Тъй като с най-висок приоритет са скобите, първо ще започнем от там. Забелязваме, че в скобите имаме отрицание, което е втория по приоритет, следователно имаме:

$1\downarrow (1\lor 1+1(1+1))=1\downarrow (1\lor 1+1.0)=$

$1\downarrow (1\lor 1+0)=1\downarrow (1+0)=1\downarrow 1=0$.

Свойства на някои булеви функции

1) Свойства на константите:

$x+1=\overline{x}$; $x+0=x$; $x.1=x$; $x.0=0$.

2) Свойства на отрицанието:

$x.\overline{x}=0$; $x+\overline{x}=1$; $\overline{\overline{x}}=x$.

3) Свойства на еквивалентността:

$x_1\equiv x_2=\overline{x_1+x_2}=(x_1\rightarrow x_2)(x_2\rightarrow x_1)=(\overline{x_1}+x_2)(\overline{x_2}+x_1)$

4) Свойства на импликацията:

$x\rightarrow x_2=\overline{x_1}+x_2$; $x\rightarrow x_2=\overline{x_2}\rightarrow\overline{x_1}$.

5) Свойства на изключващото или:

$x_1+x_2=\overline{x_1\equiv x_2}=x_1\overline{x_2}+\overline{x_1}x_2=(x_1+x_2)(\overline{x_2}+\overline{x_1})$.

6) Свойства на чертата на Шефер:

$x_1\mid x_2=\overline{x_1.x_2}=\overline{x_1}\lor\overline{x_2}$.

7) Свойства на стрелката на Пиърс:

$x_1\downarrow x_2=\overline{x_1\lor x_2}=\overline{x_1}.\overline{x_2}$.

Нека $F=\{f_1(x_1,\ldots,x_n),f_2(x_1,\ldots, x_n),\ldots\}$ е произволно множество от двоични функции.

Определение 2: Под формула над множеството $F$ ще разбираме:

1. Всички функции от $F$.

2. Всички изрази от вида $f_i(\phi_1,\ldots,\phi_{n_i})$, където $f_i\in F$, а $\phi_j$ е или формула над $F$ или буква на променлива, $j=1,2\ldots, n_i$.

Определение 3: На всяка формула ще съпоставяме еднозначно по естествен начин функция и ще казваме, че формулата реализира тази функция.

Определение 4: Ако една функция се реализира с формула над $F$, то казваме, че тя е суперпозиция над $F$ или още обвивка.

С $[F]$ ще означаваме множеството от всички суперпозиции над $F$ (обвивката на $F$).

Пример: $f=x_1\lor x_2.\overline{x_3}$ е формула над $F=\{\lor, . ,\overline{}\}$ т.е. в $F$ имаме функциите дизюнкция, конюнкция и отрицание. Тук $f$ е над $F$ т.е. $f$ е формула над $F$, като $f$ реализира функцията дадена в таблицата по-долу:

Нека да разгледаме множеството $F=\{.,\overline{}\}$. Очевидно то е съставено от функциите конюнкция и отрицание. Тогава множеството $[F]$ ще се състои от всички други функции, които можем да реализираме чрез конюнкция и отрицание. Например от Закона на Де Морган знаем, че $\overline{x_1\lor x_2}=\overline{x_1}.\overline{x_2}$ и следователно $x_1\lor x_2=\overline{\overline{x_1}.\overline{x_2}}$ т.е. реализирахме дизюнкцията само чрез конюнкция и отрицание. Също така от Закона на Де Морган е известно, че $x_1\mid x_2$, както и, че $x_1\downarrow x_2=\overline{x_1\lor x_2}=\overline{x_1}.\overline{x_2}$ т.е. чрез конюнкция и отрицание реализирахме и чертата на Шефер, както и стрелката на Пиърс. Както по-късно ще видим с функциите конюнкция и отрицание можем да реализираме всяка двоична функция. От казаното до тук следва, че за множеството от всички суперпозиции над $F$ имаме $[F]=\{.,\overline{},\lor,\mid, \downarrow\ldots\}$. На мястото на многоточието в множеството $[F]$ можем да запишем и всяка друга двоична функция на $n$ променливи.

Определение 5: Едно множество от двоични функции $F$ ще наричаме пълно, ако $[F]\equiv F_2$ или казано с други думи - едно множество от двоични функции $F$ ще наричаме пълно, ако множеството от суперпозициите му (неговата обвивка) съвпада с множеството от всички двоични функции.

Теорема 1 (Теорема на Бул): Множеството съставено от двоичните функции $\{{\bf .},{\bf  \lor},{\bf  \overline{}}\}$ е пълно.

Доказателство: Нека да вземем $f(x_1,x_2,\ldots, x_n)=0$. Тогава със сигурност можем да твърдим, че $f(x_1,x_2\ldots, x_n)=x_1.\overline{x_1}$.

Нека сега $f(x_1,x_2,\ldots, x_n)$ е произволна двоична функция, различна от нула. Да означим $x^{\alpha}=\overline{x}$, при $a=0$ и $x^{\alpha}=x$, при $a=1$. 

Лесно се вижда, че $x^{a}=1$, тогава и само тогава, когато $x=a$. От тук следва, че $x_{1}^{a_1}x_2^{a_2}\ldots x_n^{a_n}=1$ тогава и само тогава, когато $x_1=a_1, x_2=a_2,\ldots, x_n=a_n$. Следователно (1) $f(x_1,x_2,\ldots, x_n)=\displaystyle\lor_{f(a_1,a_2,\ldots, a_n)=1}x_1^{a_1}x_2^{a_2}\ldots x_n^{a_n}$, където дизюнкцията се взема по всички $n$-орки $(a_1, a_2,\ldots, a_n)$, за които $f(a_1,a_2,\ldots, a_n)$.

Нека $f(b_1,b_2\ldots, b_n)$. Тогава в дясната страна на равенството (1) ще има член на дизюнкцията от вида $b_1^{b_1}b_2^{b_2}\ldots b_n^{b_n}=1$, от където получаваме, че самата дизюнкция ще е равна на $1$. Ако $f(b_1,b_2,\ldots b_n)=0$, във всяка конюнкция от дясната страна на равенството (1) ще има поне един множител от вида $b_k^{\overline{b_k}}=0$ поради, което можем да твърдим, че всяка конюнкция е равна на $0$. Понеже $0\lor 0\lor\ldots\lor 0=0$, то и цялата дизюнкция в дясната страна на $(1)$ ще е равна на $0$.

Теорема 2 Нека $F=\{f_1(x_1,x_2,\ldots x_{n_{1}}), f_2(x_1,x_2\ldots x_{n_{2}}),\ldots\}$ е пълно множество от двоични функции. Тогава необходимо и достатъчно условие множеството от функции $G=\{g_1(x_1,x_2,\ldots x_{m_{1}}),g_2(x_1,x_2,\ldots, x_{m_{2}}),\ldots\}$ да е пълно е всички функции $f_1, f_2,\ldots f_k,\ldots$ от $F$ да са суперпозиция над $G$.

2 Задача Да се докаже, че следните множества са пълни:

а) $A=\{{\bf .}, {\bf\overline{}}\}$; б) $B=\{{\bf\overline{}},{\bf\lor}\}$; в) $C=\{{\bf\downarrow}\}$; г) $D=\{{\bf\mid}\}$

Решение: а) Тъй като от Законите на Де Морган имаме, че $\overline{x_1\lor x_2}=\overline{x_1}.\overline{x_2}$ следва, че $x_1\lor x_2=\overline{\overline{x_1}.\overline{x_2}}$, т.е. можем да реализираме дизюнкцията чрез отрицание и конюнкция.От тук следва, че всяка фунция от пълното множество множеството $\{{\bf .},{\bf  \lor},{\bf  \overline{}}\}$  принадлежи на множеството от суперпозициите на $A$, т.е. принадлежи на $[A]$.

б) Тъй като от Законите на Де Морган имаме, че 

$x_1.x_2=\overline{\overline{x_1}\lor\overline{x_2}}$ значи можем да реализираме конюнкцията чрез отрицание и дизюнкция. От тук можем да кажем, че всяка функция от пълното множество  {{\bf .},{\bf  \lor},{\bf  \overline{}}\}$принадлежи на множеството от суперпозициите на$B$, т.е. принадлежи на$[B]$.

в) Не е трудно да съобразим, че $\overline{x_1}=x_1\downarrow x_1$. Освен това знаем, че двоичната функция стрелка на Пиърс е отрицанието на дизюнкцията. От тук следва, че $x_1\lor x_2=\overline{x_1\downarrow x_2}$. Комбинирайки двете равенства получаваме, че $x_1\lor x_2=(x_1\downarrow x_2)\downarrow (x_1\downarrow x_2)$. Така успяхме да реализираме отрицание и дицюнкция само с помощта на двоичната функция стрелка на Пиърс и според Теорема 2 и Теоремата на Бул множеството $C$ е пълно.

г) Не е трудно да се види, че $\overline{x_1}=x_1\mid x_1$. Освен това от факта, че функцията черта на Шефер е отрицанието на конюнкцията следва, че $x_1.x_2=\overline{x_1\mid x_2}$. Сега като комбинираме двете равенства получаваме, че $x_1.x_2=(x_1\mid x_2)\mid (x_1\mid x_2)$. По този начин успяхме да реализираме отрицанието и конюнкцията само с помощта на двоичната функция черта на Шефер и според Теорема 2 и Теоремата на Бул множеството $D$ е пълно.

Използвана литература:

1. Дискретна математика, Светла Бойчева, Стефка Толева-Стоименова, изд. Сиела 2018 г.

2. Увод в дискретната математика, Красимир Манев, изд. КЛМН 2012 г.

3. Въведение в дискретната математика, Христо Кискинов, Пловдивско университетско издателство