Минимизация высказываний методом Квайна
1. Выражение из произвольной формы приводится к СДНФ.
2. Выполнив в СДНФ все возможные неполные склеивания, а затем все возможные поглощения мы получим Сокращенную ДНФ (СкДНФ). Конъюнкции в СкДНФ называются импликантами.
 |
Примечание: Склеивание: X×Y Ú X×Y ≡ X
Неполное склеивание: X×Y Ú X×Y ≡ X Ú X×Y Ú X×Y
3. На основании СкДНФ и СДНФ строим импликантную матрицу и путем нахождения минимального покрытия этой матрицы получаем минимальную дизъюнктивную нормальную форму (МДНФ).
Пример 1:
| |||||
 |  | ||||
f = X×Y×Z Ú X×Y×Z Ú X×Y×Z Ú X×Y×Z Ú X×Y×Z
(I) (II) (III) (IV) (V)
I-II : X×Y (VI)
I-III : Y×Z (VII)
I-V : X×Z (VIII )
III-IV : X×Z (IX)
IV-V : Y×Z (X)
VII-X : Z
VIII-IX:Z
Импликантная матрица.
| _ _ _ X×Y×Z | _ _ X×Y×Z | _ _ X×Y×Z | _ X×Y×Z | _ _ X×Y×Z | |
| _ _ X×Y | + | + | |||
| _ Z | + | + | + | + |
СкДНФ(f) = X×Y Ú Z = МДНФ.
Пример 2:
 | |  | |  |  | ||||||||||||
|  | | |||||||||||||||
X×Y×ZÚX×Y×ZÚX×Y×ZÚX×Y×ZÚX×Y×ZÚX×Y×Z
1 2 3 4 5 6
 | |||||||||||
| | | | ||||||||
| |||||||||||
1-2 : X×Y СкДНФ = ХYÚY×ZÚX×ZÚY×Z×ÚX×ZÚX×Y
1-4 : Y×Z
2-3 : X×Z
3-6 : Y×Z
4-5 : X×Z
5-6 : X×Y
Импликантная матрица.
| X×Y×Z | _ X×Y×Z | _ _ X×Y×Z | _ X×Y×Z | _ _ X×Y×Z | _ _ _ X×Y×Z | |
| X×Y | * + | * + | ||||
| Y×Z | # + | # + | ||||
| _ X×Z | # + | # + | ||||
| _ _ Y×Z | * + | * + | ||||
| _ X×Z | * + | * + | ||||
| _ _ X×Y | # + | # + |
МДНФ1 = X×Y Ú Y×Z Ú X×Z
МДНФ2 = Y×Z Ú X×Y Ú X×Z