- 550 -
образует ядро покрытия. Ясно, что при переходе от сокращенного покрытия к минимальному прежде всего следует выделить все экстремали. Если множество экстремалей не образует покрытия, то оно дополняется до покрытия кубами из сокращенного покрытия.
Сокращенное покрытие Z, и минимальные покрытия С’min и C”min выражаются следующим образом:
; 
; 
.
Сокращенная форма представляет собой дизъюнкцию четырех простых импликант, т. е. y = x1x̅2 ∨ x1x3 ∨ x2x3 ∨ x̅1x2. Экстремалями являются простые импликанты x1x̅2 и x̅1x2, которым соответствуют 1-кубы (10x) и (01x), а отмеченные вершины - x1x̅2x̅3 и x̅1x2x̅3 или соответственно (100) и (010).
2. Метод Квайна - Мак-Класки. Этот метод используется в случаях, когда функция задана в дизъюнктивной совершенной нормальной форме (или таблицей соответствия). Приведение к сокращенной форме осуществляется последовательным применением операции склеивания axi ∨ ax̅i = a, где a - конъюнкции переменных, отличных от xi. Множеству конституент единицы, представленных в исходной форме, соответствует совокупность 0-кубов K0, а операции склеивания - объединение двух 0-кубов, которые отличаются только одной координатой. Результатом такого объединения является 1-куб, в котором различные координаты исходных 0-кубов замещены символом х. Сравнивая попарно все 0-кубы, получаем множество 1-кубов K1. Применяя к K1 операцию склеивания, находим множество 2-кубов K2 и т. д. Этот процесс продолжается до тех пор, пока получаемое из Ks очередное Ks+1 не окажется пустым множеством. В результате множество K0 преобразуется в комплекс кубов К = { K0, K1, K2, …, Ks], причем s ≤ n.
Для выделения из К множества простых импликант Z ⊂ K при каждой операции склеивания необходимо отмечать каким-либо знаком (например, меткой v ) те кубы, которые объединяются в кубы высшей размерности. Очевидно, неотмеченные кубы и образуют множество простых импликант Z. Чтобы уменьшить число сравниваемых пар при операции объединения целесообразно разбить множество Ks на классы, в каждом из которых содержатся s-кубы с одинаковым числом единиц (или нулей), и упорядочить эти классы по возрастающему числу единиц. Так как объединяться могут только такие два s-куба, число единиц в которых точно на
- 551 -
одну больше или меньше, то достаточно ограничиться попарным сравнением s-кубов одного класса с s-кубами соседнего класса.
На втором шаге при извлечении экстремалей и образовании минимального покрытия используется таблица покрытий. Ее строки соответствуют простым импликантам, а столбцы — конституентам единицы дизъюнктивной совершенной нормальной формы данной функции, которые представляются 0-кубами (вершинами) комплекса кубов. В клетку таблицы записывается метка, если простая импликанта в данной строке покрывает вершину в данном столбце. Экстремалям соответствуют те строки таблицы, которые содержат единственную метку в каком-либо столбце. Удаляя строки экстремалей и все столбцы, в которых эти строки имеют метки, получаем более простую таблицу. На основе этой таблицы выбираем простые импликанты, которые дополняют выделенное множество экстремалей до минимального покрытия функции.
Пример минимизации функции. Рассмотрим в качестве примера функцию четырех переменных у = f(х1, х2, х3, х4), заданную таблицей соответствия
Ей соответствует дизъюнктивная совершенная нормальная форма y = x̅1x̅2x3x4 ∨ x̅1x2x̅3x̅4 ∨ x̅1x2x̅3x4 ∨ x̅1x2x3x4 ∨ x1x̅2x̅3x4 ∨ x1x̅2x3x4 ∨ x12x̅3x̅4 ∨ x1x2x̅3x4 . Множество 0-кубов после разбиения и упорядочения записывается следующим образом:
.
Объединяя кубы и отмечая те из них, которые покрываются кубами большей размерности, имеем: