Общий принцип минимизации функции по методу Квайна

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

В результате таких действий будет получена дизъюнкция простых конъюнкций (т.е. конъюнкций, логическими сомножителями которой являются переменные или их отрицания). Далее для получения СДНФ, у которой используемые простые конъюнкции включают все переменные или их отрицания, в конъюнкции, где представлены не все переменные, вводят недостающие переменные X_i; за счет умножения расширяемой конъюнкции на и раскрытия скобок.

ПРИМЕР: С помощью эквивалентных преобразований приведите формулу к ДНФ, КНФ, СДНФ, СКНФ.

= = = =

= = =

= = =

= =

= - КНФ.

=

= =

= - СКНФ.

= =

= =

= =

= - ДНФ.

= =

= =

= - СДНФ.

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

ТЕРМИНОЛОГИЯ:

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

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

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

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

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

Метод Квайна выполняется в несколько этапов.

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

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

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

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

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

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

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

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

Пример 1 Задана функция

I этап. а) Получение импликант ранга 2 и 1.

В таблице нет пустых строк, след. ранг всех импликант уменьшен до 1.

Полученные импликанты: х₁, х₂

Импликанты первого ранга всегда являются первичными, поэтому поиск первичных импликант закончен.