Минимизация логических функций

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

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

Общий принцип

Для минимизации функции по методу Квайна, необходимо, чтобы она была представлена в СНДФ. Метод заключается в пошаговом уменьшении ранга минтермов, входящих в состав ФАЛ и их количества.

Терминология

Импликанты – конъюнктивные термы переменного ранга.

Первичные импликанты – импликанты, входящие в выражения для минимизированной функции.

Существенные импликанты – импликанты, безусловно входящие в состав ФАЛ (т.е. каждая из них является единственной первичной импликантой, входящией в состав одного из первоначальных минтермов (минтермов СНДФ))

Нефункциональные импликанты – импликанты, не входящие в состав ни одного из минтермов.

Алгоритм минимизации

I этап. Получение первичных импликант.

II этап. Обработка первичныхимпликант

а) выделение существенных импликант.

б) исключение нефункциональных импликант

III этап. Составление минимальной комбинации импликант для покрытия оставшихся минтермов.