80
правок
Изменения
Нет описания правки
== Сокращенная ДНФ ==
Запишем известную функцию ''<x,y,z>'' (медиана) в СДНФ:
<mathtex>(x \and wedge y \and wedge z) \or vee (x \and wedge y \and wedge \neg z) \or vee (x \and wedge \neg y \and wedge z) \or vee (\neg x \and wedge y \and wedge z)</mathtex>. Известно, что это выражение равносильно следующему: <mathtex>((x \and wedge y \and wedge z) \or vee (x \and wedge y \and wedge \neg z)) \or vee ((x \and wedge \neg y \and wedge z) \or vee (x \and wedge y \and wedge z)) \or vee ((\neg x \and wedge y \and wedge z) \or vee (x \and wedge y \and wedge z))</mathtex>. Вынесем в каждой скобке общий конъюнкт (например, в первой <mathtex>(x \and wedge y \and wedge z) \or vee (x \and wedge y \and wedge \neg z)=(x \and wedge y) \or vee (z \and wedge \neg z))</mathtex>. Т.к. <mathtex>z \and wedge \neg z = 0</mathtex>, то такой конъюнкт не влияет на значение выражения, и его можно опустить. Получим в итоге формулу <mathtex>(x \and wedge y) \or vee (y \and wedge z) \or vee (x \and wedge z)</mathtex>.<br><br>
{{Определение
|definition =
Сокращенная ДНФ: форма записи функции, обладающая следующими свойствами:<br>
1. Никакие два слагаемых нельзя объединить по рассмотренному выше правилу.<br>
2. Ни один из конъюнктов не является подмножеством другого (например, <mathtex>(x \and wedge y)</mathtex> - подмножество <mathtex>(x \and wedge y \and wedge z)</mathtex>).<br>
Функцию можно записать с помощью сокращенной ДНФ не единственным способом.
}}
== Минимальная ДНФ ==
{{Определение
|definition =
Минимальная ДНФ - та сокращенная ДНФ, в которой содержится минимальное количество переменных.
}}
Каждая минимальная ДНФ является сокращенной, но не каждая сокращенная - минимальна.<br>
Минимальная ДНФ представляет функцию в наиболее удобно для работы с ней виде.
