карта Карно

Ка́рта Ка́рно (куб Ка́рно, диагра́мма Ка́рно, ка́рта Ве́йча) — графический способ представления булевых функций с целью их удобной и наглядной ручной минимизации. Является одним из эквивалентных способов описания или задания логических функций наряду с таблицей истинности или выражениями булевой алгебры. Преобразование карты Карно в таблицу истинности или в булеву формулу и обратно осуществляется элементарным алгоритмом. Удобство и наглядность такого представления логической функции обусловлено тем, что логические термы, к которым могут быть применены операции попарного неполного склеивания и элементарного поглощения группируются в карте Карно в виде визуально очевидных прямоугольных массивов, содержащих в своих ячейках одинаковые значения (нули и единицы). Карты Карно можно рассматривать как развертку на плоскость n-мерного булева куба, причем размерность этого гиперкуба совпадает с количеством переменных представляемой функции, а каждая вершина гиперкуба взаимно однозначно соответствует одной клетке карты Карно. Графически карта Карно изображается в виде прямоугольника или квадрата из ячеек, число которых равно , причем любые две соседние ячейки по вертикали или горизонтали или, иными словами — в окрестности фон Неймана описывают термы, различающиеся только по одной переменной — с логическим отрицанием и без логического отрицания. Также соседним являются первая и последняя строки, крайний левый и крайний правый столбцы таблицы, поэтому таблица Карно является фактически разверткой логического гиперкуба на поверхность тороида. Возможно построение самых различных карт для одной и той же функции, удовлетворяющих условию: геометрическое соседство ячеек в смысле фон Неймана — логическое соседство термов — то есть с расстоянием Хэмминга между термами соседних ячеек равным 1. Любая из таких таблиц одинаково удобна для минимизации функции, но обычно переменные по строкам и столбцам в карте Карно упорядочивают по рефлексивному коду Грея из-за мнемоничности и наглядности.