Рассмотрим правила минимизации с использованием карт Карно.
1. В карте Карно группы единиц (для получения ДНФ) и группы нулей (для получения КНФ) необходимо обвести четырехугольными контурами. Внутри контура должны находится только одноименные значения функции. Данный процесс соответствует операции склеивания или нахождения импликант функции.
2. Количество клеток внути контура должно быть целой степенью двойки (1, 2, 4, 8, 16...).
3. При проведении контуров, крайние строки карты (верхние и нижние, левые и правые), а также угловые клетки, считаются соседними (для карт до четырех переменных).
4. Каждый контур должен включать максимально возможное количество клеток. В этом случае, он будет соответствовать простой импликанте.
5. Все единицы (нули) в карте (даже одиночные) должны быть охвачены контурами. Любая единица (нуль) может входить в контуры произвольное количество раз.
6. Множество контуров, покрывающих все 1 (0) функции, образуют тупиковую ДНФ (КНФ). Целью минимизации является нахождение минимальной формы из множества тупиковых форм.
7. В элементарной конъюнкции (дизъюнкции), которая соответствует одному контуру, остаются только те переменные, значение которых не изменяется внутри обведенного контура.
Переменные булевой функции входят в элементарную коньюнкцию (для значений функции 1) без инверсии, если их значение на соответствующих координатах равно 1, и с инверсией - если 0.
Для значений булевой функции, равных 0, записываются элементарные дизьюнкции, куда переменные входят без инверсии, если их значение на соответствующих координатах равно 0, и с инверсией - если 1.
Если рассматривать запись результатов минимизации в кубическом виде, то, при минимизации булевой функции по единичным значениям, каждой конъюнкции ранга R соответствует куб ранга R, где каждой переменной без инверсии соответствует 1 в кубе, переменной с инверсией - 0, а на месте отсутствующей переменной ставиться X.
Полученное множество кубов образует единичное покрытие C1 (соответствующее ДНФ).
При минимизации булевой функции по нулевым значениям и представлении результатов минимизации в кубическом виде, нулевое покрытие C0 формируется на основе обратной ДНФ , которая является инверсной функцией по отношению к КНФ.
Отметим, что обратная ДНФ строится на основе КНФ.
Таким образом каждой дизъюнкции ранга R (из КНФ) соответствует куб ранга R, где каждой переменной без инверсии соответствует 0 в кубе, переменной с инверсией - 1, а на месте отсутствующей переменной ставится X.
Полученное множество кубов образует нулевое покрытие C0.
При данном способе задания, таблица истинности функции представляется в виде координатной карты состояний, которая содержит 2n клеток (по числу входных наборов булевой функции n переменных).
Переменные функции разбиваются на две группы так, что одна группа определяет координаты столбца карты, а другая - координаты строки.
При такoм способе построения, каждая клетка определяется значениями переменных, соответствующих определенному двоичному набору.
Внутри каждой клетки карты Карно ставится значение функции на данном наборе.
Переменные в строках и столбцах располагаются так, чтобы смежные клетки карты Карно различались только в одном разряде переменных, то есть были соседними. Поэтому значения переменных в столбцах и в строках карты образуют соседний код Грея.
Такой способ представления очень удобен для наглядности при минимизации булевых функций.
Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из Белл Лабс.
Метод карт Карно применим к минимизации булевых функций до 6-ти переменных (до 4 переменных на плоскости и до 6 переменных в трехмерной интерпретации).
Если требуется получить карту Карно для какой-либо функции, сначала надо записать эту функцию в СДНФ (совершенной дизъюнктивно нормальной форме) или в виде таблицы истинности.
Каждое слагаемое булева выражения в СДНФ, или каждая единица в столбце функции таблицы истинности, задается на карте Карно единицей в соответствующей клетке. Координаты этой клетки содержат те же входные переменные и их инверсии, что и данное слагаемое СДНФ булева выражения ( или данная строка таблицы истинности ).
Taблица истинности для четырех переменных включает 16 строк, следовательно, карта Карно должна состоять из 16 клеток, как показано на рисунке:
У карты Карно для четырех переменных, клетки крайнего левого столбца должны рассматриваться как соседние для клеток крайнего правого столбца, а клетки верхней строки – как соседние для клеток нижней строки.
Другими словами, данная карта расположена на поверхности цилиндра (правый край карты склеен с левым), изогнутого и растянутого так, что верхний срез соединяется с нижним срезом, а цилиндр превращается в тор (бублик).
Правила упрощения заполненной карты Карно для четырех переменных заключаются в следующем :
– соседние две, четыре, или восемь единиц обводят общим контуром;
– контур должен быть прямоугольным без изгибов или наклонов;
– каждый контур превращает все входящие в него единицы в одну, то есть объединенные таким образом слагаемые СДНФ булева выражения дают одно слагаемое в упрощенном выражении;
– те входные переменные, которые входят в координаты данного контура совместно со своими инверсиями, исключаются из слагаемого, которое дает данный контур в упрощенное выражение.
Рассмотрим пример упрощения булевых выражений с помощью карты Карно:
В данном примере минимизации булевой функции F1, нижний контур из двух единиц 15 и 16 , соответствующих пятому и шестому слагаемым в исходном булевом выражении, дает возможность опустить B и`B, после чего в нем остается произведение `A C`D.
В верхнем контуре из четырех единиц 11, 12, 13 и 14 , соответствующих первым четырем слагаемым исходного булева выражения, попарно опускаются A и`A, D и`D, так что в результате верхний контур дает произведение B C.
Рассмотрим еще один пример упрощения булевых выражений с помощью карты Карно:
В данном примере минимизации булевой функции F2, контур из двух единиц 12 и 13 , соответствующих второму и третьему слагаемым в исходном булевом выражении, дает возможность опустить А и`А, после чего в нем остается произведение B`C`D.
В контуре из четырех единиц 11, 12, 14 и 15 , соответствующих другим четырем слагаемым из исходного булева выражения, попарно опускаются В и`В, С и`С, так что в результате этого верхний контур дает произведение `A`D.
Карта Карно представляется в данном случае свернутой в цилиндр, в котором верхний край совмещается с нижним. Данный пример показывает также, что контуры могут накладываться друг на друга.