Этот метод применим к функции, записанной в СДНФ. Метод минимизации функции проводится поэтапно.
1 этап. Нахождение первичных импликант.
Все конъюнкции СДНФ данной функции сравнивают между собой попарно, применяя закон склеивания . Удобно члены функции занумеровать, поместить в таблицу.
Члены | Результаты 1-го склеивания | Результаты 2-го склеивания | …………. |
1. | 1. | 1. | |
2. | 2. | 2. | |
3. | 3. | 3. | |
… | … | … | |
… | … | … | |
… | … | … |
Сравнить последовательно 1-й член со всеми остальными. Результаты склеивания записать во 2-й столбец, указывая в скобках номера склеенных членов, а склеенные члены 1-го столбца отметить звездочкой (*).Ранг полученных конъюнкций на единицу ниже, т.е. они содержат на один знак меньше. Эти конъюнкции нумеруются, затем операцию повторяют, записывая результат в 3-й столбец и т.д. Заканчивают эту процедуру когда вновь полученные конъюнкции уже не склеиваются между собой. Все неотмеченные знаком * конъюнкции называются первичными (простыми импликантами). Все члены, отмеченные знаком *, будут поглощены простыми импликантами на основании операции поглощения . Для удобства простые импликанты в таблице обводятся рамочкой.
|
|
Дизъюнкция всех простых импликант дает сокращенную ДНФ данной функции. Далее необходимо перейти к тупиковой ДНФ. Это 2-й этап.
Прежде рассмотрим 1-й этап на примере.
Пример 5. Минимизировать функцию (см. пример 1)
Поместим члены в 1-й столбец таблицы, занумеруем их. Применим закон склеивания, результат запишем во 2-й столбец таблицы, снова занумеруем их, склеенные члены 1-го столбца отметим звездочками, и т.д.
Члены | Результаты 1-го склеивания | Результаты 2-го склеивания | |
1. | * | (1, 2) | (2, 5) |
2. | * | * (2, 3) | (3, 4) |
3. | * | * (2, 4) | |
4. | * | * (3, 5) | |
5. | * | * (4, 5) |
Несклеившиеся простые импликанты обводим рамочкой. Дизъюнкция их дает сокращенную ДНФ. В данном примере 1-й этап приводит к цели. есть минимальная форма функции. В общем случае надо перейти от сокращенной формы к тупиковой, а затем к минимальной.