2.7. АЛГОРИТМ КВАЙНА — МАК-КЛАСКИ

Этот метод включает в себя два этапа — преобразование исходной функции к сокращенной форме с помощью операции склеивания и получение минимальной формы путем исключения избыточных простых импликант.

Преобразование булевых формул путем склеивания удобно выполнять в символическом виде, где минтермы записываются в столбик словами длины , буквы которых соответствуют всем переменным данной функции. Входящие в минтерм переменные называются связанными и предстарляются значениями, при которых минтерм равен единице (1 для и 0 для ). Не входящие в миитерм переменные являются свободными и обозначаются через X. Минтермы ранга канонической формы представляются просто наборами значений переменных, на которых функция равна единице.

При склеивании пары минтермов ранга, отличающихся только значениями переменной появляется минтерм ранга который входит в сомножителя в исходные мингермы, т. е. . При этом представляющий его символ получается замещением в символе склеиваемого минтерма значения переменной на X. Аналогично склеивание пары минтермов ранга приводит к появлению минтерма ранга с двуми свободными переменными и т. д. Принято говорить, что склеиваемые минтермы покрываются результирующими минтермами более низкого порядка.

Чтобы уменьшить количество сравниваемых пар, целесообразно разбить множество минтермов на классы, в каждом из которых содержатся символы с одинаковым числом единиц (или нулей), и упорядочить эти классы по возрастающему (или убывающему) числу единиц. Так как объединяться могут только такие минтермы, символы которых содержат точно на одну больше или на одну меньше единиц, то достаточно ограничиться попарным сравнением символов соседних классов.

Рассмотрим в качестве примера функцию четырех переменных, заданную таблицей соответствия:

Множество символов минтермов этой функции после упорядочения и разбиения на классы представляют минтермы канонической формы:

Объединяя минтермы и отмечая (значком V) те из них, которые покрываются мннтермамн низшего ранга, имеем

Неотмеченные символы соответствуют простым импликантам сокращенной формы . Для минимизации этой формы строится таблица покрытий, столбцы которой соответствуют минтермам канонической формы, а строки — простым импликантам (табл. 2.4).

Таблица 2.4

Здесь меткой V отмечены те минтермы, которые покрываются простыми имплнкантами. При переходе от сокращенного покрытия к минимальному следует прежде всего выделить те импликанты, называемые экстремалями, которые покрывают минтермы данной функции, не покрываемые никакими другими импликантами. Экстремали соответствует та строка таблицы, которая содержит единственную метку в каком-либо столбце. В рассматриваемом примере единственная экстремаль представлена символом (X 10 X), которому соответствует минтерм . Удаляя строки экстремалей и все столбцы, в которых эти строки имеют метки, получаем более простую таблицу (табл. 2.5).

Таблица 2.5

На основе этой таблицы выбираем простые импликанты, которые дополняют выделенное множество экстремалей (ядро покрытия) до минимального покрытия функции. В данном случае целесообразно выбрать простые импликанты (ОХ 11) и (10 X 1), которые совместно с экстремалью (X 10 X) и образуют минимальное покрытие .

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