1302
правки
Изменения
м
→Сокращенная ДНФ: # + <x,y,z>
== Сокращенная ДНФ ==
Запишем известную [[Определение булевой функции|функцию]] ''<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>.<br><br>
{{Определение
#Никакие два слагаемых нельзя объединить по рассмотренному выше правилу.
#Ни один из конъюнктов не является подмножеством другого (например. Например, <tex>(x \land y)</tex> - — подмножество <tex>(x \land y \land z)</tex>).
Функцию можно записать с помощью сокращенной ДНФ не единственным способом.
