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

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

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

Рассмотрим процесс минимизации на примере функции F. Сначала определим, какие конституенты имеют общие члены. Это конституенты К^и К_С), а также К₄ и К₆. Так как конституенты К₂ и К₆ имеют общие члены ВС, они могут быть вынесены за скобки:

Оставшееся в скобках выражение (AvA) = l. Таким образом, конституенты К₂ и К₆ склеиваются по А:

Однако конституента К₆ может понадобиться для операции склеивания конституент К₄ и К₆, поэтому проведем неполное склеивание с сохранением конституенты К₆, т. е.:

Таким образом,.

Теперь можно провести склеивание по В конституент К₄ и К₆:

В результате имеем более простое выражение для F:

Вынесем за скобки С и получим конечный результат минимизации:

Пример 3.5.

Составить СовДНФ функции F" и выполнить ее минимизацию.

Решение. Составим список наборов, на которых функция F" равна единице. Это наборы 0, 1,2, 4, 5.

Запишем для каждого набора констигуенту единицы (табл. 3.7).

Таблица 3.7

Составим дизъюнкцию всех конституент:

Будем выполнять операцию склеивания конституент, помня, что для любой конституенты можно выполнять операцию неполного склеивания, т. е. использовать се дважды для склеивания с разными конституентами.

Конституенты К₀ и К_у склеиваются по С: К₀ v К_х = ЛВС v ЛВС = AB (CvC) = ЛВ.

Копституеиты К_А и К₅ склеиваются по С: K_Av К₅ = ЛВС v ЛВС = ЛВ (С vC) = ЛВ.

Результаты склеивания конституент К₀, К_х и К₅ в свою очередь склеиваются по Л:

Таким образом, дизъюнкция конституент К₀, К_у, К_А, К₃ равна В.

Конституенты К₂ и К₀ склеиваются по В: К₂ v К₀ = ЛВС v ЛВС = AC (Bv В) = ЛС.

Функция F" в результате упрощения будет иметь вид: F" = BvЛС.

В приведенном примере конституента К₀ использовалась дважды для склеивания с конституентами К_у и К₂.