Изменения

Перейти к: навигация, поиск

ДНФ

1756 байт убрано, 06:06, 21 декабря 2011
Нет описания правки
Пример ДНФ:
<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>, выражающее дистрибутивность конъюнкции относительно дизъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «дизъюнкция» на «конъюнкция» и наоборот.
 
Например ДНФ <tex>\to</tex> КНФ: <tex> (x \land \overline{z}) \lor y = (x \lor y) \land (y \lor \overline{z}) </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>
== СДНФ ==
|+
|-align="center" bgcolor=#EEEEFF
| x || y || z || <tex>med(\langle x,y,z)\rangle </tex>
|-align="center" bgcolor=#F0F0F0
| 0 || 0 || 0 || 0
|+
|-align="center" bgcolor=#EEEEFF
| x || y || z || <tex>med(\langle x,y,z)\rangle </tex> ||
|-align="center" bgcolor=#F0F0F0
| 0 || 0 || 0 || 0 ||
3. Все полученные конъюнкции связываем операциями дизъюнкции.
<tex>med(\langle x,y,z) \rangle = (x \land y \land z) \lor (\overline{x} \land y \land z) \lor (x \land \overline{y} \land z) \lor (x \land y \land \overline{z})</tex>
==Примеры СДНФ для некоторых функций==
54
правки

Навигация