Введите логическую функцию — калькулятор построит её таблицу истинности, нарисует карту Карно с пронумерованными группами единиц и выдаст минимальную дизъюнктивную нормальную форму (МДНФ), найденную методом Квайна — Мак-Класки. Ниже разобрано, как получить тот же ответ вручную: два примера с решением на 3 и на 4 переменные и таблица склеивания минтермов.
Теория и пояснения
Минимизация логической функции — это поиск её самой короткой равносильной записи, то есть формы с наименьшим числом вхождений переменных. Исходной точкой служит таблица истинности: по строкам, где функция равна 1, выписывается СДНФ, а затем полные минтермы склеиваются между собой по правилу X ∧ Y ∨ X ∧ ¬Y = X — два набора, различающиеся ровно в одном разряде, дают один терм без этой переменной. Термы, которые больше не склеиваются, называются простыми импликантами; из них выбирают минимальное покрытие всех единичных наборов, и результат называется минимальной дизъюнктивной нормальной формой, МДНФ. Наглядно склейку выполняет карта Карно: таблица истинности разворачивается в прямоугольник с заголовками в коде Грея, единицы объединяются в прямоугольники из 2, 4 или 8 клеток, и каждый прямоугольник даёт один терм — переменные, меняющиеся внутри группы, выпадают. Карта замкнута в кольцо, поэтому склеиваются и клетки у противоположных краёв, включая четыре угла. Формальный аналог карты — метод Квайна — Мак-Класки: те же склейки, но в виде таблиц, зато без ограничения на число переменных. Калькулятор на этой странице выполняет минимизацию именно методом Квайна — Мак-Класки: он строит таблицу истинности введённой формулы, находит все простые импликанты, отбирает существенные, добирает остаток и выводит строку «Упрощённое выражение (МДНФ)», а рядом рисует карту Карно с пронумерованными группами, чтобы результат можно было сверить с ручным решением. Если функция тождественно истинна, минимальная форма равна константе 1, если тождественно ложна — константе 0. У функции может быть несколько тупиковых ДНФ одинаковой длины, поэтому ответ, отличающийся от выданного, тоже бывает верным — проверить это можно сравнением таблиц истинности двух записей.
Частые вопросы
Как минимизировать логическую функцию онлайн?
Введите формулу в поле выше — калькулятор построит таблицу истинности, нарисует карту Карно с группами единиц и выведет строку «Упрощённое выражение (МДНФ)». Это и есть минимальная форма функции: равносильная исходной, но с наименьшим числом букв. Всё считается в браузере, регистрация не нужна.
Что такое карта Карно и как ей пользоваться?
Карта Карно — это таблица истинности, развёрнутая в прямоугольник с заголовками в коде Грея (00, 01, 11, 10), так что соседние клетки отличаются ровно одной переменной. Единицы объединяют в прямоугольники из 1, 2, 4 или 8 клеток — как можно крупнее и как можно меньшим числом групп. В каждой группе оставляют переменные, которые не меняются, и соединяют полученные термы знаком ИЛИ.
Как работает метод Квайна — Мак-Класки?
В три шага. Сначала склеивание: минтермы, отличающиеся ровно в одном разряде, объединяются, а этот разряд заменяется прочерком; склейки повторяются, пока возможны. Несклеившиеся термы — простые импликанты. Затем строится таблица покрытия, и из импликантов выбирается минимальный набор, накрывающий все единичные наборы: сначала существенные, потом остаток.
Для скольких переменных строится карта Карно?
Плоская карта наглядна для 2, 3 и 4 переменных — калькулятор рисует её именно в этих случаях. Для 5 и более переменных карту пришлось бы разбивать на слои, поэтому там пользуются методом Квайна — Мак-Класки: он даёт тот же результат при любом числе переменных и работает в калькуляторе всегда.
Что такое простые и существенные импликанты?
Простой (первичный) импликант — терм, который больше не склеивается ни с одним другим, то есть максимально крупная группа единиц на карте. Существенный импликант — тот, который единственным накрывает хотя бы один единичный набор: без него функцию не покрыть, поэтому он обязательно входит в МДНФ. Остальные простые импликанты могут оказаться лишними.
Чем МДНФ отличается от СДНФ?
СДНФ содержит по одному полному терму на каждый единичный набор, и в каждом терме участвуют все переменные — форма единственная, но длинная. МДНФ получается из СДНФ склеиванием и содержит наименьшее возможное число букв. Например, СДНФ из четырёх полных термов на 12 букв может свернуться в МДНФ из двух термов на 4 буквы.
Почему мой ответ отличается от ответа калькулятора?
У функции может быть несколько тупиковых ДНФ одинаковой длины — тогда верны обе записи. Проверьте это так: постройте таблицы истинности вашей формы и выданной калькулятором. Если итоговые столбцы совпадают во всех строках и число букв одинаково, обе формы минимальны. Сравнить две записи напрямую можно на странице проверки равносильности.
Можно ли минимизировать до КНФ (МКНФ)?
Да, по той же карте, но группируют не единицы, а нули: каждая группа нулей даёт дизъюнкцию, в которой переменная берётся с отрицанием, если внутри группы она равна 1. Полученные скобки соединяют знаком И — это минимальная конъюнктивная форма. Калькулятор выводит СКНФ, из которой МКНФ получается тем же склеиванием.