Минимизация: карты Карно

Урок о том, как из громоздкой СДНФ получить короткую формулу — наглядно, с помощью клетчатой карты.

Карта Карно — это таблица истинности, перерисованная так, что любые два соседних набора отличаются ровно одной переменной. Это позволяет «склеивать» единицы и убирать лишние переменные.

СДНФ всегда правильна, но часто избыточна: в ней может быть много длинных слагаемых, хотя функция реализуется куда проще. Минимизация — это поиск самой короткой эквивалентной формулы. Картой Карно её делают вручную для 2–4 переменных быстро и наглядно.

Зачем это нужно

Короткая формула — это меньше логических элементов в схеме, дешевле и быстрее устройство, проще понять и проверить выражение. Сравните: СДНФ из четырёх трёхбуквенных конъюнкций против ответа вида $A \lor \neg B$. Обе задают одну функцию, но вторая очевидно лучше. Алгебраическое упрощение по законам логики работает, но требует догадки, какой закон применить. Карта Карно делает это механически и наглядно.

Идея: склеивание

В основе минимизации лежит закон склеивания:

$$ (X \land A) \lor (X \land \neg A) = X $$

Если функция истинна и при $A$, и при $\neg A$ (а остальное $X$ одинаково), то от $A$ значение не зависит — её можно выбросить. Карта Карно расставляет наборы так, чтобы склеиваемые пары стояли рядом и их было видно глазами.

Карта для двух переменных

Для функции $F(A, B)$ карта — это квадрат $2 \times 2$: столбцы по $A$, строки по $B$. Возьмём функцию, истинную в строках $(0,1)$, $(1,0)$, $(1,1)$ — то есть «$A$ ИЛИ $B$»:

Ищем прямоугольные группы из единиц размером 1, 2, 4 клетки. Здесь видны две двойки:

• Правый столбец (обе клетки при $A=1$): внутри него $B$ меняется с 0 на 1, а $A=1$ постоянна → группа даёт просто $A$.
• Нижняя строка (обе клетки при $B=1$): внутри $A$ меняется, $B=1$ постоянна → группа даёт $B$.

Объединяем покрытие через ИЛИ:

$$ F = A \lor B $$

Что и требовалось — мы получили $A \lor B$ напрямую, минуя длинную СДНФ.

Карта для трёх переменных

Для $F(A, B, C)$ карта — прямоугольник $2 \times 4$. Ключевой момент — порядок столбцов: $AB = 00, 01, 11, 10$ (так называемый код Грея). Соседние столбцы отличаются одной переменной, и крайние столбцы ($00$ и $10$) тоже соседние — карта «заворачивается» по горизонтали в кольцо.

Возьмём функцию, истинную на наборах $(0,0,1)$, $(0,1,1)$, $(1,1,1)$, $(1,0,1)$ — то есть везде, где $C=1$:

Все четыре единицы лежат в одной строке $C=1$ — это группа из 4 клеток. Внутри неё $A$ и $B$ пробегают все комбинации, значит от них функция не зависит, а $C=1$ постоянна. Результат:

$$ F = C $$

СДНФ этой функции содержала бы четыре трёхбуквенных слагаемых, а карта Карно сразу даёт ответ в одну букву.

Правила группировки

• Группы — только прямоугольники со степенями двойки клеток: 1, 2, 4, 8.
• Чем больше группа, тем короче слагаемое: группа из 2 убирает 1 переменную, из 4 — 2 переменные.
• Группы могут пересекаться; каждую единицу нужно покрыть хотя бы раз.
• Карта заворачивается: левый и правый края соседние (а для карт 4×4 — и верх с низом).

Как это работает

Группа из двух соседних единиц — это пара наборов, отличающихся одной переменной. Их минтермы склеиваются по закону выше, и отличающаяся переменная исчезает. Группа из четырёх — это два склеивания подряд, уходят две переменные. Проверим минимизацию «все единицы при $C=1$» программой: сравним короткую формулу $F = C$ с исходной таблицей.

truth = {
    (0,0,0):0, (0,0,1):1, (0,1,0):0, (0,1,1):1,
    (1,0,0):0, (1,0,1):1, (1,1,0):0, (1,1,1):1,
}

def minimized(a, b, c):
    return c == 1   # карта Карно дала F = C

ok = True
for a, b, c in sorted(truth):
    got = int(minimized(a, b, c))
    print((a, b, c), 'F=C ->', got, '| таблица', truth[(a, b, c)])
    if got != truth[(a, b, c)]:
        ok = False
print('Совпадает со всей таблицей:', ok)

Вывод:

(0, 0, 0) F=C -> 0 | таблица 0
(0, 0, 1) F=C -> 1 | таблица 1
(0, 1, 0) F=C -> 0 | таблица 0
(0, 1, 1) F=C -> 1 | таблица 1
(1, 0, 0) F=C -> 0 | таблица 0
(1, 0, 1) F=C -> 1 | таблица 1
(1, 1, 0) F=C -> 0 | таблица 0
(1, 1, 1) F=C -> 1 | таблица 1
Совпадает со всей таблицей: True

Короткая формула $F = C$ воспроизвела все восемь строк — минимизация корректна.

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

• Неправильный порядок столбцов. Если расставить $AB$ как $00, 01, 10, 11$, соседи перестанут отличаться одной переменной и склеивание сломается. Только код Грея: $00, 01, 11, 10$.
• Группы не степени двойки. Нельзя взять группу из 3 клеток. Только 1, 2, 4, 8.
• Забывают про заворачивание. Единицы в крайнем левом и крайнем правом столбцах склеиваются — это легко упустить.
• Берут мелкие группы. Всегда выгоднее одна большая группа, чем несколько мелких: формула короче.

Итоги

• Карта Карно располагает наборы по коду Грея — соседи отличаются одной переменной.
• Соседние единицы склеиваются, лишняя переменная пропадает: $(X \land A) \lor (X \land \neg A) = X$.
• Группы — прямоугольники из 1, 2, 4, 8 клеток; чем больше, тем короче слагаемое.
• Карта заворачивается по краям; группы могут пересекаться, но каждую единицу надо покрыть.
• Результат — минимальная ДНФ, дешевле и понятнее исходной СДНФ.