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

1. Постановка задачи. Минимизация схемы в булевом базисе сводится к поиску минимальной дизъюнктивной формы, которой соответствует минимальное покрытие. Общее число букв, входящих в нормальную форму, выражается ценой покрытия

Обычно задача минимизации решается в два шага. Сначала ищут сокращенное покрытие, которое включает все 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 -

одну больше или меньше, то достаточно ограничиться попарным сравнением s-кубов одного класса с s-кубами соседнего класса.

На втором шаге при извлечении экстремалей и образовании минимального покрытия используется таблица покрытий. Ее строки соответствуют простым импликантам, а столбцы — конституентам единицы дизъюнктивной совершенной нормальной формы данной функции, которые представляются 0-кубами (вершинами) комплекса кубов. В клетку таблицы записывается метка, если простая импликанта в данной строке покрывает вершину в данном столбце. Экстремалям соответствуют те строки таблицы, которые содержат единственную метку в каком-либо столбце. Удаляя строки экстремалей и все столбцы, в которых эти строки имеют метки, получаем более простую таблицу. На основе этой таблицы выбираем простые импликанты, которые дополняют выделенное множество экстремалей до минимального покрытия функции.

Пример минимизации функции. Рассмотрим в качестве примера функцию четырех переменных у = f(х₁, х₂, х₃, х₄), заданную таблицей соответствия

Ей соответствует дизъюнктивная совершенная нормальная форма y = x̅₁x̅₂x₃x₄ ∨ x̅₁x₂x̅₃x̅₄ ∨ x̅₁x₂x̅₃x₄ ∨ x̅₁x₂x₃x₄ ∨ x₁x̅₂x̅₃x₄ ∨ x₁x̅₂x₃x₄ ∨ x₁₂x̅₃x̅₄ ∨ x₁x₂x̅₃x₄ . Множество 0-кубов после разбиения и упорядочения записывается следующим образом:

Объединяя кубы и отмечая те из них, которые покрываются кубами большей размерности, имеем:

- 552 -

Простым импликантам соответствуют неотмеченные кубы.Составляем таблицу покрытия Z, которому соответствует сокращенная форма y = x̅₁x₃x₄ ∨ x̅₁x₂x₄ ∨ x̅₂x₃x₄ ∨ x₁x̅₂x₄ ∨ x₁x̅₃x₄ ∨ x₂x₃ .

→

K⁰

-------

↓ Z

0

1

0

0

0

0

1

1

0

1

0

1

1

0

0

1

1

1

0

0

0

1

1

1

1

0

1

1

1

1

0

1

Обозначения

импликант

0 x 1 1

v

v

A

0 1 x 1

v

v

B

x 0 1 1

v

v

C

1 0 x 1

v

v

D

1 x 0 1

v

v

E

x 1 0 x

v

v

v

v

F

Извлекаем единственную экстремаль (х10х), которой соответствует минитерм x₂x̅₃ и упрощаем таблицу к виду:

→

K₁⁰

-------

↓ Z₁

0

0

1

1

1

0

0

1

0

1

1

1

1

0

1

1

0 x 1 1

v

v

0 1 x 1

v

x 0 1 1

v

v

1 0 x 1

v

v

1 x 0 1

v

В качестве дополнительных целесообразно выбрать кубы (0x11) и (10x1), так как они совместно с экстремалью (x10x) образуют покрытие функции, минимальная форма которой имеет вид: y = x̅₁x₃x₄ ∨ x₁x̅₂x₄ ∨ x₂x̅₃ . Соответствующее этой функции

- 553 -

минимальное покрытие иллюстрируется на четырехмерном кубе и на карте Карно.

@@@@@@@