20
правок
Изменения
Нет описания правки
}}
Каждая минимальная ДНФ является сокращенной, но не каждая сокращенная {{---}} минимальна.
Например, запись <tex>(x \land y) \lor (y \land z) \lor (x \land z)</tex> является минимальной ДНФ для медианы (она же сокращенная, как видно в примере выше); а запись <tex>(x \land y \land \lnot z) \lor (\neg x \land y \land z) \lor (x \land z)</tex> {{- --}} не минимальная, но сокращенная ДНФ.<br>
== Минимизация ДНФ ==
=== Карты Карно ===
Построим следующую таблицу <tex>n \cdot times n</tex>, где <tex>n</tex> {{---}} количество переменных:
{| border="1"
|
**подмножество элементарных конъюнкций длины <tex>n</tex> (оставшиеся)
**подмножество элементарных конъюнкций длины <tex>n-1</tex>
*Если множество элементарных конъюнкций длины <tex>n-1</tex> не пусто, то заново выполняются операции неполного попарного склеивания и элементарного поглощения для конъюнкций длины <tex>n-1</tex> и т.дтак далее.
Алгоритм завершается, когда подмножество является пустым, либо нельзя выполнить ни одной операции неполного попарного склеивания.
После выполнения алгоритма будет получена сокращенная минимальная форма.
