Решатель карты Карно (K-Map)

Упрощение булевых функций с помощью карты Карно

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

Solver работает с функциями от 2 до 5 переменных. Начать можно с самой K-Map, таблицы истинности, булева выражения, минтермов или макстермов.

Все способы ввода описывают одну и ту же функцию. Изменение в одном представлении автоматически отражается в остальных.

Что означают 0, 1 и X?

Ячейка может содержать:

• 1, если функция истинна;
• 0, если функция ложна;
• X, если значение выхода несущественно.

X обозначает безразличное состояние. Его можно включить в группу, если это позволяет получить более простое выражение. Использовать такой элемент обязательно не требуется.

От таблицы истинности к карте Карно

Таблица истинности перечисляет все возможные комбинации входных переменных.

Карта Карно содержит те же данные, но располагает комбинации в порядке кода Грея. Поэтому соседние ячейки отличаются только одной переменной.

Например:

A'B'

A'B

В этих двух термах меняется только B.

После объединения остаётся:

A'

Переменная, которая меняет своё значение внутри группы, исключается из упрощённого терма.

На том же принципе основаны группы из 4, 8 и большего числа ячеек.

Минтермы, макстермы и булевы выражения

Если функция уже задана индексами, заполнять каждую ячейку вручную не нужно.

Например:

Σm(1,3,5,7)

задаёт минтермы — комбинации, для которых функция равна 1.

Запись:

ΠM(0,2,4,6)

задаёт макстермы, соответствующие выходу 0.

Можно также ввести булево выражение напрямую. Solver вычислит его значения и построит соответствующие представления функции.

Это удобно, когда нужно проверить связь между выражением, таблицей истинности, K-Map, минтермами и макстермами.

Правила группировки на карте Карно

Размер правильной группы всегда является степенью двойки:

1, 2, 4, 8, 16

Чем больше допустимая группа, тем больше изменяющихся переменных обычно удаётся убрать.

Края карты Карно логически соединены между собой.

Левая и правая стороны считаются соседними. То же самое относится к верхнему и нижнему краю.

Поэтому четыре угловые ячейки тоже могут образовать одну группу.

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

Solver выделяет выбранные области непосредственно на карте.

SOP и POS

В форме SOP (Sum of Products) рассматриваются прежде всего комбинации, где функция равна 1.

Пример:

A'B + BC

В форме POS (Product of Sums) группируются комбинации с выходом 0.

Например:

(A + B')(B + C)

Нельзя заранее сказать, какая из форм всегда будет короче.

Для одной функции проще может оказаться SOP, а для другой — POS.

Если условие задачи не требует конкретной формы, полезно сравнить оба результата.

Quine-McCluskey и Petrick's Method

При небольшом количестве переменных подходящие группы часто хорошо видны на карте.

При 4 или 5 переменных возможных вариантов покрытия становится больше.

Solver применяет Quine-McCluskey, чтобы систематически находить простые импликанты функции.

Простой импликант нельзя расширить, не включив недопустимую комбинацию.

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

Если после их выбора остаётся несколько вариантов, Petrick's Method используется для анализа оставшихся покрытий.

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

Карты Карно для 2–5 переменных

Карта для 2 переменных содержит 4 ячейки.

При 3 переменных получается 8 ячеек, и становится заметнее связь противоположных краёв.

4-переменная карта Карно содержит 16 ячеек и часто используется в задачах по цифровой логике.

Для 5 переменных существует уже 32 входные комбинации. Ручная проверка становится сложнее, особенно при наличии безразличных состояний.

Во всех режимах карта, таблица истинности, выражение, минтермы и макстермы остаются синхронизированными.

Логическая схема и PDF

После минимизации выражение можно представить в виде логической схемы.

Это помогает увидеть, как результат реализуется с помощью элементов AND, OR и NOT.

Solver также показывает количество термов, литералов и логических элементов.

Полное решение можно экспортировать в PDF вместе с картой Карно, выделенными группами, этапами решения и схемой.