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

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

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

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

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

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

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

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

f = yzv + xyv + yzv + хуz+ xzv + уzv + уzv.

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

После исключения повторяющихся членов функция выражается в СДНФ:

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

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

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

В первую группу входят две нижние клетки второго столбца слева с минтермами xyzv и xyzv. В соответствии с аксиомой дизъюнкции имеем

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

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

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

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

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

Карта Карно позволяет также провести минимизацию той же функции в КНФ по нулевым значениям минтермов, находящихся в пустых клетках карты (рис. 1.5) и определяющих нулевое значение функции, т. е. ее инверсное значение F. Порядок проведения минимизации сохраняется прежним. Минимизирующие контуры, охватывающие соседние клетки с нулевым значением минтермов рассматриваемой функции, показаны на рис.6 пунктиром. Из карты Карно находим F= хуz + уzv + xzv + xyv.

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

F = (x+y+z+v)(y+z+v)(x+z+v)(x+y+v).

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

F = xyzyzv, Р = х+у+z+v+у+z+v+x+z+v+x+y+v.

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

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

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

или