Метод карт Карно
Карта Карно — это таблица, в которой соседние наборы аргументов расположены так, чтобы при переходе между соседними клетками изменялся ровно один аргумент. Объединяя соседние клетки с единичными значениями функции, можно получить минимальное логическое выражение без громоздких алгебраических преобразований.
Назначение и устройство карты Карно
Карта Карно строится по истинному набору функции: в клетках отмечают те комбинации аргументов, на которых функция равна 1. Чаще всего карту используют для перехода от дизъюнктивной нормальной формы к минимальной форме — сумме произведений.
Карта Карно — прямоугольная таблица клеток для всех наборов аргументов булевой функции, расположенных в порядке кода Грея. В соседних клетках коды отличаются ровно одним разрядом.
Для двух аргументов получается таблица \(2\times2\), для трёх — \(2\times4\), для төрт — \(4\times4\). Заголовки строк и столбцов записывают в порядке Грея: \(00, 01, 11, 10\), а не в обычном порядке \(00, 01, 10, 11\). Благодаря этому крайние строки или столбцы также считаются соседними: карта как бы «сворачивается» в цилиндр.
Правила группировки единиц
Единицы объединяют в группы, или импликанты. Каждая группа должна содержать \(1, 2, 4, 8,\ldots\) клеток — только степень двойки. Группа имеет прямоугольную форму и может пересекать границу карты. Разрешены группы из одной клетки, если её нельзя присоединить к другим.
Если в группе из \(2^k\) клеток объединены единичные наборы, то в соответствующем произведении сохраняются только те аргументы, значения которых одинаковы во всех клетках. Число литералов уменьшается на \(k\).
- Группа должна состоять только из единиц. Если в условии разрешены неопределённые значения \(X\), их можно присоединять по необходимости.
- Группу выбирают максимально большой: большая группа даёт более короткий член.
- Каждая единица должна попасть хотя бы в одну группу.
- Перекрытие групп разрешено и иногда необходимо.
- Диагональные клетки соседними не считаются.
- Крайние клетки строки или столбца соседствуют друг с другом.
Группа из двух клеток устраняет один аргумент, группа из четырёх — два, группа из восьми — три. Если вся карта заполнена единицами, функция равна 1, и аргументы в ответе не нужны.
Какое объединение допустимо на карте Карно?
Алгоритм минимизации по единичным наборам
- Определите число аргументов и начертите карту нужного размера.
- Подпишите строки и столбцы кодами Грея.
- Отметьте единицами клетки, соответствующие истинным наборам функции.
- Найдите максимальные допустимые группы единиц, начиная с самых больших.
- Для каждой группы выпишите аргументы, которые не меняются внутри неё.
- Соедините полученные произведения знаком дизъюнкции \(\lor\) и проверьте, покрыты ли все единицы.
Если аргумент равен 1 во всех клетках группы, он кіреді без отрицания: \(x\). Если равен 0 во всех клетках, кіреді с отрицанием: \(\overline{x}\). Если меняется с 0 на 1, он исчезает из произведения.
Разобранный пример
Минимизируем функцию төрт аргументов \(F(a,b,c,d)\), заданную единичными наборами \(1,3,5,7,9,11,13,15\).
В карте \(4\times4\) строки зададим аргументами \(a,b\) в порядке \(00,01,11,10\), а столбцы — аргументами \(c,d\) в порядке \(00,01,11,10\).
| \(ab\\backslash cd\) | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 1 | 1 | 0 |
| 01 | 0 | 1 | 1 | 0 |
| 11 | 0 | 1 | 1 | 0 |
| 10 | 0 | 1 | 1 | 0 |
Минимальная форма: \(F=d\). Восемь исходных единичных наборов заменяются одним литералом, потому что значение функции зависит только от последнего аргумента.
Пример с несколькими группами
Пусть \(F(a,b,c)=1\) на наборах \(1,3,4,5,7\). В карте \(2\times4\) единицы располагаются в клетках с номерами 1, 3, 4, 5 и 7. Можно выделить группу из төрт клеток \(1,3,5,7\) и отдельную пару \(4,5\).
Перекрытие клетки 5 допустимо: она входит сразу в две группы. Это не ошибка, а способ получить короткое выражение.
Не используйте обычный порядок заголовков \(00,01,10,11\): тогда соседними окажутся наборы, отличающиеся сразу в двух аргументах. Не группируйте по диагонали, не забывайте о соседстве через края и не оставляйте единицу непокрытой. Нельзя включать в группу нулевую клетку, если она не отмечена как неопределённая.
Как проверить результат
После записи выражения проверьте три свойства. Во-первых, каждое исходное единичное значение должно покрываться хотя бы одной группой. Во-вторых, выражение не должно давать 1 на наборах, где функция равна 0. В-третьих, группы должны быть максимально крупными. Иногда существует несколько равносильных минимальных выражений: это нормально.
Чем больше клеток в группе, тем меньше литералов в соответствующей конъюнкции. Минимизация карты Карно выбирает группы так, чтобы получить покрытие всех единиц с наименьшим числом и длиной членов.
Если требуется минимизация по нулевым наборам, используют аналогичный приём, но группируют нули и получают произведение сумм — форму, связанную с конъюнктивной нормальной формой. Для тапсырмалардың по единичным наборам обычно достаточно описанного алгоритма.
Быстрая проверка
Главное
- Карту Карно заполняют по единичным наборам функции, а заголовки располагают в порядке Грея.
- Группы содержат \(1,2,4,8,\ldots\) клеток, имеют прямоугольную форму и могут переходить через границу карты.
- В группе сохраняются только аргументы, постоянные во всех клетках: единица — без отрицания, ноль — с отрицанием.
- Нужно покрыть все единицы максимально крупными группами; перекрытие групп разрешено.
- Для минимизации по нулям применяют аналогичный метод и получают форму, связанную с КНФ.