Расстановка меток. Остальные этапы
нужны, чтобы отбросить некоторые первичные импликанты. На данном этапе составляется
таблица, число строк которой равно числу полученных первичных импликант, число
столбцов совпадает с числом минитермов СДНФ. Если в некоторый минитерм СДНФ
входит какая – либо из первичных импликант, то на пересечении соответствующего
столбца и строки ставится метка. В таблице 2.2.2 приведем результат расстановки
меток:
Таблица 2.2.2
0000
0100
1100
1010
0011
1110
1011
0
1
2
3
4
5
6
7
1
0-00
У
У
2
-100
У
У
3
-011
У
У
4
11-0
У
У
5
1-10
У
У
6
101-
У
У
Нахождение существенных импликант.
Если в каком – либо из столбцов таблицы меток стоит только одна метка, то
первичная импликанта, стоящая в соответствующей строке, называется существенной
импликантой. Все существенные импликанты запоминаются. А из таблицы меток исключаются
строки, соответствующие существенным импликантам, и столбцы минитермов
«покрываемых» этими существенными импликантами.
Существенными являются импликанты
0-00 и -011. Поэтому вычеркиваем 1-ю и 3-ю строки и столбцы: 1, 5, 2, 7.
Составим сокращенную таблицу меток:
Таблица 2.2.3
1100
1010
1110
-100
У
11-0
У
У
1-10
У
У
101-
У
Выбор минимального покрытия.
Исследуется результирующая таблица. Выбирается такая совокупность первичных
импликант, которая иссключает метки во всех столбцах (по крайней мере по одной
в каждом столбце). При нескольких возможных вариантах такого выбора отдается
предпочтение варианту покрытия с минимальным суммарным числом букв в простых
импликантах, образующих покрытие.
С учетом существенных импликант
получим две МДНФ для этой функции имеет вид:
1.
2.
Число букв составляющих простые
импликации в каждом варианте одинаково. Во втором варианте на одно отрицание
меньше, поэтому берем его за искомое: