Решатель карт Карно
Бесплатный онлайн-решатель карт Карно: введите булево выражение от двух до шести переменных и получите его карту с обведённой каждой группой и прочитанной по ней минимальной суммой произведений или произведением сумм.
Введите логическое выражение для его анализа (поддерживает пропозициональную логику, булеву алгебру)
Руководство
Нажмите на оператор, чтобы выполнить его пример в калькуляторе. Для каждого показаны все способы ввода.
Введите выражение, и этот решатель карт Карно разложит его значения истинности по сетке в коде Грея, обведёт каждую группу, которую можно объединить, и прочитает по ним минимальную форму. Он принимает символы (¬ ∧ ∨ → ↔) и обычный ASCII (!, &, |, ->, <->), работает с двумя-шестью переменными и находит точный минимум, а не просто хороший. Ничего никуда не отправляется: карта строится в вашем браузере.
Как решить карту Карно
- Введите выражение в поле выше - например, (A & B) | (!A & C). Клавиатура операторов вставит символы, если набирать их вручную не хочется.
- Решатель читает переменные из выражения и раскладывает значения истинности по сетке. Оси закодированы кодом Грея (00, 01, 11, 10), поэтому соседние клетки различаются ровно одной переменной - именно поэтому их группа сворачивается в один терм.
- Каждое цветное кольцо - это группа. Наведите курсор или коснитесь группы в легенде, чтобы выделить её на карте, и обратите внимание на помеченные как существенные: их не может опустить никакая минимальная форма. Группа может огибать края карты, а клетка может входить сразу в несколько групп.
- Прочитайте минимальную форму ниже. Переключайтесь между суммой произведений и произведением сумм, копируйте результат, загружайте его обратно в калькулятор или экспортируйте карту в LaTeX или TikZ.
Что даёт решатель
- Каждая группа обведена и раскрашена, существенные помечены, и у каждой указан терм, который она оставляет.
- Минимальная форма, которая действительно минимальна: покрытие ищется точно, а не выбирается жадно, поэтому даже циклическая карта выходит кратчайшей.
- Сумма произведений или произведение сумм - группировать единицы или нули - по одной и той же карте.
- Карта в LaTeX: простой таблицей или перерисованной в TikZ с кольцами и легендой.
- А ещё таблица истинности, свойства и эквивалентные формы, если открыть то же выражение в полном калькуляторе.
Разобранный пример
Карта для (((A∧B)∧C)∨((A∧B)∧¬C))∨((¬A∧B)∧C). Истинны три клетки, и их покрывают две группы по две, пересекающиеся в одной из них, - весь метод в миниатюре: переменная, которая меняется внутри группы, выпадает из её терма, а клетка может быть покрыта дважды.
Карта Карно
Каждая цветная группа покрывает прямоугольник истинных клеток. Переменные, которые меняются внутри группы, выпадают, поэтому каждая группа оставляет одну конъюнкцию. Как читать эту карту →
| ABC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | ⊥ | ⊥ | ⊤ | ⊥ |
| 1 | ⊥ | ⊥ | ⊤ | ⊤ |
Группы
Сколько переменных может быть у карты Карно?
Этот решатель строит карты для 2-6 переменных. Меньше 2 - нечего группировать; пять и шесть рисуются как две или четыре сложенные плоскости, а больше 6 и это перестаёт читаться легче, чем таблица истинности рядом. Для большего числа переменных эквивалентные формы калькулятора всё равно дадут минимизированную ДНФ.
| Переменные | Клетки | Сетка |
|---|---|---|
| 2 | 4 | 2 × 2 |
| 3 | 8 | 2 × 4 |
| 4 | 16 | 4 × 4 |
| 5 | 32 | 2 × (4 × 4) |
| 6 | 64 | 4 × (4 × 4) |
Сумма произведений и произведение сумм
Группировка истинных клеток даёт сумму произведений: по одной конъюнкции на группу, соединённых ИЛИ. Группировка ложных даёт произведение сумм с отрицанием литералов на выходе: по одной дизъюнкции на группу, соединённых И. Обе описывают одну и ту же функцию, а какая короче - зависит от того, единицы или нули складываются в более аккуратные прямоугольники. Поэтому решатель даёт обе, а вы берёте меньшую.
Часто задаваемые вопросы
Ответы на распространённые вопросы о работе с Логическим калькулятором
Сколько переменных может быть у карты Карно?
Этот решатель строит карты для двух-шести переменных: две дают сетку 2 × 2, три - 2 × 4, четыре - 4 × 4. Пять и шесть рисуются так же, как их рисуют учебники: как два или четыре наложенных слоя 4 × 4, где клетки на одном и том же месте соседних слоёв считаются соседними, - группа, не упоминающая переменные наложения, оказывается тем же прямоугольником на каждом слое. Больше шести соседства, которые нужно держать в голове, перестают быть видимыми, а ради этого карта и существует: тогда берите минимизированную ДНФ из эквивалентных форм калькулятора.
Чем сумма произведений отличается от произведения сумм?
Это два способа прочитать одну и ту же карту. Группировка истинных клеток даёт сумму произведений: по одной конъюнкции на группу, соединённых ИЛИ. Группировка ложных даёт произведение сумм с отрицанием литералов на выходе: по одной дизъюнкции на группу, соединённых И. Обе описывают одну функцию; какая короче, зависит от того, единицы или нули складываются в более аккуратные прямоугольники, - поэтому решатель даёт обе.
Ответ решателя действительно минимальная форма?
Да. Сначала берутся существенные простые импликанты, а остаток покрытия ищется полным перебором с ветвями и границами, а не жадно. Это важно на циклической карте - где ни одна группа не существенна, - потому что жадный выбор может остановиться на покрытии, которое длиннее минимального на один терм, и никогда об этом не сообщит. Доминируемые строки и столбцы вычёркиваются вместе с существенными, раз за разом, пока таблица не перестанет уменьшаться, так что большинство карт до перебора вообще не доходят - именно это делает точный ответ мгновенным даже при шести переменных.
Почему столбцы подписаны 00, 01, 11, 10, а не 00, 01, 10, 11?
Потому что именно этот порядок и заставляет карту работать. Подписи идут кодом Грея, где соседние значения различаются ровно одним битом: значит, любые две соседние клетки различаются ровно одной переменной, и прямоугольник одинаковых значений оказывается термом, из которого эта переменная выпала. В обычном двоичном порядке 01 и 10 стояли бы рядом, различаясь двумя битами, и объединять их не имело бы смысла. По той же причине края замыкаются: первый и последний столбцы тоже различаются одним битом, поэтому группа может уйти за один край и продолжиться у другого.
Можно ли отметить клетки как безразличные?
Напрямую нет: решатель отображает выражение, а выражение в каждой строке истинно или ложно - третьего значения ввести некуда. Там, где функция действительно игнорирует вход, впишите это в формулу, и карта это покажет: терм вида (D | !D) помещает D на карту как переменную, от которой функция не зависит, - именно так построена готовая карта для правильной BCD-цифры.