20
правок
Изменения
Нет описания правки
== Сокращенная ДНФ ==
{{Определение
|definition =
Сокращенная ДНФ: форма записи функции, обладающая следующими свойствами:
}}
Функцию можно записать с помощью сокращенной ДНФ не единственным способом.
Запишем [[Определение булевой функции|функцию]] <tex>\left<x, y, z\right> </tex> (медиана) в виде [[СДНФ|совершенной ДНФ]]:
<tex>(x \land y \land z) \lor (x \land y \land \lnot z) \lor (x \land \lnot y \land z) \lor (\neg x \land y \land z)</tex>.
Известно, что это выражение равносильно следующему:
<tex>((x \land y \land z) \lor (x \land y \land \lnot z)) \lor ((x \land \lnot y \land z) \lor (x \land y \land z)) \lor ((\neg x \land y \land z) \lor (x \land y \land z))</tex>.
Вынесем в каждой скобке общий конъюнкт (например, в первой <tex>(x \land y \land z) \lor (x \land y \land \lnot z)=(x \land y) \lor (z \land \lnot z)</tex>.
Так как <tex>z \land \lnot z = 0</tex>, то такой конъюнкт не влияет на значение выражения, и его можно опустить.
Получим в итоге формулу <tex>(x \land y) \lor (y \land z) \lor (x \land z)</tex>.
== Минимальная ДНФ ==
{{Определение
