Минимизация логических функций

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

. (2.3)

Применяя к (2.3) закон склеивания = 1, получаем

.

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

Метод непосредственного упрощения весьма громоздок в реализации и, кроме того, не гарантирует отыскания минимальной нормальной формы (НФ). Поэтому применяют различные способы систематизации слагаемых, облегчающие их склеивание. Одним из таких способов является применение диаграмм или карт Карно (Вейча). Карта Карно представляет собой прямоугольник, разбитый на квадраты, число которых равно 2ⁿ, где n – количество переменных (аргументов). Так, для функции трех переменных будет 8 квадратов, для функции четырех переменных – 16 и т. д. На полученной таким образом карте обозначаются переменные. Каждая переменная должна занимать 50 % клеток карты и на 50 % пересекаться с клетками, занимаемыми другими переменными. Карты Карно отличаются от карт Вейча порядком обозначения переменных.

Например, для функции четырех переменных ( , , , ) на карте Карно по горизонтали перечисляются и , по вертикали – и (рис. 2.12). На карте Вейча: по горизонтали – и , по вертикали – и . Клетки, не занятые указанными переменными, будут представлять их инверсию. Произведение переменных, на площадях которых расположена клетка, представляет соответствующий минтерм.

Функцию в СДНФ наносят на карту, отмечая, например, знаком 1 квадраты, соответствующие тем наборам, на которых функция равна единице. В остальные квадраты вписывается 0. Таким образом, карта Карно – это один из способов представления логической функции. Задача минимизации с помощью карт Карно заключается в отыскании минимального покрытия функции, т. е. покрытия минимальным числом минтермов, содержащих минимальное число переменных. Для этого необходимо произвести объединение (склеивание) клеток.