Минимизация функций с использованием карт Карно

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

Таблица кода Грея для двоичных чисел длиной в два разряда

В двоичном коде переход от 1 к 2 сопровождается изменением 01→10 логической переменной сразу в двух разрядах, а в коде Грея – в одном.

При заполнении карты Карно в ее клетки заносятся значения функции f(X), которые соответствуют набору переменных на пересечении столбца и строки. Пример карты Карно для логической функции трех переменных приведен на рис.3.

Рис.3

Единичные значения функции у₁ соответствуют наборам х₁,х₂х₃= 110, 001, 101, 111.

Для минимизации логической функции в виде СДНФ выделяют прямоугольные области клеток заполненные единицами. Каждая сторона области должна состоять из 2^K клеток, где K — целое число (2^К=1;2;4;8;...). Для такой области вместо составления элементарных конъюнкций на каждую единицу можно обойтись одной общей конъюнкцией на всю областьсразу. С этой целью для каждой области составляется комбинация аргументов, которая однозначно определяет эту область. Разряды, которые в пределах области меняют свои значения, отмечаются символом (*), как на рис.4. Очевидно, что изменение этих разрядов в пределах области не меняет значения функции. Так как изменение этих разрядов не влияет на функцию y, можно не учитывать их в конъюнкции области.

Рис.4. Получение МДНФ с использованием карты Карно

При минимизации этой логической функции получаем три области единиц. Первой области соответствует набор1*1*, второй области - набор1*00, третьей области – 01*0. Здесь разряды, которые можно удалить, заменены звёздочками. Третья область образуется крайними клетками второго столбца таблицы, так как крайние клетки столбцов и таблиц считаются соседними, потому что они тоже могут склеиваться.

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

.

Чтобы получить минимальную КНФ в карте Карно аналогичными прямоугольными областями охватываются нулевые клетки, и также записываются наборы, соответствующие охваченным областям.

Получение МКНФ с использованием карты Карно показано на рис.5.

Рис.5

Для каждой области составляют элементарную дизъюнкцию, используя необходимые инверсии на её входах. Первой области соответствует набор 01*, дизъюнкция (х₁ v ); второй области — набор *00, дизъюнкция (x₂ v x₃). МКНФ функции запишем в виде

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

На практике применяют и другие методы, минимизации логических функций — метод Петрика, метод карт Вейча. Однако многие методы пригодны для числа переменных до 5. При увеличении числа переменных они становятся громоздкими, теряют наглядность. Кроме того, выбор областей в этих методах в большинстве случаев проводится интуитивно, сильно зависит от индивидуального опыта и искусства разработчика, что препятствует автоматизации проектирования и применения на ЭВМ.