Метод Куайна — Мак-Класки
Метод Куайна—Мак-Класки (англ. Quine–McCluskey method) — табличный метод минимизации булевых функций, предложенный Уиллардом Куайном и усовершенствованный Эдвардом Мак-Класки. Представляет собой попытку избавиться от недостатков метода Куайна.
Алгоритм минимизации
Особенности
Специфика метода Куайна — Мак-Класки по сравнению с методом Куайна в сокращении количества попарных сравнений на предмет их склеивания. Сокращение достигается за счёт исходного разбиения термов на группы с равным количеством единиц (нулей). Это позволяет исключить сравнения, заведомо не дающие склеивания.
Несмотря на большую возможность практического применения чем у карт Карно когда речь идёт о более чем четыре переменных, метод Куайна—Мак-Класки тоже имеет ограничения области применения, так как время работы метода растёт экспоненциально с увеличением входных данных. Можно показать, что для функции от n переменных верхняя граница количества основных импликант 3n/n. Если n = 32 их может быть больше чем 6.5 * 1015. См. также Трансвычислительная задача.
Функции с большим количеством переменных должны быть минимизированы с помощью потенциально не оптимального эвристического алгоритма. На сегодня эвристический алгоритм минимизации эспрессо является фактическим мировым стандартом.
Пример
Шаг 1: находим основные импликанты
Пусть функция задана с помощью следующей таблицы истинности:
Можно легко записать СДНФ, просто просуммировав минтермы (не обращая внимание на не полностью определённые термы), где функция принимает значение 1.
f = x ¯ y z ¯ t ¯ + x y ¯ z ¯ t ¯ + x y ¯ z t ¯ + x y ¯ z t + x y z ¯ t ¯ + x y z t . {displaystyle f={ar {x}}y{ar {z}}{ar {t}}+x{ar {y}}{ar {z}}{ar {t}}+x{ar {y}}z{ar {t}}+x{ar {y}}zt+xy{ar {z}}{ar {t}}+xyzt.}Для оптимизации запишем минтермы, включая те, которые соответствуют равнодушным состояниям, в следующую таблицу:
Теперь можно начинать комбинировать между собой минтермы, то есть проводить операцию склеивания. Если два минтерма отличаются лишь символом, который стоит в одной и той же позиции в обоих, заменяем этот символ на «-», это означает, что данный символ для нас не имеет значения. Термы, не поддающиеся дальнейшему комбинированию, обозначаются «*». При переходе к импликантам второго ранга, трактуем «-» как третье значение. Например: −110 и −100 или −11- могут быть скомбинированы, но не −110 и 011-. (Подсказка: Сначала сравнивай «-».)
Количество "1" Минтермы | Импликанты 1-го уровня | Импликанты 2-го уровня ------------------------------|-----------------------|---------------------- 1 m4 0100 | m(4,12) -100* | m(8,9,10,11) 10--* m8 1000 | m(8,9) 100- | m(8,10,12,14) 1--0* ------------------------------| m(8,10) 10-0 |---------------------- 2 m9 1001 | m(8,12) 1-00 | m(10,11,14,15) 1-1-* m10 1010 |-----------------------| m12 1100 | m(9,11) 10-1 | ------------------------------| m(10,11) 101- | 3 m11 1011 | m(10,14) 1-10 | m14 1110 | m(12,14) 11-0 | ------------------------------|-----------------------| 4 m15 1111 | m(11,15) 1-11 | | m(14,15) 111- |Шаг 2: таблица простых импликант
Когда дальнейшее комбинирование уже невозможно, конструируем таблицу простых импликант. Здесь учитываем только те выходы функции, которые имеют значение, то есть не обращаем внимания на не полностью определённые состояния.
Принцип выбора импликант такой же как и в методе Куайна. Простые импликанты, которые является ядрами выделены жирным шрифтом. В этом примере, ядра не перекрывают все минтермы, в таком случае может быть выполнена дополнительная процедура упрощения таблицы (см. Метод Петрика). Получаем следующий вариант:
f x , y , z , t = y z ¯ t ¯ + x y ¯ + x z . {displaystyle f_{x,y,z,t}=y{ar {z}}{ar {t}}+x{ar {y}}+xz. }