54
правки
Изменения
КНФ
,→КНФ
КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу: <tex>a (b\lor c)\to a b\lor a c</tex>, которое выражает дистрибутивность конъюнкции относительно дизъюнкции. После этого необходимо в каждой конъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из дизъюнкции все конъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом результатом не обязательно будет СДНФ, даже если исходная КНФ была СКНФ. Точно также можно всегда перейти от ДНФ к КНФ. Для этого следует использовать правило <tex>a\lor b c\to (a \lor b)(a \lor c)</tex>, выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.
Например КНФ <tex>\to</tex> ДНФ: <tex>(x \lor y) \land (y \lor \overline{z}) = (x \land y) \lor y \lor (x \land \overline{z}) \lor (y \land \overline{z}) = y \land (x \lor 1 \lor \overline{z}) \lor (x \land \overline{z}) = (x \land \overline{z}) \lor y</tex>
Например ДНФ <tex>\to</tex> КНФ: <tex> (x \land \overline{z}) \lor y = (x \lor y) \land (y \lor \overline{z}) </tex>
== СКНФ ==
{{Определение
