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