Алгоритм Куайна – МакКласки

Алгоритм Куайна-МакКласки ( QMC ), также известный как метод простых импликантов , представляет собой метод, используемый для минимизации булевых функций , который был разработан Уиллардом В. Куайном в 1952 году ^{[1] [2]} и расширен Эдвардом Дж. МакКласки. в 1956 г. ^[3] В качестве общего принципа этот подход уже был продемонстрирован логиком Хью Макколлом в 1878 г. ^{[4] [5] [6]} был доказан Арчи Блейком в 1937 г. ^{[7] [8] [9] [6]}и был заново открыт Эдвардом В. Самсоном и Бертоном Э. Миллсом в 1954 году ^{[10] [6]} и Раймондом Дж. Нельсоном в 1955 году. ^{[11] [6]} Также в 1955 году Пол В. Абрахамс и Джон Г. Нордал ^[12] , а также Альберт А. Маллин и Уэйн Г. Келлнер ^{[13] [14] [15] [16]} предложили десятичный вариант метода. ^{[17] [14] [15] [16] [18] [19] [20] [21]}

Алгоритм Куайна-МакКласки функционально идентичен отображению Карно , но табличная форма делает его более эффективным для использования в компьютерных алгоритмах, а также дает детерминированный способ проверки достижения минимальной формы булевой функции. Иногда его называют методом табуляции.

Хотя алгоритм Куайна-МакКласки более практичен, чем отображение Карно , при работе с более чем четырьмя переменными, он также имеет ограниченный диапазон использования, поскольку решаемая им задача является NP-полной . ^{[22] [23] [24]} Время работы алгоритма Куайна-МакКласки экспоненциально растет с увеличением числа переменных. Для функции от n переменных количество простых импликант может достигать , ^[25] например, для 32 переменных может быть более 534 × 10 ¹² простых импликантов. Функции с большим количеством переменных должны быть минимизированы потенциально неоптимальными${\ displaystyle 3 ^ {n} / {\ sqrt {n}}}$эвристические методы, из которых минимизатор эвристической логики Espresso был стандартом де-факто в 1995 году. ^{[ требуется обновление ] [26]}

Второй шаг алгоритма сводится к решению проблемы покрытия множества ; ^[27] На этом шаге алгоритма могут возникнуть NP-трудные экземпляры этой проблемы. ^{[28] [29]}

В этом примере входные данные представляют собой логическую функцию с четырьмя переменными, которая оценивается как для значений и , оценивается как неизвестное значение для и и везде (где эти целые числа интерпретируются в их двоичной форме для ввода в для краткости изложения). обозначение). Входные данные, которые оцениваются , называются «minterms». Мы кодируем всю эту информацию, записывая${\ Displaystyle е: \ {0,1 \} ^ {4} \ к \ {0,1 \}}$${\ Displaystyle 1}$${\ Displaystyle 4,8,10,11,12}$${\ Displaystyle 15}$${\ Displaystyle 9}$${\ Displaystyle 14}$${\ Displaystyle 0}$${\ Displaystyle е}$${\ Displaystyle 1}$

Это выражение говорит о том, что выходная функция f будет равна 1 для minterms и (обозначается термином «m») и что нас не волнует вывод для комбинаций и (обозначается термином «d»).${\ Displaystyle 4,8,10,11,12}$${\ Displaystyle 15}$${\ Displaystyle 9}$${\ Displaystyle 14}$

Диаграмма Хассе графа поиска алгоритма для 3 переменных. Учитывая, например, подмножество узлов нижнего уровня (светло-зеленые), алгоритм вычисляет минимальный набор узлов (здесь: темно-зеленый), который точно покрывает .${\ displaystyle S = \ {abc, a {\ overline {b}} c, {\ overline {a}} bc, {\ overline {a}} b {\ overline {c}}, {\ overline {a} }{\надчеркните {b}}c\}}$${\ Displaystyle \ {{\ overline {а}} б, в \}}$${\ Displaystyle S}$