Упрощение логических функций методом Карно

В основу преобразования логической функции положена теорема о склеивании. Если функция записана в СДНФ, то в ней могут оказаться пары соседних минтермов, для которых можно выполнить склеивание, в результате чего пара минтермов заменяется импликантой — общей частью этих минтермов. В таком случае один и тот же минтерм может быть соседним с несколькими другими минтермами, образуя соответствующие пары, для каждой из которых можно осуществить склеивание. Например, в функции порядка /7 = 4.

первый член является соседним по отношению ко второму и третьему членам, поэтому после склеивания получим функцию.

содержащую две импликанты размерностью (п — 1), т. е. 3-го порядка.

Увидеть все соседние минтермы не так просто, особенно для функций большой размерности. Более того, импликанты, имеющие размерность (п — 1), сами могут оказаться соседними и допустить повторное склеивание. Пусть.

тогда можно склеить первый и второй члены, а также третий с пятым и четвертый с шестым и получить

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

где ad — то общее, что есть в первом, втором, третьем и пятом членах функции (18).

Карно М. предложил расположить все возможные минтермы функции порядка п в виде прямоугольной или квадратной таблицы так, чтобы каждый минтерм был в окружении соседних минтермов. Имеется в виду, что слева и справа, а также сверху и снизу от минтерма оказываются соседние ему минтермы. Не останавливаясь на алгоритме формирования карт Карно, в основу которого положен код Грея, покажем вид карт для п = 2, …, 5. На рис. 23 в клетках карт Карно записаны номера соответствующих минтермов в десятичном и двоичном виде.

Рис. 23. Карты Карно для п = 2 (а); /7 = 3 (б); п = 4 (в); п = 5 (г) Нетрудно видеть, что функция (18) есть сумма минтермов.

Двоичное отображение соответствующих номеров: 0001, ООП, 0101,.

1010,0111,1000.

Если в соответствующие клетки карты Карно поставить 1, то эта карта для функции (18) приобретает вид, показанный на рис. 24.

Удивительное свойство карт Карно заключается в том, что наружные стороны карты могут быть попарно склеены, так как там располагаются соседние минтермы. Например, для п = 4 минтермы верхнего ряда т₀, т_А, т_п, т_% являются попарно соседними с минтермами нижнего ряда т_ъ т_ь, /л_|4, т₁₀ и т. д. Зная это свойство, легко увидеть пары склеиваемых минтермов. Пара склеиваемых минтермов образует импликанту, содержащую общую в них часть. Из карты Карно легко получить соответствующие импликанты, используя пометки на полях, показывающие общее в элементах столбцов и строк. Например, пары минтермов в верхнем правом и нижнем правом углах имеют одинаковые переменные а, Ъ, d, что дает импликанту add.

Рис. 24. Карты Карно дпя функции (18).

Пары соседних минтермов образуют простейший контур с числом клеток 2.

Контур дтя склеивания может содержать не только 2 клетки (одинарное склеивание, исключение одной переменной, получение импликанты размерности (п — 1)), но и 4 клетки (двойное склеивание, исключение двух переменных, получение импликанты порядка (я — 2)), восемьклеток и т. д., т. е. кратно 2*, где к — целое положительное число.

Контур для склеивания (так называемый истинный контур) имеет вид квадрата или прямоугольника. Минимальная длина стороны прямоугольника /_min = 1. Длина стороны также кратна числу 2^к. Максимальная длина.

/.тх ⁼ 2″ ^/2 для четного значения п и /_тах = 2 ^(и+1)/2 для нечетного значения п. На рис. 24 четыре левые клетки, заполненные единицами, образуют истинный контур, в котором у всех элементов есть общие переменные а и с/, поэтому вместо минтермов т_ъ, т₅, т₇ остается импликанта ad, размерность которой меньше, чем размерность склеиваемых минтермов, на 2.

К истинному контуру предъявляется еще одно важное требование. Из рис. 23 видно, что при увеличении п на 1 каждое новое поле карты Карно получается из двух субполей предыдущей размерности. Истинный контур всегда симметричен относительно одной из центральных осей (горизонтальной или вертикальной, см. рис. 23, п = 5) или полностью размещается в одном из субполей симметрично относительно одной из его осей. На этом же рисунке показано два истинных контура (контур 1, состоящий из восьми и контур 2 — из четырех клеток) и два ложных (3 — из восьми и 4 — из четырех клеток).

На рис. 25 для примера показаны шесть заполненных карт Карно с выделенными контурами, из которых следует запись функций в ДНФ.

Рис. 25. Примеры карт Карно для различных функций с указанием секторов для Функций:

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

Здесь наглядно демонстрируется, что в релейно-контактном исполнении в первом случае понадобилось бы 10 контактов, а во втором случае после преобразования — 8 контактов. В функции/₃ также можно сэкономить на одном контакте, если записать.

Опишем полезный прием работы с картой Карно, в котором используется дополняющий минтерм. Пусть до полного истинного контура не хватает одной единицы, т. е. одного минтерма, как это показано на рис. 26. Если бы функция содержала минтерм /и, то согласно обведенному контуру/+ /и,₃ = а. Сама функция/описывается заштрихованным полем.

Рис. 26. Использование дополняющего минтерма В общем виде можно записать.

где к — импликанта, описывающая содержание контура. Из карты Карно видно, чтоf=k + /77,. Следовательно, согласно закону Де Моргана.

Функция равна содержанию контура к, и дополняющий минтерм /и, при этом должен отсутствовать. В нашем примере.

Продолжая преобразования, получим.

Иногда приходится решать обратную задачу. Если функция записана в ДНФ, то необходимо перейти к СДНФ. Пусть дана функция.

Первому члену ab соответствуют четыре единицы контура 1 (рис. 27). Второму члену соответствуют четыре единицы контура 2, члену acd — две единицы контура 3.

Рис. 27. Переход от ДНФ к СДНФ.

Учитывая, что многократное повторение одного и того же минтерма /и, тождественно однократной записи m_h можно записать функцию ср в СДНФ, перечислив все минтермы согласно клеткам, в которых встречается хотя бы одна единица. В нашем примере.

Проиллюстрируем процедуру синтеза логического автомата на следующей задаче: требуется построить автомат, фиксирующий принятие решения в результате голосования по мажоритарному принципу, для работы комиссии из четырех человек a, b, с, d, в которой председатель а имеет два голоса. Таблица истинности и карта Карно приобретают вид, показанный на рис. 28.

Рис. 28. Мажоритарный автомат: а — таблица истинности; б — карта Карно Запишем функцию через два контура аире исключением дополняющего минтерма т_н (правая верхняя клетка карты Карно)

Структурная схема автомата и его релейно-контактное исполнение показаны на рис. 29.

Рис. 29. Автомат для голосования:

а — реализация в базисе «И—ИЛИ—НЕ»; б — релейная интерпретация.