Как работает метод Куайна-Мак-Класки для упрощения логических функций?

Метод Куайна — Мак-Класки — табличный метод минимизации булевых функций, предложенный Уиллардом Куайном и усовершенствованный Эдвардом Мак-Класки. ru.ruwiki.ru

Алгоритм работы метода: ru.ruwiki.ru

1. Термы, на которых определена функция алгебры логики, записываются в виде их двоичных эквивалентов. ru.ruwiki.ru
2. Эти эквиваленты разбиваются на группы, в каждую группу входят эквиваленты с равным количеством единиц (нулей). ru.ruwiki.ru
3. Производится попарное сравнение эквивалентов (термов) в соседних группах, с целью формирования термов более низких рангов. ru.ruwiki.ru
4. Составляется таблица, заголовком строк в которой являются исходные термы, а заголовком столбцов — термы низких рангов. ru.ruwiki.ru
5. Расставляются метки, отражающие поглощение термов высших рангов (исходных термов), и далее минимизация производится по методу Куайна. ru.ruwiki.ru

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

Метод имеет ограничения области применения, так как время работы метода растёт экспоненциально с увеличением входных данных. ru.ruwiki.ru