Метод Квайна — Мак-Класки¶

Метод Квайна — Мак-Класки — это алгоритм минимизации булевых функций, предназначенный для упрощения логических выражений, представленных в виде дизъюнктивной нормальной формы (ДНФ). Метод является систематической процедурой, позволяющей находить минимальные или сокращённые покрытия булевой функции, и широко применяется в цифровой схемотехнике и теории автоматов. Разработан независимо американским математиком Уиллардом ван Орманом Квайном (1952) и американским инженером Эдвардом Джозефом Мак-Класки (1956). В отличие от карт Карно, которые эффективны для функций с небольшим числом переменных (до 4–6), метод Квайна — Мак-Класки пригоден для автоматизированной обработки функций с произвольным числом переменных и реализуется программно.

¶История

Метод восходит к работам Уилларда Квайна, который в 1952 году предложил алгоритм нахождения простых импликант булевой функции, основанный на последовательном склеивании термов. В 1956 году Эдвард Мак-Класки усовершенствовал процедуру, формализовав этапы поиска существенных импликант и выбора минимального покрытия. Метод стал одним из первых алгоритмов, реализованных в системах автоматизированного проектирования (САПР) цифровых микросхем. В 1960-х годах он был включён в учебные курсы по дискретной математике и схемотехнике, а позже адаптирован для многозначных логик и не полностью определённых функций.

¶Основные понятия

Для понимания метода необходимо ввести несколько определений:

• Импликанта — произведение (конъюнкция) литералов (переменных или их отрицаний), которое обращается в единицу на всех наборах, где функция равна единице.
• Простая импликанта — импликанта, которая не может быть упрощена путём удаления литералов (то есть не поглощается другой импликантой).
• Существенная импликанта — простая импликанта, которая покрывает хотя бы один минтерм (единичный набор), не покрываемый никакой другой простой импликантой.
• Минтерм — конъюнкция всех переменных функции (с отрицанием или без), дающая единицу на единственном наборе.
• Покрытие — множество импликант, объединение которых (дизъюнкция) равно заданной функции.

¶Алгоритм

Метод Квайна — Мак-Класки состоит из двух основных этапов: нахождение всех простых импликант и выбор минимального покрытия.

¶Этап 1: Построение всех простых импликант

1. Представление минтермов в двоичной форме. Каждый минтерм кодируется двоичным числом, где 1 соответствует переменной без отрицания, 0 — с отрицанием. Для не полностью определённых функций (с безразличными состояниями) используются символы «-» (прочерк).
2. Группировка по числу единиц. Минтермы разбиваются на группы в зависимости от количества единиц в двоичном представлении. Это ускоряет процесс склеивания, так как склеиваться могут только термы, различающиеся ровно в одном разряде.
3. Последовательное склеивание. Для каждой пары термов из соседних групп (с числом единиц, отличающимся на 1) проверяется, различаются ли они ровно в одном бите. Если да, то образуется новый терм, в котором этот бит заменяется на «-» (прочерк). Исходные термы помечаются как использованные. Процесс повторяется для вновь полученных термов, пока возможно склеивание.
4. Выделение простых импликант. Термы, которые не были помечены как использованные на каком-либо шаге, являются простыми импликантами. Они не могут быть склеены с другими термами.

¶Этап 2: Выбор минимального покрытия

1. Построение таблицы покрытия. Строки таблицы соответствуют простым импликантам, столбцы — исходным минтермам (или существенным наборам). Если импликанта покрывает минтерм, в соответствующей ячейке ставится отметка.
2. Выделение существенных импликант. Если в каком-то столбце есть только одна отметка, то соответствующая импликанта является существенной — она обязательно включается в минимальное покрытие. После выбора существенных импликант удаляются все покрываемые ими минтермы.
3. Решение задачи о покрытии. Для оставшихся минтермов выбирается минимальное подмножество простых импликант, покрывающее все столбцы. Эта задача является NP-трудной, поэтому для её решения используются эвристики (например, метод Петрика, метод ветвей и границ) или точные алгоритмы для малых размерностей.

¶Пример

Рассмотрим функцию трёх переменных \( f(x, y, z) \), заданную минтермами: 0 (000), 1 (001), 3 (011), 5 (101), 7 (111).

Этап 1. Склеивание:

• Группа 0 (0 единиц): 000
• Группа 1 (1 единица): 001
• Группа 2 (2 единицы): 011, 101
• Группа 3 (3 единицы): 111

Склеивание:

• 000 и 001 → 00- (использованы 000, 001)
• 001 и 011 → 0-1 (использованы 001, 011)
• 001 и 101 → -01 (использованы 001, 101)
• 011 и 111 → -11 (использованы 011, 111)
• 101 и 111 → 1-1 (использованы 101, 111)

Повторное склеивание полученных термов:

• 00- и 0-1 → 0-- (использованы 00-, 0-1)
• 0-1 и -11 → --1 (использованы 0-1, -11)
• -01 и 1-1 → --1 (использованы -01, 1-1)

Простые импликанты: 0-- (соответствует ¬x), --1 (соответствует z), и терм -11 (не был использован во втором склеивании, соответствует yz).

Этап 2. Таблица покрытия:

Существенные импликанты: 0-- покрывает 000, который не покрывается другими; --1 покрывает 101, который не покрывается другими. После их выбора остаётся минтерм 011, покрываемый обеими импликантами. Минимальное покрытие: {0--, --1} → \( \neg x \vee z \).

¶Применение

Метод Квайна — Мак-Класки используется в:

• Цифровой схемотехнике — для синтеза комбинационных логических схем (сумматоров, дешифраторов, мультиплексоров) с минимальным числом логических элементов.
• Системах автоматизированного проектирования — в программных пакетах (например, Espresso, Logic Friday) для минимизации булевых функций.
• Теории автоматов — при минимизации систем переключательных функций.
• Обучении — как классический пример алгоритма минимизации в курсах дискретной математики и информатики.

¶Ограничения и модификации

Основной недостаток метода — экспоненциальный рост числа термов при увеличении числа переменных. Для функций с 10 и более переменными алгоритм становится неэффективным. В таких случаях применяются эвристические методы (например, алгоритм Espresso), которые не гарантируют нахождение абсолютного минимума, но работают быстрее. Метод также может быть расширен на многозначные логики и не полностью определённые функции (с «безразличными» состояниями). Для ускорения этапа выбора покрытия используются алгоритмы на основе целочисленного линейного программирования или методы ветвей и границ.

¶Источники

• Quine W. V. The Problem of Simplifying Truth Functions // The American Mathematical Monthly. — 1952. — Vol. 59, No. 8. — P. 521–531.
• McCluskey E. J. Minimization of Boolean Functions // Bell System Technical Journal. — 1956. — Vol. 35, No. 6. — P. 1417–1444.
• Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986. — 384 с.
• Угрюмов Е. П. Цифровая схемотехника. — СПб.: БХВ-Петербург, 2004. — 800 с.