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

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

.

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

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

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

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

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

Замечание.

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