Специальная математика (стр. 8 )

 

Примечание: Склеивание: 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

2.1.7. Минимизация с помощью карт Вейча

Смысл минимизации состоит в том, что специальным образом размечаются карты, где каждая клеточка – возможная комбинация значений аргументов. В эту карту заносятся единицы, соответсвующие конституентам единицы минимизируемой функции. А затем выделяются максимальные правильные подкубы, что соответсвует операциям склеивания и поглощения.

Примеры.

Пусть дана СДНФ импликации: XY Ú XY Ú XY

 

Y Y

1	1
X	1

МДНФ для импликации, в соответствии с двумя выделенными подкубами, будет:

X Ú Y

Для СДНФ XYZ Ú XYZ Ú XYZ Ú XYZ Ú XYZ

X X

Y _ Y     1	1	1
1		1	1