Изменения

Запишем известную функцию ''<x,y,z>'' (медиана) в СДНФ:

<math>(x \and y \and z) \or (x \and y \and \neg z) \or (x \and \neg y \and z) \or (\neg x \and y \and z)</math>. Известно, что это выражение равносильно следующему: <math>((x \and y \and z) \or (x \and y \and \neg z)) \or ((x \and \neg y \and z) \or (x \and y \and z)) \or ((\neg x \and y \and z) \or (x \and y \and z))</math>. Вынесем в каждой скобке общий конъюнкт (например, в первой <math>(x \and y \and z) \or (x \and y \and \neg z)=(x \and y) \or (z \and \neg z))</math>. Т.к. <math>z \and \neg z = 0</math>, то такой конъюнкт не влияет на значение выражения, и его можно опустить. Получим в итоге формулу <math>(x \and y) \or (y \and z) \or (x \and z)</math>.<br><br>

Сокращенная ДНФ: форма записи функции, обладающая следующими свойствами:<br>

1. Никакие два слагаемых нельзя объединить по рассмотренному выше правилу.<br>

2. Ни один из конъюнктов не является подмножеством другого (например, <math>(x \and y)</math> - подмножество <math>(x \and y \and z)</math>).<br>

Функцию можно записать с помощью сокращенной ДНФ не единственным способом.

== Минимальная ДНФ ==

Минимальная ДНФ - та сокращенная ДНФ, в которой содержится минимальное количество переменных.