дискр мат / Минимизация_булевых_функций
.doc
Минимизация булевых функций
Дизъюнктивная и конъюнктивная нормальные формы
Определение
Если х – логическая
переменная и
,
то выражение
называется литерой.
Определение
Элементарной конъюнкцией или конъюнктом называется конъюнкция литер.
Элементарной дизъюнкцией или дизъюнктом называется дизъюнкция литер.
Пример
и
- элементарные конъюнкции
и
- элементарные дизъюнкции
- одновременно и
то и другое.
Определение
Дизъюнкция конъюнктов называется дизъюнктивной нормальной формой (ДНФ).
Конъюнкция дизъюнктов называется конъюнктивной нормальной формой (КНФ).
Пример
- ДНФ
- КНФ
- одновременно и
ДНФ и КНФ
Теорема
Любая формула эквивалентна некоторой ДНФ.
Любая формула эквивалентна некоторой КНФ.
Опишем алгоритм приведения формулы к ДНФ и КНФ, который и доказывает теорему.
Приведение формулы к ДНФ:
-
выражаем все логические операции, входящие в формулу через дизъюнкцию, конъюнкцию и отрицание, используя следующие эквивалентности:
\
;
-
используя законы Моргана, переносим все отрицания к переменным и сокращаем двойное отрицание;
-
используя законы дистрибутивности, преобразуем формулу так, чтобы все конъюнкции были раньше дизъюнкций.
Пример
выразим операции
и
через конъюнкцию и дизъюнкцию
=
=
перенесем двойные отрицания к формулам и сократим их
=
=
используя закон дистрибутивности приводим формулу к ДНФ=
=
.
Приведение формулы к КНФ производится аналогично, только применяем закон дистрибутивности так, чтобы все дизъюнкции выполнялись раньше, чем конъюнкции.
Пример
выразим операции
и
через конъюнкцию и дизъюнкцию
=
=
перенесем двойные отрицания к формулам и сократим их
=
=
используя закон дистрибутивности приводим формулу к КНФ=
=
.