Этап. Нахождение существенных импликант

Этап. Нахождение первичных импликант

Запишем члены функции в 1-й столбец таблицы, применим к ним закон склеивания, рассматривая последовательно 1-й член со всеми остальными, затем 2-й со всеми остальными и т.д. Результаты запишем во 2-й столбец таблицы, занумеруем их и укажем в скобках номера склеенных членов, а в 1-ом столбце склеившиеся члены пометим звездочками. Повторим эту процедуру с членами 2-го столбца и т.д. Те импликанты, которые не склеиваются, обведем рамочками, они и являются простыми импликантами.

Заметим, что при склеивании импликант 2-го столбца таблицы для сравнения со взятой импликантой надо выбирать из последующих импликант только те, которые содержат буквы с соответствующими данной импликанте индексами.

	Члены	Результаты 1-го склеивания	Результаты 2-го склеивания
1.	*	(1, 4)	(3, 9)
2.	*	(1, 6)	(4, 6)
3.	*	* (2, 3)
4.	*	* (2, 7)
5.	*	(3, 4)
6.	*	* (3, 8)
7.	*	(5, 6)
8.	*	(5, 8)
9.		* (7, 8)

Если в результате склеивания получаются одинаковые импликанты, то оставляют только одну из них.

Итак, 1-й этап (“Нахождение первичных импликант”) закончен. Ими являются все импликанты, обведенные рамочками.

Этап. Расстановка меток

Составляется таблица, число строк которой равно числу найденных простых импликант, а число столбцов – числу членов СДНФ данной функции. В 1-й столбец записываются первичные импликанты, в 1-ю строку члены функции. Если в член функции входит первичная импликанта, то на пересечении их ставится метка .

У первичных импликант 3-го порядка метки удобно проставить по номерам склеенных членов 1-го столбца, приписанным у импликант рядом (в скобках), а у первичных импликант 2-го порядка по номерам членов 1-го столбца. Число меток в строке зависит от числа исключенных букв в импликанте. Для исключенных букв число меток будет .

Рассмотрим 2-й этап на примере 6. Составим таблицу.


(1)	(2)	(3)	(4)	(5)	(6)	(7)	(8)
V			V
V					V
		V	V
				V	V
				V			V
	V	V				V	V

Заметьте, член получился при склеивании членов 3 и 9, 2-го столбца, а те в свою очередь из членов 2, 3 и 7, 8 1-го столбца. Так, первичная импликанта соответствует членам 2, 3, 7, 8 данной функции. Итак, таблица меток построена.

этап. Нахождение существенных импликант

Если в каком-либо столбце составленной таблицы меток имеется только одна метка, то первичная импликанта, стоящая в соответствующей строке, является существенной. Она не может быть исключена из минимальной формы функции, т.к. без нее не может быть получено покрытие всего множества импликант данной функции. Из таблицы меток исключаются строки и столбцы, на пересечении которых стоит эта единственная метка.

В таблице меток (см. пример 6) столбцами с единственной меткой являются столбцы (2), (7). Соответствующая импликанта является существенной. Метку обводят кружочком, существенные импликанты – рамочкой, а столбцы с единственной меткой вычеркивают из таблицы. По закону поглощения меньшее количество меток в столбце может исключить большее. Так (2) и (7) столбцы входят соответственно в (3) и в (8), поэтому исключаем (3) и (8) столбцы из таблицы меток. 3-й этап закончен.

Далее ⇒