Материал: Дискретная математика. учебное пособие. Горбунов В.В., Лапшина М.Л
Таблица 27.
х |
у |
z |
х л у |
x v z |
(х л y) v (у л z) |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Получаем F1 = 00000111 и F2 = 00000111. Значит, функции эквивалентны.
Задача 4. Используя СДНФ, найдите булеву функцию, принимающую значение 1 на следующих наборах переменных, и только на них: f(0,1,0) = f (1,0,1) = f (1,1,1) = 1.
Решение. Алгоритм построения СДНФ.
1. Наборам 010; 101; 111 соответствуют
конъюнкции:
л
л
;
л
л
;
л
л
.
Напомним, что для каждого набора из
нулей и единиц τ1, τ2, τ3
выписываем
конъюнкцию
л
л
, причем, если
τ1= 1,
то соответствующая переменная хi
входит в конъюнкцию без отрицания.
2. Составим дизъюнкцию полученных конъюнкций, т. е. составляем СДНФ функции:
Задача
5. Составьте СКНФ функции
.
Решение.
Таблица 28.
x1 |
х2 |
x1 х2 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
Выпишем f(0,0) = 0; f (1,1) = 0, булева функция принимает значение 0 на наборах (0; 0) и (1; 1).
Составим дизъюнкции, соответствующие этим наборам:
л
и
л
(если
=
0, то переменная входит в дизъюнкцию
без отрицания, если
=
1, то переменная в дизъюнкции берется
с отрицанием).
3. Составим конъюнкцию полученных дизъюнкций, т. е. составляем СКНФ функции f(х1, х2,) = ( v )л( л ).
Задача 6. Найдите СДНФ и СКНФ функции
,
заданной следующей таблицей истинности:
Таблица 29.
|
|
|
|
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
Решение. По теореме о функциональной полноте СДНФ имеет вид:
;
СКНФ имеет вид:
.
Описанный способ нахождения СДНФ и СКНФ по таблице истинности бывает часто более трудоемким. Для нахождения СДНФ данную формулу приводим сначала к ДНФ, а затем преобразовываем ее конъюнкции с помощью следующих действий:
а) если в конъюнкцию входит некоторая переменная со своим отрицанием, то мы удаляем эту конъюнкцию из ДНФ;
б) если в конъюнкцию одна и та же переменная входит несколько раз, то все они удаляются, кроме одной;
в) если в конъюнкцию не входят некоторые
переменные, то для каждой из них к
конъюнкции добавляется соответствующая
формула вида
;
г) если в полученной ДНФ имеется несколько одинаковых конъюнкций, то оставляем только одну из них.
В результате получается СДНФ.
Задача 7. Найдите СДНФ для ДНФ
.
Решение.
1. Удаляем конъюнкцию
,
так как здесь переменная вместе со своим
отрицанием. Остается
.
2. Из конъюнкции
удаляем
переменную у, так как она входит
сюда два раза. Остается
.
3. В первой конъюнкции нет переменной
у, поэтому к ней добавляется формула
,
а во второй конъюнкции нет переменной
х, поэтому к ней добавляется формула
.
Получаем:
.
4. Используем дистрибутивные законы:
.
5. К первой и второй конъюнкциям добавляем
и получаем:
.
6. Используем дистрибутивные законы:
.
7. В полученной
формуле имеется две одинаковые конъюнкции:
.
Удалив одну из них, получим:
В
итоге мы получили соответствующую СДНФ.
Задача 8. Найдите СКНФ для КНФ
.
Решение. Опишем алгоритм приведения КНФ к СКНФ аналогично вышеизложенному приведению ДНФ к СДНФ.
1. Во второй
дизъюнкции не хватает переменной у,
поэтому в дизъюнкцию добавим
и, используя дистрибутивные законы,
получаем:
.
2. В третью дизъюнкцию добавим
и получим две дизъюнкции:
.
Добавив в каждую из них
,
получим:
.
3. Соберем в конъюнкцию все дизъюнкции:
.
4. Избавляемся от одинаковых дизъюнкций, оставляя только одну. В результате получается СКНФ:
