Минимизация высказываний методом Квайна

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					# +	# +

МДНФ₁ = X×Y Ú Y×Z Ú X×Z

МДНФ₂ = Y×Z Ú X×Y Ú X×Z