Мастерство карт Карно: упрощение логики с таблицами истинности и булевыми выражениями

Кто создал карту Карно?

Морис Карно, инженер по телекоммуникациям в Bell Labs, ввел карту Карно в 1953 году при проектировании цифровой логики для телефонных коммутационных схем.

Зачем использовать карту Карно?

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

На практике инженеры предпочитают карты Карно булевой алгебре для упрощения, как только понимают, как читать диаграмму.

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

Связь таблиц истинности с картами Карно

Для двух входов A и B каждый может быть 0 или 1, давая 2² = 4 выходных комбинации. Карта Карно переупорядочивает таблицу истинности в квадратную сетку, где соседние ячейки отличаются только одной переменной, делая паттерны очевидными.

Каждому выходу таблицы истинности соответствует конкретная ячейка K-карты. Например, выход α для A=0, B=0 появляется в левом верхнем углу карты. То же отображение для β, χ, δ.

Смежность в K-карте (по горизонтали или вертикали) указывает на общие булевы переменные. Ячейки α и χ делят B′, β и δ — B, α и β — A′, χ и δ — A. Узнавание этих отношений позволяет быстро группировать и упрощать.

Практические примеры

1. Перенос таблицы истинности в карту Карно

Решение: найдите две строки с «1» в таблице истинности, поставьте «1» в соответствующие ячейки K-карты, затем сгруппируйте их.

2. Получение булева выражения из K-карты

Решение: сгруппируйте смежные «1», сохраните переменные, постоянные внутри группы, отбросьте остальные. Для примера выражение: Out = B.

3. Множественная группировка для минимальной стоимости

Решение: сгруппируйте две «1» горизонтально, получая Out = A′.

4. Комбинирование групп через карту

Решение: после переноса таблицы истинности сгруппируйте вертикально для Out = B и горизонтально для Out = A. Финальное выражение: Out = A + B, простейшая форма.

5. Работа с перекрывающимися группами

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

Упрощение реальных логических диаграмм

Пример 1:

Процесс: переведите исходную схему в булево выражение, отобразите слагаемые-произведения на K-карте, сгруппируйте ячейки, получите упрощенное выражение, перерисуйте минимизированную схему.

Пример 2 — упрощение невозможно:

В некоторых случаях карта показывает, что логика уже минимальна. Даже повсеместный гейт исключающего ИЛИ (7486) часто оставляют без изменений, так как его нельзя упростить дальше.

Дополнительные ресурсы

• Рабочий лист по картам Карно
• Рабочий лист по булевой алгебре
• Рабочий лист по базовым логическим гейтам