- •Оглавление
- •Тождества, связывающие булевы функции
- •Примеры
- •Вопросы и упражнения для самостоятельной работы
- •§1.2. Нормальные формы булевых функций
- •Примеры
- •Вопросы и упражнения для самостоятельной работы
- •§1.3. Важнейшие замкнутые классы булевых функций
- •Примеры
- •Вопросы и упражнения для самостоятельной работы
- •§1.4. Полные системы. Теорема Поста
- •Примеры
- •Вопросы и упражнения для самостоятельной работы
Тождества, связывающие булевы функции
x’ =x0 =x|x=xx= 1x; (1)
xy= (x’y’)’ =x’y’ = (xx)(yy); (2)
xy= (x’y’)’ =x’y= =(xy)y=x’|y’ = (x|x)|(y|y); (3)
xy=x’y; (4)
xy= (xy) (yx) =xyx’y’; (5)
xy=xy’x’y. (6)
Примеры
1. Доказать, что:
а) (xy)’ =x’y’(закон де Моргана); б)x’y’ =xy.
Решение. Построим таблицы значений:
x y x’ y’ xyа)(xy)’ 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’)(yx’) =x’y.
Решение.СпособI. Строим таблицы значений:
x y x’ y’ xy’ yx’ (xy’)(yx’) 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’)(yx’) =|избавимся от, используяxy= x’y’согласно (2)| = (xy’)’(yx’)’=|применим закон де Моргана для первого сомножителя и тождество (6) для второго| = (x’y)(yx’’y’x’)’=|несколько раз применим з-н де Моргана для второго сомножителя, предварительно заменивx’’ =x| =(x’y)((yx)’(y’x’)’)=(x’y)(y’x’)(yx)=| перемножим две последние скобки|=(x’y)(yy’yx’xy’xx’)=|учитывая, чтоyy’= xx’=0, опустим данные слагаемые и раскроем оставшиеся скобки| =(x’y)( yx’xy’)=yx’x’yyx’xx’yyxy’= yx’yx’00= yx’.
3. Установить, дистрибутивно ли сложениеотносительно умножения.
Решение. Закон дистрибутивности означает, что справедливо тождество: (xy)z=xzyz(по умолчанию умножение выполняется первым). Упростим левую и правую части уравнения:
1) (xy)z=(x’yxy’)z=x’yzxy’z;
2) xzyz=((xz)’yz)(xz(yz)’)=((x’z’)yz)(xz(y’z’))=
=x’yzz’yzxzy’xzz’= x’yzxzy’.
Сравнивая результаты упрощений, приходим к выводу о выполнении дистрибутивного свойства.
4. Установить, ассоциативна ли стрелка Пирса.
Решение. Ассоциативность стрелки Пирса означала бы справедливость равенства (xy)z =x(yz). Проверим тождественную истинность табличным способом:
x y z xy yz (xy)z x(yz)
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; б)xy; в) x→y; г)xy; д)xy.
Проверить свойство дистрибутивности:
а) (xy)z=(xz)(yz); б) (x→y)z=(xz)→(yz);
в) (xy)z=(xz)(yz); г) (x|y)z=(xz)|(yz).
§1.2. Нормальные формы булевых функций
Теорема. Пусть f(x1,x2,…,xn) –произвольная булева функция. Тогда
f(x1,x2,…,xn) =x1f(1,x2,…,xn)x1’f(0,x2,…,xn);
f(x1,x2,…,xn) = (x1f(0,x2,…,xn))(x1’f(1,x2,…,xn)).
Последовательно применяя данное разложение по переменным x1,x2,…,xn, можно получить формулу, содержащую лишь дизъюнкции, конъюнкции и отрицания. Например,
f(x,y) =f(1,1)xyf(1,0)xy’f(0,1)x’yf(0,0)x’y’, (7)
f(x,y) = (f(1,1)x’y’)( f(1,0)x’y)(f(0,1)xy’)(f(0,0)xy). (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)получается заменой в исходной формуле дизъюнкций на конъюнкции, а конъюнкций на дизъюнкции.