Как построить карту Карно: решение по шагам

Дано: булева функция четырёх переменных $F(A,B,C,D)$, равная единице на наборах с номерами 0, 1, 2, 5, 8, 9, 10, 13, 15 и нулю на остальных семи. Найти: минимальную дизъюнктивную нормальную форму, построив карту Карно.

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

$$F = (\neg B \wedge \neg D) \vee (\neg C \wedge D) \vee (A \wedge B \wedge D).$$

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

Решение по шагам

Шаг 1. Разметить оси кодом Грея. Карта на четыре переменные - это таблица 4 на 4. По вертикали откладывают пару $AB$, по горизонтали пару $CD$, но не в обычном порядке 00, 01, 10, 11, а в порядке 00, 01, 11, 10. Такой порядок называют кодом Грея: в нём каждый следующий код отличается от предыдущего одним разрядом, и первый с последним тоже. Именно из-за этого сдвига соседство на карте совпадает с соседством наборов.

Номер клетки собирается из битов: старшие два разряда берутся из строки, младшие два из столбца. Получается вот такая сетка номеров.

Шаг 2. Перенести значения из таблицы истинности. Сначала выписываем саму таблицу: шестнадцать наборов, в девяти из них функция истинна.

Теперь каждая единица ложится в свою клетку сетки из шага 1. Карта заполнена:

Шаг 3. Обвести максимальные группы единиц. Группа - это прямоугольник из 1, 2, 4, 8 или 16 клеток, в котором стоят одни единицы, причём карта считается склеенной в кольцо по обеим осям: левый столбец соседствует с правым, верхняя строка с нижней. Берут всегда самый большой прямоугольник, какой удаётся натянуть, потому что чем он больше, тем короче конъюнкция.

На нашей карте находится четыре максимальных прямоугольника.

Первая группа - те самые четыре угла: они соседние как раз потому, что края карты склеены. Четвёртая группа тоже заворачивается, но по вертикали: строки $AB = 00$ и $AB = 10$ примыкают друг к другу.

Шаг 4. Выбросить лишнюю группу. Прямоугольников четыре, а в ответ идут не все. Смотрим, какие клетки покрыты единственным способом. Клетки 2 и 10 входят только в группу углов, клетки 5 и 13 только в столбец, клетка 15 только в пару. Значит, эти три группы обязательны. А вот квадрат 0, 1, 8, 9 обязательным не оказался: клетки 0 и 8 уже забраны углами, клетки 1 и 9 столбцом. Он ничего не добавляет к покрытию и в минимальную форму не входит.

Шаг 5. Записать ответ. Складываем конъюнкции трёх обязательных групп по дизъюнкции:

$$F = (\neg B \wedge \neg D) \vee (\neg C \wedge D) \vee (A \wedge B \wedge D).$$

Ответ: $F = \neg B \wedge \neg D \vee \neg C \wedge D \vee A \wedge B \wedge D$, три конъюнкции и семь вхождений переменных.

Формула и откуда она берётся

За всей картой стоит один закон - склеивание: $(X \wedge \neg Y) \vee (X \wedge Y) = X \wedge (\neg Y \vee Y) = X$. Если две полные конъюнкции отличаются ровно одной переменной, эта переменная выносится за скобку и исчезает, потому что вместе со своим отрицанием даёт тождественную единицу.

Карта Карно - это способ увидеть такие пары глазами, не перебирая формулы. Код Грея по осям устроен так, что горизонтальные и вертикальные соседи всегда отличаются одним битом. Поэтому прямоугольник из двух клеток убирает одну переменную, из четырёх - две, из восьми - три. В группе остаются только те переменные, которые внутри неё не меняются, и берутся они с отрицанием, если равны нулю.

Проверим на столбце: клетки 1, 5, 9, 13 в двоичной записи это 0001, 0101, 1001 и 1101. Переменные $A$ и $B$ пробегают все четыре комбинации, а $C$ всюду равна нулю и $D$ всюду единице. Отсюда и конъюнкция $\neg C \wedge D$ - ровно то, что выдаёт таблица шага 3.

Исходной точкой обычно служит совершенная дизъюнктивная нормальная форма: в ней по одной конъюнкции из всех четырёх переменных на каждую единицу таблицы. Карта Карно ничего не изобретает - она просто показывает, какие из этих девяти конъюнкций можно попарно склеить и до какого предела процесс доходит.

Карты на два, три и пять переменных

Для двух переменных карта вырождается в квадрат 2 на 2, и минимизация там очевидна без всякой техники. Для трёх переменных карта становится полосой 2 на 4: по вертикали одна переменная, по горизонтали пара в коде Грея. Склейка через левый и правый края работает и здесь, а вот по вертикали заворачивать нечего - строк всего две.

Пять переменных рисуют двумя картами 4 на 4 рядом: одна для $E = 0$, другая для $E = 1$. Клетки с одинаковыми координатами на разных картах считаются соседними, и группа может лежать на обеих сразу. С шести переменных метод теряет смысл: увидеть соседство в четырёх слоях человек уже не может, и задачу передают алгоритму Квайна и Мак-Класки, который делает то же самое перебором, а не глазами.

Отдельный случай - неопределённые значения, их помечают крестиком. Такую клетку разрешено включать в группу, если это укрупняет прямоугольник, и разрешено игнорировать, если пользы нет. Крестик, не вошедший ни в одну группу, никаких обязательств не создаёт.

Проверка ответа

Ответ проверяют подстановкой, и достаточно двух-трёх наборов, выбранных с умом. Берём набор 10, то есть $A = 1$, $B = 0$, $C = 1$, $D = 0$: первое слагаемое даёт $\neg B \wedge \neg D = 1 \wedge 1 = 1$, значит вся дизъюнкция истинна. В таблице на этом наборе тоже единица.

Теперь набор 7, где $A = 0$, $B = 1$, $C = 1$, $D = 1$. Первое слагаемое обнуляется из-за $B = 1$, второе из-за $C = 1$, третье из-за $A = 0$. Получается ноль - и в таблице ноль. Полезно проверять именно граничные наборы: тот, что попал в спорную группу, и тот, что лежит вплотную к ней.

Второй способ проверки - счёт. В совершенной ДНФ девять конъюнкций по четыре буквы, всего тридцать шесть вхождений переменных; в найденной форме семь. Если после минимизации букв стало не меньше, значит где-то взяты не максимальные прямоугольники. Механику самих преобразований без карты разбирает страница как упростить логическое выражение, а построение самой таблицы истинности - отдельный разбор.

Частые ошибки

• Оси размечены в обычном двоичном порядке 00, 01, 10, 11. Тогда соседние клетки отличаются двумя битами, склейка даёт неверные конъюнкции, и ответ не совпадёт с таблицей ни на одном наборе.
• Забыли про склейку через край. Четыре угла 0, 2, 8, 10 выглядят разрозненными, и их обводят четырьмя одиночными клетками. Вместо двух букв получается шестнадцать.
• Взяли все найденные прямоугольники. Группа $\neg B \wedge \neg C$ на этой карте максимальна, но избыточна: её клетки уже покрыты. Лишнее слагаемое не делает формулу ложной, но минимальной она уже не будет.
• Группа не степени двойки. Прямоугольник из трёх или шести клеток обвести нельзя: сокращение переменных работает только при размере 1, 2, 4, 8 или 16.
• Перепутан порядок разрядов при нумерации. Если считать старшим разряд $D$, а не $A$, карта заполнится другими единицами, и ответ будет верным для другой функции.
• Переменная взята без отрицания. Внутри группы углов $B = 0$ и $D = 0$, поэтому в конъюнкцию идут $\neg B$ и $\neg D$; ноль означает отрицание, а не пропуск переменной.

FAQ

Сколько групп должно получиться? Столько, сколько нужно, чтобы накрыть все единицы, и ни одной сверх того. Сначала выписывают все максимальные прямоугольники, затем оставляют обязательные - те, в которых есть клетка, не покрытая ничем другим. Если после этого остались непокрытые единицы, к ним добирают самые крупные из оставшихся групп.

Бывает ли несколько правильных ответов? Да. Здесь минимальная форма единственна, но если минимизировать по той же карте нули этой функции, минимальных вариантов окажется два и они одинаковой длины. Оба верны, выбирать можно любой.

Чем карта Карно отличается от метода Квайна и Мак-Класки? Ничем по сути: оба ищут простые импликанты и минимальное покрытие. Карта делает это наглядно и быстро до четырёх-пяти переменных, метод Квайна формально и без ограничения на число переменных, зато вручную он гораздо длиннее.

Как по карте получить МКНФ, а не МДНФ? Склеивать нули вместо единиц, записать минимальную ДНФ для инверсии функции, а потом применить к ней закон де Моргана. Получится произведение дизъюнкций - минимальная конъюнктивная форма.

Коротко

1. Начертить таблицу 4 на 4, разметить строки парой $AB$, столбцы парой $CD$ и обязательно в порядке 00, 01, 11, 10.
2. Перенести единицы из таблицы истинности в клетки с соответствующими номерами; для нашей функции это клетки 0, 1, 2, 5, 8, 9, 10, 13, 15.
3. Обвести максимальные прямоугольники из единиц размера 1, 2, 4, 8, помня, что края карты склеены по обеим осям. Их здесь четыре.
4. Оставить только обязательные группы - те, где есть клетка, не покрытая другими. Квадрат 0, 1, 8, 9 отбрасывается как избыточный.
5. Сложить конъюнкции обязательных групп: $F = (\neg B \wedge \neg D) \vee (\neg C \wedge D) \vee (A \wedge B \wedge D)$, семь букв вместо тридцати шести.