Метод Квайна – Мак – Класки

Основное неудобство метода Квайна состоит в том, что при поиске простых импликант необходимо производить попарные сравнения вначале всех конститутент единицы, затем полученных в результате склеивания произведений.

С целью упрощения этой процедуры Мак – Класки предложил алгоритм, существо которого сводится к следующему:

1. вводится понятие цифрового эквивалента для каждого произведения по следующему правилу: некоторому произведению ставится в соответствие цифровой эквивалент с использованием цифр 0 и 1 и – (прочерк). Переменной, входящей в произведение в прямом виде ставится в соответсвие единица (1), в инверсном – нуль (0), отсутствие переменной обозначается прочерком;
2. в любом произведении переменные располагаются только в одном порядке, а именно – по возрастанию индексов;
3. склейке подлежат только те произведения, в которых прочерки расположены соответственно, количество нулей (или единиц) отличается на единицу и они расположены так же соответственно.

Пример:

Произведению x₁x₂x₄ для функции, зависящей от пяти переменных нужно поставить в соответствие следующий цифровой набор: x₁x₂x₄: 11-0-

Приведем графическое изображение процесса поиска простых импликант для функции, представленной в следующей СДНФ:

f(x₁x₂x₃x₄) = x₁x₂x₃x₄ x₁x₂x₃x₄ x₁x₂x₃x₄ x₁x₂x₃x₄

запишем выражение функции в виде дизъюнкции цифровых эквивалентов:

f(x₁x₂x₃x₄) = 1101 1010 0101 1000

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

Для нашего примера это выглядит так:

Итак, простые импликанты:

10-0 и -101, т.е. f(x₁x₂x₃x₄) = x₁x₂x₄ x₂x₃x₄