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

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

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

При склеивании пары минтернов n-го ранга, отличающихся только значениями переменной xi, появляется минтерм (n-1)-го ранга Мn-1, который входит в качестве сомножителя в исходные минтермы. При этом представляющий его символ получается замещением в символе склеивания минтерма значения переменной xi на ´. Аналогично склеивание пары минтермов (n-1)-го ранга приводит к появлению минтерма (n-2)-го ранга с двумя свободными переменными и т.д. Приянто говорить, что склеиваемые минтермы покрываются результирующими минтермами более низкого ранга.

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

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

М4=

Объединяя минтермы и отмечая минтермы, покрываемые минтернами низшего рагна имеем:

М3=

´

´

´

;

М2=

´

´

´

´

´

´

´

´

Неотмеченные символы соответствуют простым импликантам сокращенной формы у =`х<sub>1</sub> х<sub>3</sub> х<sub>4</sub> +`х₁ х₂ х₄ + `х<sub>2</sub> х<sub>3</sub> х<sub>4</sub> +х<sub>1</sub>`х₂ х₄ + х₁`х<sub>3</sub> х<sub>4</sub> + х<sub>2</sub>`х₃. Для минимизации этой формы строится таблица покрытий, столбцы которой соответствуют минтермам канонической формы, а строки – простым импликантам (табл. 2.4)

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

Таблица 2.4

В рассматриваемом примере единственная экстремаль представляется символом (´ 1 0 ´). Удаляя строки экстремалей и все столбцы, в которых эти строки имеют метку, получаем более простую таблицу (табл. 2.5).

Таблица 2.5

На основе этой таблицы выбираем простые импликанты, которые дополняют выделенной множество экстремалей (ядро покрытия) до минимального покрытия функции. В данном случае целесообразно выбрать простые импликанты (0´ 11) и (10´ 1), которые совместно с экстремалью (´ 10´) и образуют минимальное покрытие у =`х<sub>1</sub> х<sub>3</sub> х<sub>4</sub> + х<sub>1</sub>`х₂ х₄ + х₂`х₃.

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