Упрощение и минимизация логических функций.

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

Рис. 4. Изображения карт Карно

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

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

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

Примечание: количество соседних отмеченных минтермов в группе должно быть пропорционально ; объединенные в группы минтермы на картах Карно (отмеченные клетки) должны образовывать либо форму квадрата, либо форму прямоугольника.

Рассмотрим процесс минимизации на примере функции, заданной следующим логическим уравнением:

Представим эту функцию в СДНФ:

На рис.6 изображена карта Карно, соответствующая рассматриваемой функции. Минтермы функции образуют в карте три группы.

Одна группа состоит из двух минтермов BCD и , что преобразуется к виду

,

т.е. переменная D из этой группы может быть исключена.

Вторая группа состоит из двух пар минтермов: , и , т.е. включает 4 = единиц. Представим дизъюнкцию минтермов этой группы в виде:

Отсюда видно, что исключаются две переменные: A и D.

Третья группа состоит из строк, для которых D = 1 и включает единиц. Следовательно, из этой группы могут быть исключены три переменные: A, B и С. Итак, получаем минимальную ДНФ в виде:

.

В общем случае функция может иметь несколько минимальных форм. На рис. 7 представлена карта Карно для функции, которая имеет две минимальные ДНФ:

и .

Карта Карно позволяет также получить минимальную КНФ функции. Минтермы, соответствующие нулевым значениям функции, находятся в пустых клетках карты Карно. Отсюда следует, что, объединяя минтермы, соответствующие пустым клеткам, можно получить минимальную ДНФ для инверсного значения функции, представленной на карте единицами. Так из рис. 7 следует нижеприведенная форма:

.

Пользуясь свойством двойственности, можно получить минимальную КНФ данной функции в виде:

.

Поиск по сайту: