Мастерство упрощения логики с картами Карно

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

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

Карты Карно и последовательность кода Грея

Наша карта Карно использует стандартную раскладку кода Грея:

Обратите внимание на заголовки верхней строки: 00, 01, 11, 10. Эта последовательность кода Грея меняет только один бит между соседними столбцами (и строками), обеспечивая соседство ячеек, отличающихся одной переменной. Это свойство смежности позволяет визуально находить общие множители.

Генерация кода Грея для карты любого размера

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

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

Примеры упрощения с 3-переменными картами Карно

Упростим несколько функций, используя 3-переменную K-карту. Сначала ставим 1, соответствующие каждому слагаемому-произведению, затем группируем смежные ячейки для получения выражения в форме Суммы Произведений.

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

Аналогично, другой набор из четырех термов сокращается к единственной переменной C:

При шести слагаемых-произведениях часто получаются две отдельные группы по четыре ячейки. Каждая группа дает отдельное слагаемое-произведение, результат — упрощенное выражение вроде A' + B:

Другой пример показывает группу из двух ячеек, сокращающуюся к BC:

В некоторых случаях заворачивание краев карты (представление её как цилиндра) раскрывает группу из четырех, сокращающуюся к единственной переменной B:

Когда все четыре ячейки разделяют переменную C', итоговый результат — просто C':

Группируя шесть ячеек в две группы по четыре, получаем лаконичное выражение A' + C'.

Упрощение булевых уравнений картами Карно: Токсичный сжигатель отходов

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

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

Для сравнения повторяем упрощение булевой алгеброй:

И решение картой Карно рядом:

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

СВЯЗАННЫЕ РАБОЧИЕ ЛИСТЫ:

• Рабочий лист по картам Карно