Материал из Викиконспекты
Сокращенная ДНФ
Запишем известную функцию [math]\left\lt x, y, z\right\gt [/math] (медиана) в СДНФ:
[math](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)[/math].
Известно, что это выражение равносильно следующему:
[math]((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))[/math].
Вынесем в каждой скобке общий конъюнкт (например, в первой [math](x \land y \land z) \lor (x \land y \land \lnot z)=(x \land y) \lor (z \land \lnot z))[/math].
Так как [math]z \land \lnot z = 0[/math], то такой конъюнкт не влияет на значение выражения, и его можно опустить.
Получим в итоге формулу [math](x \land y) \lor (y \land z) \lor (x \land z)[/math].
| Определение: |
Сокращенная ДНФ: форма записи функции, обладающая следующими свойствами:
- Никакие два слагаемых нельзя объединить по рассмотренному выше правилу.
- Ни один из конъюнктов не является подмножеством другого. Например, [math](x \land y)[/math] — подмножество [math](x \land y \land z)[/math].
Функцию можно записать с помощью сокращенной ДНФ не единственным способом. |
Минимальная ДНФ
| Определение: |
| Минимальная ДНФ — та сокращенная ДНФ, в которой содержится минимальное количество вхождений переменных. |
Каждая минимальная ДНФ является сокращенной, но не каждая сокращенная — минимальна.
Например, запись [math](x \land y) \lor (y \land z) \lor (x \land z)[/math] является минимальной ДНФ для медианы (она же сокращенная, как видно в примере выше); а запись [math](x \land y \land \lnot z) \lor (\neg x \land y \land z) \lor (x \land z)[/math] - не минимальная, но сокращенная ДНФ.
Минимальная ДНФ представляет функцию в наиболее удобном для работы с ней виде.
См. также
