Метод импликантных матриц

Для поиска минимальной формы функции пользуются методом импликантных матриц. Существо метода заключается в следующем: составляется импликантная матрица, колонки которой именуются конституентами единицы, а строки – простыми импликантами. Затем находится минимальное покрытие всех конституент единицы простейшими импликантами. При этом ищется такая минимальная совокупность простых импликант, которые совместно покрывают все конституенты единицы исходной функции. Факт покрытия отмечается в клетке матрицы символом * (звездочка) в случае, когда импликанта покрывает соответствующую конституенту (является ее собственной частью). Из всех простых импликант выбираются вначале только такие, которые только одни покрывают конституенты единицы (в колонке матрицы только один символ покрытия), затем производится перебор.

Пример:

Простые импликантыКонституенты единицы

A

B

C

D

E

F

r	*					*	*
p	*	*					*
q					*			*
m					*
n	*									*

Из матрицы видно, что в минимальную форму функции обязательно войдут импликанты n (покрывает конституенту F), импликанта r (покрывает конституенту D). То же справедливо отностительно импликанты p. Что касается остальных, то нужно выбрать минимальную совокупность.

Итак:

f1min = n

r p q f2min = n r p m

Т.е. данная функция имеет две одинаково минимальные формы.

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

Содержание раздела

---

---