Тождества, связывающие булевы функции

x’ =x0 =x|x=xx= 1x; (1)

xy= (x’y’)’ =x’y’ = (xx)(yy); (2)

xy= (x’y’)’ =x’y= =(xy)y=x’|y’ = (x|x)|(y|y); (3)

xy=x’y; (4)

xy= (xy) (yx) =xyx’y’; (5)

xy=xy’x’y. (6)

Примеры

1. Доказать, что:

а) (xy)’ =x’y’(закон де Моргана); б)x’y’ =xy.

Решение. Построим таблицы значений:

x y x’ y’ xyа)(xy)’ x’y’б)xy x’y’

0 0 1 1 0 1 1 0 0

0 1 1 0 1 0 0 0 0

1 0 0 1 1 0 0 0 0

1 1 0 0 1 0 0 1 1

Равенства последних столбцов (правая и левая части соответствующих уравнений) и доказывают истинность.

2. Доказать, что (xy’)(yx’) =x’y.

Решение.СпособI. Строим таблицы значений:

x y x’ y’ xy’ yx’ (xy’)(yx’) x’y

0 0 1 1 0 1 0 0

0 1 1 0 0 0 1 1

1 0 0 1 1 0 0 0

1 1 0 0 0 1 0 0

Способ II. Упростим левую часть, используя свойства функций: (xy’)(yx’) =|избавимся от, используяxy= x’y’согласно (2)| = (xy’)’(yx’)’=|применим закон де Моргана для первого сомножителя и тождество (6) для второго| = (x’y)(yx’’y’x’)’=|несколько раз применим з-н де Моргана для второго сомножителя, предварительно заменивx’’ =x| =(x’y)((yx)’(y’x’)’)=(x’y)(y’x’)(yx)=| перемножим две последние скобки|=(x’y)(yy’yx’xy’xx’)=|учитывая, чтоyy’= xx’=0, опустим данные слагаемые и раскроем оставшиеся скобки| =(x’y)( yx’xy’)=yx’x’yyx’xx’yyxy’= yx’yx’00= yx’.

3. Установить, дистрибутивно ли сложениеотносительно умножения.

Решение. Закон дистрибутивности означает, что справедливо тождество: (xy)z=xzyz(по умолчанию умножение выполняется первым). Упростим левую и правую части уравнения:

1) (xy)z=(x’yxy’)z=x’yzxy’z;

2) xzyz=((xz)’yz)(xz(yz)’)=((x’z’)yz)(xz(y’z’))=

=x’yzz’yzxzy’xzz’= x’yzxzy’.

Сравнивая результаты упрощений, приходим к выводу о выполнении дистрибутивного свойства.

4. Установить, ассоциативна ли стрелка Пирса.

Решение. Ассоциативность стрелки Пирса означала бы справедливость равенства (xy)z =x(yz). Проверим тождественную истинность табличным способом:

x y z xy yz (xy)z x(yz)

0 0 0 1 1 0 0

0 0 1 1 0 0 1

0 1 0 0 0 1

0 1 1 0 0 0

1 0 0 0 1 1

1 0 1 0 0 0

1 1 0 0 0 1

1 1 1 0 0 0

Далее продолжать подсчет последнего столбца не требуется. Стрелка Пирса не ассоциативна.

Вопросы и упражнения для самостоятельной работы

Доказать тождества (1)–(6).

Для приведенных ниже функций установить, выполняются ли законы коммутативности и ассоциативности:

а) x|y; б)xy; в) x→y; г)xy; д)xy.

Проверить свойство дистрибутивности:

а) (xy)z=(xz)(yz); б) (x→y)z=(xz)→(yz);

в) (xy)z=(xz)(yz); г) (x|y)z=(xz)|(yz).

§1.2. Нормальные формы булевых функций

Теорема. Пусть f(x₁,x₂,…,x_n) –произвольная булева функция. Тогда

f(x₁,x₂,…,x_n) =x₁f(1,x₂,…,x_n)x₁’f(0,x₂,…,x_n);

f(x₁,x₂,…,x_n) = (x₁f(0,x₂,…,x_n))(x₁’f(1,x₂,…,x_n)).

Последовательно применяя данное разложение по переменным x₁,x₂,…,x_n, можно получить формулу, содержащую лишь дизъюнкции, конъюнкции и отрицания. Например,

f(x,y) =f(1,1)xyf(1,0)xy’f(0,1)x’yf(0,0)x’y’, (7)

f(x,y) = (f(1,1)x’y’)( f(1,0)x’y)(f(0,1)xy’)(f(0,0)xy). (8)

Разложение вида (7) называют совершенной дизъюнктивной нормальной формой (СДНФ), а разложение вида (8) —совершенной конъюнктивной нормальной формой (СКНФ). Нетрудно видеть, что в СДНФ (7) можно отбросить те слагаемые, для которыхf(a,b)=0, а в СКНФ (8) — сомножители, гдеf(a,b)=1.

Элементарной конъюнкцией(конъюнктом) называют конъюнкцию переменных, быть может с их отрицаниями, в которой каждая переменная встречается не более одного раза.

Дизъюнкцию конечного числа конъюнктов называют дизъюнктивной нормальной формой (ДНФ). Таким образом, разложение (7) представляет собой ДНФ. Отличие СДНФ от ДНФ заключается в том, что в совершенной форме каждое слагаемое (конъюнкт) содержит все переменные и/или их отрицания.

Аналогичные определения со взаимной заменой дизъюнкций на конъюнкции приводят к понятиям: элементарная дизъюнкция(дизъюнкт) иконъюнктивная нормальная форма (КНФ).

Принцип двойственности имеет место и для булевых функций. Двойственнойк булевой функцииf(x,y,…,z) называется функция

f ^*(x,y,…,z)=f ’(x’,y’,…,z’).

Теорема. Если f(x,y,…,z)представлена формулой, содержащей лишьдизъюнкции, конъюнкции и отрицания, то двойственная функция f ^*(x,y,…,z)получается заменой в исходной формуле дизъюнкций на конъюнкции, а конъюнкций на дизъюнкции.