Карты Карно

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

Карта Карно (рисунок 1.10, а — в) представляет собой графическое изображение значений всех возможных комбинаций переменных. Иными словами, карту Карно можно рассматривать как графическое представление всех контермов заданного числа переменных.

Каждый контерм изображается на карте в виде клетки. Карта образуется путем такого расположения клеток, при котором контермы соседних клеток отличаются только значением одной переменной. В связи с указанным соседними считаются также крайние клетки каждого столбца или строки. Символ «1» характеризует прямое значение переменной, а «0» — ее инверсное значение.

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

Рисунок 1.10 - Карта Карно функции для двух (а),трех (б) и четырех (в) переменных

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

С помощью простейших преобразований представим эту функцию в виде ДСНФ:

После исключения повторяющихся членов функция принимает вид:

Функция состоит из 11 контермов, в связи с чем на карте Карно (рисунок 1.11) ее будут представлять 11 клеток, отмеченных единицами.

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

Затем на карте Карно необходимо определить соседние контермы (клетки) и объединить их в минимальное количество групп соседних контермов (клеток). Для наглядности выделенные группы соседних клеток показывают сплошными линиями. Минимальное количество групп соседних контермов для рассматриваемой функции будет равно трем.

Рисунок 1.11 - Карта Карно функции

В первую группу входят две нижние клетки второго столбца слева с контермами y z v и y z .

В соответствии с (1.21) имеем

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

Вторая группа состоит из двух пар верхних клеток крайних столбцов, определяющих контермы , v и x , x v. Сумма этих контермов дает

т. е. из группы исключаются две переменные: х и v.

Третья группа состоит из восьми клеток второй и третьей строк, для которых v=1, а переменные х, у, z входят с прямыми и инверсными значениями, в связи с чем переменные х, у, z из этой группы могут быть исключены. Сумма контермов обеих строк будет равна v.

На основании проведенных операций получаем минимальную функцию, выраженную в ДНФ:

Карта Карно позволяет также провести минимизацию той же функции по нулевым значениям контермов, находящихся в пустых клетках карты (рисунок 1.11) и определяющих нулевое значение функции, т. е. ее инверсное значение . Порядок проведения минимизации сохраняется прежним. Минимизирующие контуры, охватывающие соседние клетки с нулевым значением контермов рассматриваемой функции, показаны на рисунке 1.11 пунктиром. Из карты Карно находим

Воспользовавшись инверсным преобразованием (3.61) находим минимальную функцию, выраженную в КНФ, равносильную ДНФ:

Минимизация функции в ДНФ или КНФ равноправна. Представление результата минимизации в ДНФ или КНФ зависит от вида функции и состава используемых логических элементов для реализации. Реализация функции в ДНФ требует преимущественного использования логических элементов И (И—НЕ), а в КНФ — логических элементов ИЛИ (ИЛИ—НЕ). При использовании логических элементов И (И - НЕ) логическую функцию целесообразно представить в виде произведения переменных, а логических элементов ИЛИ (ИЛИ—НЕ) — в виде суммы переменных. Задачу решают, воспользовавшись правилом двойной инверсии и теоремой де Моргана. Для полученной функции в примере соответственно имеем:

В качестве примеров определим минимальные функции в ДНФ и КНФ, представленные в виде карт Карно для трех переменных (рисунок 1.12) и четырех переменных (рисунок 1.13).

Рисунок 1.12 - Карта Карно функции Рисунок 1.13 – Карта Карно функции

При нахождении минимальной функции в ДНФ, представленной картой Карно на рисунке 1.12, группировочные контуры должны охватывать контермы крайних столбцов 1 и 4 (первый контур) и контермы нижней строки (второй контур).

В первой группе контермов результат не зависит от значений х и z, так как они могут принимать либо состояние «0», либо состояние «1». Переменные х и z можно исключить. В итоге первое слагаемое определяемой минимальной функции равно . Во второй группе контермов результат не зависит от значений х и у, следовательно, второе слагаемое определяется переменной z. Таким образом, имеем минимальную функцию в ДНФ:

или

Минимальную функцию в инверсном виде находят из группировки двух пустых клеток карты:

откуда

т. е. дизъюнктивная и конъюнктивная минимальные формы рассмотренной функции совпадают.

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

или

.

Минимальную функцию в инверсном виде находят из трех контуров, охватывающих пустые клетки:

с прямым значением

или

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