Карта Карно — таблица истинности, разложенная по клеткам так, что соседние клетки отличаются значением одной переменной. Благодаря этому одинаковые значения функции, стоящие рядом, можно «склеить» в одну группу и сразу прочитать короткую формулу. Калькулятор находит наименьший набор групп точно — методом Куайна — Мак-Класки — и рисует эти группы на карте.
Как пользоваться
- Выберите число переменных: 2, 3, 4 или 5. Переменные называются A, B, C, D, E, и первая — старший разряд номера набора.
- Отметьте единицы функции: нажмите на клетку — 0 сменится на 1, второе нажатие поставит x (безразлично), третье вернёт 0. Можно и ввести номера наборов в поле: «1, 3, 5-7».
- Выберите, что группировать: единицы — получится минимальная ДНФ, нули — минимальная КНФ.
Номер набора в углу клетки — это номер строки таблицы истинности: для четырёх переменных клетка в строке AB = 10 и столбце CD = 11 — набор 1011₂ = 11. Задать функцию выражением и сразу увидеть её таблицу и СДНФ можно в калькуляторе таблицы истинности.
Правила групп
- Группа — прямоугольник из 2ᵏ клеток: 1, 2, 4, 8, 16. Группа из 2ᵏ клеток убирает k переменных: чем больше группа, тем короче её конъюнкция.
- Карта замкнута: верхний край соседствует с нижним, левый — с правым, поэтому четыре угловые клетки карты 4 × 4 образуют одну группу.
- Каждая единица должна попасть хотя бы в одну группу; группы могут перекрываться.
- Минимальная форма — та, где групп меньше всего, а при равном числе — меньше букв. Если таких форм несколько, калькулятор показывает одну из них.
Пример
Функция четырёх переменных, равная 1 на наборах 6, 8, 9, 10, 11, 12, 13 и 14, — пример из статьи о картах Карно, им калькулятор открывается по умолчанию. Единицы складываются в три группы: строка AB = 10 целиком (A·B'), левый квадрат нижних строк (A·C') и пара клеток 0110 и 1110 (B·C·D'). Минимальная ДНФ — AC' + AB' + BCD', а группировка нулей даёт КНФ (A + B)(A + C)(B' + C' + D').
Частые вопросы
Как минимизировать функцию картой Карно?
Расставьте значения функции по клеткам карты: строки и столбцы подписаны наборами переменных в порядке кода Грея, поэтому соседние клетки отличаются одной переменной. Обведите единицы прямоугольными группами из 1, 2, 4, 8 или 16 клеток — как можно более крупными и как можно меньшим их числом; группы могут перекрываться и переходить через край карты. Каждой группе соответствует конъюнкция переменных, которые в ней не меняются; дизъюнкция групп и есть минимальная ДНФ.
Зачем нужны безразличные наборы (x)?
Это наборы, на которых значение функции не важно: например, коды 10–15 у схемы, которая получает только десятичные цифры 0–9 в двоичном коде. Клетку с x можно включить в группу, если это делает группу больше, и не включать, если не помогает, — так форма получается короче.
Как получить КНФ по карте Карно?
Сгруппируйте не единицы, а нули. Каждая группа нулей даёт дизъюнкцию переменных, которые в ней не меняются, причём переменная, равная в группе 1, входит с отрицанием. Конъюнкция таких дизъюнкций — минимальная КНФ. В калькуляторе для этого переключите «Группировать» на «нули → КНФ».
Как устроена карта для пяти переменных?
Карта для пяти переменных — 4 строки на 8 столбцов: строки задают переменные A и B, столбцы — C, D и E в порядке трёхразрядного кода Грея (000, 001, 011, 010, 110, 111, 101, 100). Соседними считаются и клетки, симметричные относительно середины строки, — поэтому некоторые группы на такой карте разделены на две части; калькулятор рисует обе части одним цветом.
Источники
- M. Karnaugh. The map method for synthesis of combinational logic circuits. Transactions of the AIEE, Part I, 1953, vol. 72, no. 5 — карта с упорядочиванием строк и столбцов кодом Грея, склеивание соседних клеток
- E. J. McCluskey. Minimization of Boolean functions. The Bell System Technical Journal, 1956, vol. 35, no. 6 — метод, которым калькулятор находит наименьшее покрытие
- Википедия. Karnaugh map; Quine–McCluskey algorithm — примеры f = Σm(6, 8, 9, 10, 11, 12, 13, 14) (ДНФ AC' + AB' + BCD', КНФ (A + B)(A + C)(B' + C' + D')) и f = Σm(4, 8, 10, 11, 12, 15) + d(9, 14) — эталоны тестов
Встроить калькулятор на свой сайт
Скопируйте код и вставьте его в HTML страницы, статьи или вики. Виджет бесплатный, без рекламы, счётчиков и cookie. Условие одно — ссылка на GAW под рамкой остаётся на месте. Подробнее о виджетах
<iframe src="https://gaw.ru/embed/karnaugh/" title="Карта Карно онлайн" width="100%" height="640" style="border:1px solid #e3e5e9;border-radius:8px" loading="lazy" allow="clipboard-write"></iframe>
<p style="margin:6px 0 0;font-size:14px">Калькулятор: <a href="https://gaw.ru/tools/karnaugh/">Карта Карно онлайн</a> — GAW.ru</p>Автоподстройка высоты рамки
Если сайт разрешает скрипты, добавьте этот код один раз в любом месте страницы: рамка будет менять высоту вместе с результатом расчёта.
<script>window.addEventListener("message",function(e){if(e.origin!=="https://gaw.ru"||!e.data||e.data.type!=="gaw:embed-height")return;var f=document.querySelectorAll('iframe[src^="https://gaw.ru/embed/"]');for(var i=0;i<f.length;i++)if(f[i].contentWindow===e.source)f[i].style.height=e.data.height+"px"})</script>Обновлено .
Нашли ошибку в расчёте?