Карта Карно
Карта Карно — наглядный способ упростить логическую функцию от трёх–пяти переменных: значения функции расставляют в таблицу так, что соседние клетки отличаются одной переменной, и объединяют единицы в прямоугольные группы.
Обновлено Редакция GAW
Карта Карно (Karnaugh map, K-map) — таблица значений логической функции, у которой строки и столбцы подписаны наборами входных переменных в порядке кода Грея. В этом порядке соседние наборы отличаются одной переменной, поэтому и любые соседние клетки карты — в том числе на противоположных краях — отличаются значением ровно одной переменной. Метод предложил Морис Карно в 1953 году.
Как пользоваться
- Расставить значения функции по клеткам: для четырёх переменных это карта 4 × 4, строки — AB, столбцы — CD в порядке 00, 01, 11, 10.
- Объединить единицы в прямоугольные группы из 1, 2, 4, 8 или 16 клеток — как можно более крупные и как можно меньшим числом. Группы могут перекрываться и переходить через края.
- Каждая группа даёт конъюнкцию переменных, которые внутри неё не меняются. Дизъюнкция этих конъюнкций — минимальная дизъюнктивная нормальная форма (ДНФ).
Если группировать нули, получается минимальная конъюнктивная нормальная форма (КНФ). Например, функция f = Σm(6, 8, 9, 10, 11, 12, 13, 14) упрощается до ДНФ AC' + AB' + BCD' и КНФ (A + B)(A + C)(B' + C' + D').
Где применяется
Карта Карно удобна для функций от трёх до пяти переменных: упростить логику дешифратора, условия в программе или комбинацию логических элементов на плате. Для большего числа переменных вручную её строить неудобно, и минимизацию делают табличным методом Куайна — Мак-Класки. Построить карту по своей функции, увидеть группы и получить ДНФ и КНФ поможет калькулятор карты Карно, а таблицу истинности по выражению — конструктор таблицы истинности. Логические элементы и законы булевой алгебры разобраны в статье «Цифровая логика».
Частые вопросы
Почему строки и столбцы карты подписаны не по порядку?
Их подписывают в порядке кода Грея — 00, 01, 11, 10, — в котором соседние наборы отличаются одной переменной. Тогда любые две соседние клетки карты, включая крайние в строке и столбце, отличаются значением ровно одной переменной, и при объединении в группу эта переменная выпадает из выражения.
Какими группами объединять единицы?
Прямоугольниками из 1, 2, 4, 8 или 16 клеток — степени двойки, — как можно более крупными и как можно меньшим их числом, чтобы покрыть все единицы. Группа из 2^k клеток убирает k переменных. Группы могут перекрываться и переходить через края карты.
Что такое безразличные наборы?
Наборы входных переменных, на которых значение функции не важно: например, коды 10–15 у схемы, которая получает только десятичные цифры 0–9 в двоичном коде. Клетку с таким набором можно включить в группу, если это делает группу больше, и не включать, если не помогает.
Источники
- 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 — пример f = Σm(6, 8, 9, 10, 11, 12, 13, 14): ДНФ AC' + AB' + BCD', КНФ (A + B)(A + C)(B' + C' + D')
Нашли ошибку?