Сокращённая и минимальная ДНФ

Сокращенная ДНФ

Запишем известную функцию <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].

Определение:

Сокращенная ДНФ: форма записи функции, обладающая следующими свойствами: 1. Никакие два слагаемых нельзя объединить по рассмотренному выше правилу. 2. Ни один из конъюнктов не является подмножеством другого (например, [math](x \and y)[/math] - подмножество [math](x \and y \and z)[/math]). Функцию можно записать с помощью сокращенной ДНФ не единственным способом.

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

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

См. также

Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно