Лекция: Минимизация высказываний методом Квайна
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