logo search
Пособие по Основам ДМ 4

4.3. Дизъюнктивные и конъюнктивные нормальные формы

Правило перехода от ДНФ к КНФ

      1. Пусть дана ДНФ F функции f.

.

Здесь – элементарные конъюнкции.

      1. Применим закон двойного отрицания: .

      2. Приведем к ДНФ .

Здесь – элементарные дизъюнкции.

      1. Возьмем второе отрицание над F. Во время преобразования не будем раскрывать скобки – остановимся на формуле, имеющей вид конъюнкции элементарных дизъюнкций – КНФ.

Замечание.

Если при приведении к ДНФ (п. 3) получить СДНФ, то в пункте 4 получится СКНФ функции F.

Правило получения СКНФ из вектор-столбца

      1. Выбрать все нулевые наборы значений аргументов.

      2. Каждому нулевому набору поставить в соответствие элементарную дизъюнкцию всех переменных так, чтобы в дизъюнкции переменная была с отрицанием, если в наборе она равна 1.

      3. Соединить полученные элементарные дизъюнкции знаком конъюнкции.