Минимизация булевой функции: карта Карно

Карта Карно помогает сократить булеву функцию, не перебирая вслепую алгебраические преобразования. На ней соседние наборы отличаются значением одной переменной: если функция равна единице на обоих, эту переменную можно убрать из соответствующего слагаемого. Объединяя такие клетки, получают более короткую дизъюнктивную нормальную форму.
Ниже можно переключать значения функции трёх переменных и наблюдать, как меняются карта и результат. Разберём пример с группой через край карты, а затем проверим, почему найденное покрытие минимально.
Зачем нужна минимизация
Булева функция принимает значения 0 и 1. Её можно задать таблицей истинности, перечислив выход для каждого набора входов. Для трёх переменных существует восемь наборов; подробнее сам подсчёт рассмотрен в статье о числе булевых функций.
Каждой единичной строке соответствует минтерм - конъюнкция всех переменных с отрицаниями там, где в наборе стоит ноль. Дизъюнкция минтермов образует совершенную ДНФ. Она удобна как однозначная исходная запись, но часто содержит избыточные литералы: так называют вхождения переменных и их отрицаний.
Минимальная ДНФ в принятом здесь смысле имеет наименьшее число конъюнктивных слагаемых; при равенстве этого числа выбираем вариант с наименьшим общим числом литералов. Возможны несколько разных минимальных ответов. Более короткая формула помогает при проектировании схемы, хотя реальная стоимость устройства зависит также от доступного базиса и других ограничений.
Как устроена карта Карно
Для трёх переменных карта содержит две строки и четыре столбца для пары . Столбцы располагают в порядке , а не обычном двоичном порядке. Это код Грея: в соседних столбцах меняется только один разряд. Переход между первым и последним столбцом тоже меняет только , поэтому края считаются соседними.
Заполняя карту, берут значение из таблицы истинности для набора, обозначенного строкой и столбцом. Например, строка и столбец соответствуют набору , то есть номеру 5 при двоичной нумерации. Важно не путать этот номер с позицией столбца на странице.
Для четырёх переменных обе оси обычно размечают последовательностью . Тогда соседствуют и верхний с нижним краем, и левый с правым. Угловые клетки могут входить в одну группу из четырёх: их соседство удобно представить, мысленно свернув карту по обоим направлениям.
Правила группировки единиц
Для ДНФ объединяют единицы в прямоугольные группы размером и так далее: число клеток всегда степень двойки. Группа может переходить через край и может пересекаться с другой группой. Диагональное касание соседством не считается. Ноль внутрь группы единиц включать нельзя.
Каждую единицу нужно покрыть хотя бы один раз. Обычно начинают с самых крупных допустимых групп: чем больше группа, тем больше переменных меняется внутри неё и исчезает из слагаемого. Но большие группы не выбирают механически: после этого нужно убедиться, что покрыты все единицы и что набор групп нельзя заменить более выгодным.
Из группы выписывают только постоянные переменные. Если постоянное значение равно 1, переменная входит без отрицания; если 0 - с отрицанием. Переменные, принимающие в группе оба значения, исчезают. Основание правила - склеивание:
В карте пара соседних клеток даёт один такой шаг; группа из четырёх убирает две меняющиеся переменные. Все полученные конъюнкции соединяют знаком .
Пример: единицы 0, 2, 5 и 7
Пусть : функция равна единице на наборах и нулю на остальных. В таблице ниже порядок строк и столбцов именно такой, как на карте, а не порядок возрастания номеров.
| / | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |

Первая пара состоит из наборов и . Она расположена на противоположных краях верхней строки. В обоих наборах и , а меняется, поэтому пара даёт .
Вторая пара объединяет и в середине нижней строки. Здесь постоянны и , а снова меняется. Получаем . Результат:
Функция равна единице, когда и совпадают; значение на ответ не влияет. Для проверки можно подставить все восемь наборов: при срабатывает первое слагаемое, при - второе, а при несовпадении оба равны нулю.
Здесь нет допустимой группы из четырёх единиц: четыре клетки не образуют одного подкуба без нулей. Каждая пара покрывает не более двух единиц, поэтому нужна как минимум пара групп. Найденные две группы достигают этой границы; каждая содержит два литерала, всего четыре. Таким образом, по указанному критерию ДНФ минимальна.
Если исходить из СДНФ, те же две группы видны и в формулах. Для первой пары запишем
Вынесенные за скобки и одинаковы для обеих клеток. Внутри скобок остаётся . Аналогично из двух минтермов нижней строки получается . Геометрия карты делает возможные склеивания видимыми, но опирается на обычные законы булевой алгебры.
При ручном решении полезно сначала подписать номера наборов рядом с черновой картой, затем перенести значения функции и только после этого рисовать группы. Закончив, проверьте каждое слагаемое отдельно: оно должно обращаться в единицу ровно на клетках своей группы. Так проще заметить перепутанное отрицание, чем искать ошибку уже в готовом выражении.
Как выбрать покрытие и проверить ответ
Сначала найдите группы, которые нельзя расширить без захвата нуля: это простые импликанты. Если единица покрывается только одной такой группой, соответствующая импликанта обязательна. Затем покройте оставшиеся единицы минимальным числом групп, сравнивая при равенстве суммарное число литералов. Перекрытие разрешено, если оно помогает получить более короткое выражение.
Проверка эквивалентности и доказательство минимальности - разные действия. Совпадение таблиц истинности подтверждает правильность функции, но само по себе не доказывает, что формулу нельзя сократить дальше. Для небольшой карты сравните возможные покрытия; для большого числа переменных практичнее использовать алгоритмические методы минимизации, поскольку карта быстро растёт.
Калькулятор выше рассматривает все допустимые группы трёх переменных и выбирает одно покрытие по тому же критерию. Числа в скобках после результата - номера наборов внутри групп, а не номера столбцов. Он работает с полностью определённой функцией и не задаёт безразличные значения.
Например, пусть в некоторой карте две разные максимальные группы перекрываются на одной единице. Это не нарушение: формула применяет операцию ИЛИ, а повторное покрытие не меняет значение . И наоборот, две непересекающиеся группы не обязательно дают лучший ответ: одна из них может быть частью более крупной допустимой группы. Поэтому сравнивают полное покрытие, а не только число новых клеток на каждом отдельном шаге.
Нули и безразличные наборы
Если нужна конъюнктивная нормальная форма, можно группировать нули. Каждая группа даёт дизъюнктивную скобку: постоянная в группе переменная со значением 0 входит без отрицания, со значением 1 - с отрицанием. Затем скобки соединяют конъюнкцией. Это обратное правило получается применением законов де Моргана к дополнению функции.
В некоторых задачах отдельные наборы входов невозможны либо значение выхода для них не задано. Их отмечают и называют безразличными. При поиске ДНФ такую клетку разрешается включить в группу единиц, если это помогает её увеличить, или не использовать вовсе. Покрывать все не требуется; все настоящие единицы покрыть обязательно. Уточните условие: считать произвольный ноль безразличным нельзя.
После минимизации выражение можно перевести в выбранный элементный базис. Например, штрих Шеффера и стрелка Пирса позволяют выразить стандартные операции через NAND или NOR. Само построение логической схемы по выражению - следующий шаг после проверки формулы.
Частые ошибки
- Обычный двоичный порядок столбцов. Между и меняются два бита; используйте порядок Грея.
- Забытые края. Первый и последний столбцы соседствуют, как и верхний и нижний края карты четырёх переменных.
- Группа из трёх или диагональ. Допустимы прямоугольные группы степенной двойки, отражающие изменение независимых переменных.
- Покрыта не каждая единица или захвачен ноль. Сверьте все клетки после выбора групп.
- Меняющаяся переменная осталась в слагаемом. Выписывайте только те значения, которые одинаковы во всей группе.
FAQ
Обязательно ли использовать все возможные группы?
Нет. Достаточно покрытия всех единиц; лишняя группа может сделать формулу длиннее. При этом одна клетка вправе участвовать в нескольких выбранных группах.
Что делать, если вся карта заполнена единицами?
Объединить все клетки в одну группу. Ни одна переменная не постоянна, поэтому функция равна константе . Если единиц нет, функция равна .
Всегда ли минимальная ДНФ единственна?
Нет. Разные наборы групп могут давать одинаково короткие эквивалентные выражения. Калькулятор показывает один из возможных вариантов.
Коротко
Карта Карно размещает соседние наборы по коду Грея. Для минимальной ДНФ объединяют единицы в допустимые группы, учитывают соседство краёв и выписывают постоянные переменные. Покрытие всех единиц и проверка нулевых наборов подтверждают эквивалентность; сравнение покрытий устанавливает минимальность.
Читайте также

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

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

Алгоритм Хопкрофта-Карпа: паросочетание по фазам
Алгоритм Хопкрофта-Карпа находит максимальное паросочетание в двудольном графе. Разбираем поиск кратчайших цепей, BFS и DFS, пример двух фаз и оценку сложности.

Число булевых функций от n переменных: формула
Сколько существует булевых функций от n переменных и почему ответ равен 2 в степени 2ⁿ? Вывод по таблице истинности, примеры и задачи с ограничениями.

Теорема Форда-Фалкерсона о максимальном потоке
Теорема Форда-Фалкерсона связывает максимальный поток и минимальный разрез. Разбираем доказательство через остаточную сеть, пример и проверку решения.

Отношение эквивалентности: классы и фактор-множество
Отношение эквивалентности: классы и фактор-множество простыми словами. Разбираем рефлексивность, симметричность и транзитивность, разбиение на классы и построение фактор-множества с примерами.