Карта Карно
Карта Карно ( KM или K-map ) — это метод упрощения выражений булевой алгебры . Морис Карно представил ее в 1953 году [1] [2] как усовершенствование диаграммы Вейча Эдварда В. Вейча 1952 года, [3] [4] , которая была повторным открытием логической диаграммы Аллана Марканда 1881 года [5] , также известной как диаграмма Марканда . [4] , но теперь основное внимание уделяется его полезности для коммутации цепей. [4] Диаграммы Вейча поэтому также известны как диаграммы Маркана-Вейча .[4] и карты Карно как карты Карно–Вейча ( карты KV ).
Карта Карно снижает потребность в обширных вычислениях, используя возможности человека по распознаванию образов. [1] Он также позволяет быстро выявлять и устранять потенциальные условия гонки .
Требуемые логические результаты переносятся из таблицы истинности на двумерную сетку, где в картах Карно ячейки упорядочены в коде Грея , [6] [4] , и каждая позиция ячейки представляет собой одну комбинацию входных условий. Ячейки также известны как minterms, в то время как каждое значение ячейки представляет соответствующее выходное значение логической функции. Выявляются оптимальные группы единиц или нулей, которые представляют собой термины канонической формы логики в исходной таблице истинности. [7] Эти термины можно использовать для записи минимального логического выражения, представляющего требуемую логику.
Карты Карно используются для упрощения реальных логических требований, чтобы их можно было реализовать с использованием минимального количества логических вентилей. Выражение суммы произведений (SOP) всегда может быть реализовано с использованием логических элементов И , передающих логический элемент ИЛИ , а выражение произведения сумм (POS) приводит к логическим элементам ИЛИ, передающим логический элемент И. Выражение POS дает дополнение функции (если F — функция, то ее дополнение будет F'). [8] Карты Карно также можно использовать для упрощения логических выражений при разработке программного обеспечения. Логические условия, используемые, например, в условных операторах., может стать очень сложным, что затрудняет чтение и сопровождение кода. После минимизации канонические выражения суммы произведений и произведений сумм могут быть реализованы напрямую с использованием логических операторов И и ИЛИ. [9]
Карты Карно используются для упрощения функций булевой алгебры . Например, рассмотрим логическую функцию, описанную следующей таблицей истинности .
Ниже приведены две разные записи, описывающие одну и ту же функцию в неупрощенной булевой алгебре с использованием логических переменных A , B , C , D и их инверсий.
