Математический аппарат инженера

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

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

5. Минимизация булевых функций

1. Постановка задачи. Минимизация схемы в булевом базисе сводится к поиску минимальной дизъюнктивной формы, которой соответствует минимальное покрытие. Общее число букв, входящих в нормальную форму, выражается ценой покрытия , где q_s - число s-кубов, образующих покрытие даннойфункции от n переменных. Используются и другие определения цены покрытия, например с’ = с + q, где

q - общее число всех кубов покрытия. Во всех случаях минимальное покрытие характеризуется наименьшим значением его цены.

Обычно задача минимизации решается в два шага. Сначала ищут сокращенное покрытие, которое включает все s-кубы максимальной размерности, но не содержит ни одного куба, покрывающегося каким-либо кубом этого покрытия. Соответствующую дизъюнктивную нормальную форму называют сокращенной, а ее минитермы - простыми импликантами. Для данной функции сокращенное покрытие является единственным, но оно может быть избыточным вследствие того, что некоторые из кубов покрываются совокупностями других кубов.

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

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

- 550 -

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

Сокращенное покрытие Z, и минимальные покрытия С’_min и C”_min выражаются следующим образом:

; ; .

Сокращенная форма представляет собой дизъюнкцию четырех простых импликант, т. е. y = x₁

x̅₂ ∨ x₁x₃ ∨ x₂x₃ ∨ x̅₁x₂. Экстремалями являются простые импликанты x₁x̅₂ и x̅₁x₂, которым соответствуют 1-кубы (10x) и (01x), а отмеченные вершины - x₁x̅

₂x̅₃ и x̅₁x₂x̅₃ или соответственно (100) и (010).

2. Метод Квайна - Мак-Класки. Этот метод используется в случаях, когда функция задана в дизъюнктивной совершенной нормальной форме (или таблицей соответствия). Приведение к сокращенной форме осуществляется последовательным применением операции склеивания ax_i ∨ ax̅_i = a, где a - конъюнкции переменных, отличных от x_i. Множеству конституент единицы, представленных в исходной форме, соответствует совокупность 0-кубов K⁰, а операции склеивания - объединение двух 0-кубов, которые отличаются только одной координатой. Результатом такого объединения является 1-куб, в котором различные координаты исходных 0-кубов замещены символом х. Сравнивая попарно все 0-кубы, получаем множество 1-кубов K¹. Применяя к K¹ операцию склеивания, находим множество 2-кубов K²

и т. д. Этот процесс продолжается до тех пор, пока получаемое из K^s очередное K^s+1 не окажется пустым множеством. В результате множество K⁰ преобразуется в комплекс кубов К = { K⁰, K¹, K², …, K^s], причем s ≤ n.

Для выделения из К множества простых импликант Z ⊂ K при каждой операции склеивания необходимо отмечать каким-либо знаком (например, меткой v ) те кубы, которые объединяются в кубы высшей размерности. Очевидно, неотмеченные кубы и образуют множество простых импликант Z. Чтобы уменьшить число сравниваемых пар при операции объединения целесообразно разбить множество K^s на классы, в каждом из которых содержатся s-кубы с одинаковым числом единиц (или нулей), и упорядочить эти классы по возрастающему числу единиц. Так как объединяться могут только такие два s-куба, число единиц в которых точно на

- 551 -