2015-09-06
905
Определение 1. Элементарной конъюнкцией или конъюнктом называется выражение, состоящее из конечного числа переменных и их отрицаний, взятых в этом выражении не более одного раза и разделенных операцией конъюнкции.
Определение 2. Элементарной дизъюнкцией или дизъюнктом называется выражение, состоящее из конечного числа переменных и их отрицаний, взятых в этом выражении не более одного раза и разделенных операцией дизъюнкции.
Определение 3. Дизъюнкция конъюнктов называется дизъюнктивной нормальной формой (ДНФ); конъюнкция дизъюнктов называется конъюнктивной нормальной формой (КНФ).
Для приведения формулы, представляющей булеву функцию, к ДНФ выполняется следующий алгоритм:
1. Выражаем все логические операции, участвующие в построении формулы, через дизъюнкции, конъюнкции и отрицания.
2. Используя законы де Моргана, переносим все отрицания к переменным.
3. Сокращаем двойные отрицания.
4. Используя закон дистрибутивности преобразуем формулу так, чтобы все конъюнкции выполнялись раньше дизъюнкций.
|
|
|
Приведение формулы к КНФ производится аналогично приведению ее к ДНФ, только в п. 4, используя закон дистрибутивности, преобразуем формулу так, чтобы все дизъюнкции выполнялись раньше, чем конъюнкции.
Пример.
Дана функция f(x, y, z) = (x ® y) ¯ 
. С помощью эквивалентных преобразований привести формулы к ДНФ и КНФ; выполнить проверку с использованием таблиц истинности.
В примере п. 4.2(стр. 73) в результате эквивалентных преобразований функции f(x, y, z) = (x ® y) ¯ получили f(x, y, z) = 
.
Используем свойство дистрибутивности для преобразования формулы:
= 
= 
.
Получили ДНФ.
Используем ассоциативный закон и поглощение для преобразования формулы:
= 
.
Получили КНФ.
Выполним проверку таблицами истинности.
| x | y | z | 
| 
| 
| 
|
Из таблицы видно, что решение верно. (Смотри таблицу истинности для функции f(x, y, z) = (x ® y) ¯ п. 4.1 стр.68)
