A) элементтері болса 12 страница

При описании второго этапа будет использоваться термин «покрытие минтермов». Он означает следующее. Пусть, например, минтерм третьего ранга разлагается (операция обратная склеиванию) на два минтерма четвёртого ранга.

Говорят, что минтерм покрывает минтермы и . Точно так же минтерм первого ранга

покрывает минтермы третьего ранга правой части приведённого равенства. Следовательно, «покрывать» означает возможность «осуществлять замену» или «замещать».

Второй этап начинается с выяснения доли участия каждой из первичных импликант в покрытии исходных минтермов. Сначала определяются существенные импликанты, без которых исходные минтермы не были бы покрыты. Затем, анализируются остальные импликанты и, из них, выбирается тот минимальный состав, который завершает покрытие оставшейся части исходных минтермов.

Реализация первого и второго этапов рассматриваемого метода имеет определённый порядок действий и несколько рекомендаций по их оформлению. Продемонстрируем это на примере.

Пусть задана логическая функция в СДНФ с минтермами четвёртого ранга.

Требуется найти её минимальную тупиковую форму.

Введём вспомогательную систему кодирования минтермов. Минтермы заданной функции нумеруются, а номера этих минтермов будем считать их кодами. При склеивании двух исходных минтермов, результату склеивания (минтерму третьего ранга) присваивается код, составленный из кодов склеиваемых минтермов. Например,

Точно также происходит образование кода результата при склеивании минтермов третьего ранга.

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

Состоит в последовательном склеивании минтермов. Оно производится в следующем порядке. Сначала проверяется возможность склеивания первого по списку минтерма четвёртого ранга со всеми остальными

Таблица 2.5.1
Код	Минтермы	Метки
[1]		*
[2]			*
[3]				*
[4]		*			*
[5]			*		*
[6]		*		*		*
[7]				*			*
[8]			*			*	*

Таблица 2.5.2
Код	Минтермы	Метки
[1,4]
[1,6]
[2,5]
[2,8]
[3,6]		*
[3,7]
		*
[4,5]
[6,8]			*
[7,8]		*

минтермами этого же ранга. В тех случаях, когда появляется такая возможность, производится склеивание. Затем, проверяется возможность склеивания второго по списку минтерма со всеми остальными, исключая первый. В положительных случаях также производится склеивание. Затем, третьего минтерма со всеми остальными, исключая первый и второй. Подобную процедуру нужно повторять до тех пор, пока имеется возможность склеивания. Результаты такого многошагового склеивания заносятся в таблицу. В ней склеиваемые минтермы отмечаются метками « * » (табл. 2.5.1). Расстановка меток, например, в первом столбце таблицы с шапкой «метки» означает: первый минтерм склеивается со вторым и первый минтерм склеивается с седьмым. При приобретении некоторого опыта в использовании рассматриваемого метода минимизации функций расстановку меток можно не делать.

По результатам

склеиваний, отмеченным в таблице 2.5.1, строится таблица 2.5.2. В ней отображается итог точно такой же процедуры для минтермов третьего ранга. Результаты выполненных склеиваний в виде минтермов второго ранга занесены в таблицу 2.5.3. Минтермы получились одинаковыми и,

Таблица 2.5.3
Код	Минтермы
[3,6,7,8]
[3,7,6,8]

в силу аксиомы 4 (п. 2.1), один из них вычёркивается.

Все неотмеченные минтермы в таблицах 2.5.1, 2.5.2 и 2.5.3, как сказано выше, называются первичными импликантами. Их логическая сумма является тупиковой формой минимизируемой функции.

Эта форма есть результат выполнения первого этапа, рассматриваемого метода минимизации логической функции.

Второй этап. Нахождение минимальной тупиковой формы функции.

Производится анализ особенностей покрытия исходных минтермов первичными импликантами. Чтобы иметь наглядное представление о покрытиях, строится таблица. Её называют таблицей покрытий. В этой таблице символом «.» отмечается факт покрытия каждого исходного минтерма определённой первичной импликантой. Для тех первичных импликант, которые, в конечном итоге, будут оставлены в минимальной тупиковой форме, символ «.» обводится кружочком. Для рассматриваемого примера это таблица 2.5.4.

Среди первичных импликант могут быть существенные импликанты. Отличительная особенность существенной импликанты состоит в том, что она, и только она, покрывает хотя бы один исходный минтерм. То есть, без неё требование полного покрытия исходных минтермов неосуществимо. Существенная импликанта обязательно должна включаться в искомую минимальную тупиковую форму функции. Поэтому, для облегчения дальнейшего выбора составляющих тупиковой минимальной формы функции, перестроим таблицу 2.5.4, исключив из неё все столбцы и строчку, касающиеся существенной импликанты (таблица 2.5.5).