Тупиковой днф называется дизъюнкция всех импликант, составляющих приведенную систему.
Тупиковая ДНФ- выражение, полученное из сокращенной ДНФ, дальнейшее упрощение которого невозможно в рамках ДНФ.
Минимальной ДНФ называется тупиковая ДНФ, состоящая из наименьшего числа букв.
Одна и та же сокращенная ДНФ может иметь несколько тупиковых ДНФ и несколько минимальных ДНФ.
Процесс минимизации на первом этапе сводится к построению полной системы импликант, затем приведенной системы существенных импликант, из которых строится сокращенная ДНФ, затем строятся тупиковые ДНФ и затем уже выбирается минимальная ДНФ. Решение задачи осуществляется в соответствии со схемой
Получение сокращенной ДНФ (нахождение импликантов функции ).
Пример 1.
Получение сокращенной ДНФ основывается на законе склеивания . Из него следует, что можно склеивать или объединять минтермы, отличающиеся только одним сомножителем. Будем склеивать не минтермы, а наборы. Выпишем все наборы переменных, соответствующие минтермам, входящим в разложение функции, в столбик, разбивая их на группы так, чтобы в каждую группу входили наборы с одинаковым числом единиц.
N Груп пы |
Наборы |
набора |
|
|
|
|
|
1 |
0010 * |
2 * |
2,3 |
001– * |
|
2,3, .10,11 |
–01– |
|
|
|
2,10 |
–010 * |
|
2,10, 3,11 |
–01– |
2 |
0011 * |
3 * |
3,11 |
–011 * |
|
|
|
|
1001 * |
()9 * |
9,11 |
10–1 |
|
|
|
|
1010 * |
10 * |
9,13 |
1–01 |
|
|
|
|
1100 * |
()12 * |
10,11 |
101– * |
|
|
|
|
|
|
10,14 |
1–10 |
|
|
|
|
|
|
12,13 |
110– |
|
|
|
|
|
|
12,14 |
11–0 |
|
|
|
3 |
1011 * |
()11 * |
|
|
|
|
|
|
1101 * |
() 13 * |
|
|
|
|
|
|
1110 * |
14 * |
|
|
|
|
|
|
|
|
|
|
|
|
|
Импликантами функции будут наборы во всех столбцах, не участвующие в склеивании (не помеченные).
, , , , , .
Сокращенная ДНФ , ее длина составляет 17 букв
На рис. изображены импликанты и склеиваемые наборы переменных.
Отметим, что на рисунке номера наборов приведены в восьмеричной системе счисления.
2. Следующий этап – построение тупиковой ДНФ. Для этого нужно составить импликантную таблицу. Строки этой таблицы обозначены импликантами функции, а столбцы минтермами функции. Каждая импликанта является частью какого-нибудь дизъюнктивного члена в СДНФ и обращается в единицу на том же наборе, что и соответствующий минтерм. На пересечении строки, в которой записана импликанта, и столбцов соответствующих минтермов, частью которых является импликанта, поставим крестики. Тупиковые формы являются дизъюнкциями тех импликантов, которые накрывают все минтермы, т.е. в таблице нужно выбрать такие строки, чтобы во всех столбцах был как минимум один плюс.
Чтобы построить тупиковую форму, нужно выбрать минимальное число строк, покрывающих крестиками все столбцы. Ясно, что в систему выбранных строк должны обязательно входить строки, содержащие плюсы, которые являются единственными в столбце. Такие строки называются базисными. Простые импликанты, стоящие в базисных строках, образуют ядро рассматриваемой функции. Обведем кружочками плюсы в строках, соответствующих этим импликантам. Из оставшихся импликант выбираем минимальное число таких, которые покрывают крестиками все свободные столбцы (т.е. те, которые не содержат ).
Импликантная таблица
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
0010 |
0011 |
1001 |
1010 |
1100 |
1011 |
1101 |
1110 |
–01– |
|
|
|
+ |
|
+ |
|
|
10–1 |
|
|
+ |
|
|
+ |
|
|
1–01 |
|
|
+ |
|
|
|
+ |
|
1–10 |
|
|
|
+ |
|
|
|
+ |
110– |
|
|
|
|
+ |
|
+ |
|
11–0 |
|
|
|
|
+ |
|
|
+ |
В тупиковую ДНФ обязательно должна входить, иначе первые два столбца не накрываются. Следовательно, первая строка является базисной, а импликанта образует ядро функции. При таком выборе автоматически накрываются и еще два столбца . Тупиковыми импликантами являются
(8)
(11)
(11)
(11)
(11)
(11)
(11)
На рисунке изображены все тупиковые ДНФ:
Среди всех тупиковых ДНФ выбираем ДНФ наименьшей длины:
МДНФ: