Ка́рта Ка́рно (куб Ка́рно, диагра́мма Ка́рно, ка́рта Ве́йча) — графический способ представления булевых функций с целью их удобной и наглядной ручной минимизацииГивоне Д. Россер Р. (1983), с. 67—76..
Является одним из эквивалентных способов описания или задания логических функций наряду с таблицей истинности или выражениями булевой алгебры. Преобразование карты Карно в таблицу истинности или в булеву формулу и обратно осуществляется элементарным алгоритмом.
Удобство и наглядность такого представления логической функции обусловлено тем, что логические термы, к которым могут быть применены операции попарного неполного склеивания и элементарного поглощения группируются в карте Карно в виде визуально очевидных прямоугольных массивов, содержащих в своих ячейках одинаковые значения (нули и единицы).
Карты Карно можно рассматривать как развертку на плоскость n-мерного булева куба, причем размерность этого гиперкуба совпадает с количеством переменных представляемой функции, а каждая вершина гиперкуба взаимно однозначно соответствует одной клетке карты Карно. Графически карта Карно изображается в виде прямоугольника или квадрата из ячеек, число которых равно , причем любые две соседние ячейки по вертикали или горизонтали или, иными словами — в окрестности фон Неймана описывают термы, различающиеся только по одной переменной — с логическим отрицанием и без логического отрицания. Также соседним являются первая и последняя строки, крайний левый и крайний правый столбцы таблицы, поэтому таблица Карно является фактически разверткой логического гиперкуба на поверхность тороида. Возможно построение самых различных карт для одной и той же функции, удовлетворяющих условию: геометрическое соседство ячеек в смысле фон Неймана — логическое соседство термов — то есть с расстоянием Хэмминга между термами соседних ячеек равным 1. Любая из таких таблиц одинаково удобна для минимизации функции, но обычно переменные по строкам и столбцам в карте Карно упорядочивают по рефлексивному коду Грея из-за мнемоничности и наглядности.
История Карты Карно были предложены в 1952 году Эдвардом В. ВейчемVeitch E. W. (May 1952). и усовершенствованы в 1953 году физиком из «Bell Labs» Морисом Карно (Maurice Karnaugh), чтобы упростить проектирование цифровых системKarnaugh M. (November 1953)..
Основные принципы Карта Карно представляет собой таблицу истинности, отформатированную особым образом, пригодным для наглядной ручной минимизации. Результатом минимизации является либо дизъюнктивная нормальная форма (ДНФ), либо конъюнктивная нормальная форма (КНФ). В первом случае работа ведётся с клетками карты, где находятся единицы, во втором — с клетками, где находятся нули. В исходной карте, как и в таблице истинности, каждая единица соответствует одному терму совершенной дизъюнктивной нормальной форме (СДНФ), а каждый ноль — одному терму совершенной конъюнктивной нормальной форме (СКНФ).
Рядом расположенные группы единиц или нулей на карте Карно объединяют в прямоугольные области или «склейки» размером клеток. Каждая такая группа в итоговой логической формуле будет соответствовать одному терму (если считать, что операция логического «ИЛИ» — это «суммирование», а операция логического «И» — это «перемножение», то один терм соответствует одному слагаемому в случае ДНФ, или одному сомножителю в случае КНФ), содержащему переменных, это группирование обычно называют «склейкой»Гивоне Д. Россер Р. (1983), с. 69.. Таким образом, работа с картой сводится к выделению оптимального набора нескольких групп единиц (нулей) и преобразование их в логическое выражение.
Принципы минимизации Основным методом минимизации логических функций, представленных в виде СДНФ или СКНФ, является операция попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания осуществляется между двумя термами, содержащими одинаковые переменные, вхождения которых (прямые и инверсные) совпадают для всех переменных, кроме одной. В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть поглощению. Например:
Аналогично для КНФ:
Возможность поглощения следует из очевидных равенств:
Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для функций многих логических переменных может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов.
Булевы функции N переменных, представленные в виде СДНФ или СКНФ, могут иметь в своём составе не более чем различных термов. Все эти элементарные термы можно представить в виде некоторой структуры, топологически эквивалентной -мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения.
На рисунке изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2-мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов:
В случае функции трёх переменных приходится иметь дело с трёхмерным кубом. Это сложнее и менее наглядно, но технически возможно. На рисунке в качестве примера показана таблица истинности для булевой функции трёх переменных и соответствующий ей куб.
Как видно из рисунка, для трёхмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных:
В общем случае можно сказать, что термов, принадлежащие одной что -мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются переменных.
Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскость, как показано на рисунке. Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) не соответствует порядку следования двоичных чисел записанных в лексикографическом порядке (00 01 10 11), а клетки, находящиеся в крайних столбцах таблицы, соседствуют между собой.
Аналогичным образом можно работать с логическими функциями большего числа переменных.
Стили представления карт Карно Традиционно существует несколько стилей представления карт Карно. Часто в шапке и левой колонке проставляются численные значения переменных, подобно тому, как они указаны в таблице истинности (а). В этом стиле наиболее очевидно, что карта Карно является своеобразной формой представления таблицы истинности. Однако клетки карты Карно следуют в несколько ином порядке, чем строки в таблице истинности, так как в таблице истинности принято строки упорядочивать в лексикографическом нарастании двоичных чисел. Например, в карте Карно для четырёх переменных порядок следования ячеек карты и строк таблицы истинности совпадёт, если переставить местами третий-четвёртый столбцы и третью-четвёртую строки карты.
Каждая строка таблицы истинности и каждая клетка карты Карно соответствует одному слагаемому ДНФ, поэтому в шапке и левой колонке карты можно указывать вхождения переменных (прямые и инверсные), как они выглядят в СДНФ (б). Существует сокращённый вариант этого стиля представления, где во вспомогательных строках и колонках указывается, в каком виде, прямом или инверсном, представлена каждая переменная в соответствующей строке или столбце карты (в).
Наконец, в некоторых случаях на краях карты линиями указываются столбцы и строки, где соответствующая переменная представлена в прямом виде (г).
а) б) в) г)
Порядок работы с картой Карно Исходной информацией для работы с картой Карно является таблица истинности минимизируемой функции. Таблица истинности содержит полную информацию о логической функции, задавая её значения на всех возможных 2n наборах входных переменных X1 … Xn. Карта Карно также содержит 2n клеток, каждая из которых ассоциируется с уникальным набором входных переменных X1 … Xn. Таким образом, между таблицей истинности и картой Карно имеется взаимно однозначное соответствие, и карту Карно можно считать соответствующим образом отформатированной таблицей истинности.
В данном разделе в качестве примера используется функция четырёх переменных, заданная таблицей истинности, изображённой на рис. 2а. Карта Карно для той же функции изображена на рис. 2б.
Принципы склейки Прямоугольную область в карте Карно, которая состоит из 2k одинаковых значений (единиц или нулей в зависимости от того, какую форму нужно получить) будем называть склейкой, группой или областью. Распределение всех имеющихся в карте Карно нулей (единиц) по склейкам будем называть покрытием. С целью минимизации булевой функции необходимо построить такое покрытие карты Карно, чтобы количество склеек было минимальным, а размер каждой склейки максимально возможным. Для этого необходимо руководствоваться следующими правилами.
Склейку клеток одной и той же карты Карно можно осуществлять как по единицам (a), так и по нулям (б). Первое необходимо для получения ДНФ, второе — для получения КНФ.
a) б)
Склеивать можно только прямоугольные области с числом единиц (нулей), являющимся целой степенью двойки (1, 2, 4, 8, 16, 32… клетки).
Рекомендуется выбирать максимально возможные области склейки. Если область склейки не является максимально возможной, это не будет ошибкой, однако ДНФ (КНФ) не получится минимальной.
В некоторых ситуациях в раскладке образуется изолированная единица или ноль, которую невозможно включить в какую-либо область. В этом случае единица (ноль) склеивается «сама с собой». Нельзя оставлять «висячие» единицы (нули), так как это приведёт к некорректной записи выражения для функции. Все единицы (нули) должны попасть в какую-либо область.
Область, которая подвергается склейке, должна содержать одинаковые значения — только единицы или только нули.
Для карт Карно с числом переменных 3 и 4 применимо следующее правило: крайние клетки каждой горизонтали и каждой вертикали граничат между собой и могут объединяться в прямоугольники (топологически карта Карно представляет собой тор). Следствием этого правила является смежность всех четырёх угловых ячеек карты Карно для 4 переменных. Для карт Карно с числом переменных менее 3 это правило не имеет смысла, так как крайние клетки и так граничат между собой; для карт Карно с числом переменных более четырёх правила смежности более сложные.
Одна ячейка карты Карно может входить сразу в несколько областей. Это следует из очевидного свойства булевых функций: повторение уже существующего слагаемого (сомножителя) не влияет на функцию:
Не следует без нужды включать клетку во все возможные склейки, это не является ошибкой, но усложняет формулу. С точки зрения минимальности ДНФ (КНФ) число склеек должно быть как можно меньше (каждая дополнительная склейка порождает дополнительный терм), а число клеток в склейке должно быть максимально возможным (чем больше клеток в склейке, тем меньше переменных содержит терм. Склейка размером 2k клеток порождает терм с n-k переменными).
В отличие от СДНФ и СКНФ, ДНФ и КНФ не всегда единственны. Для некоторых функций существует несколько эквивалентных друг другу ДНФ (КНФ), которые соответствуют разным способам покрытия карты Карно прямоугольными областями. Очень часто две различные ДНФ (КНФ) имеют одинаковую сложность, что не позволяет сделать однозначный выбор минимальной формулы.
Карты с неопределёнными значениями На практике встречаются случаи, когда при некоторых значениях аргументов булева функция не определена. Например, булева функция описывает цифровое устройство, у которого некоторые сочетания входных сигналов физически невозможны или же при некоторых значениях входных сигналов реакция устройства не имеет значения. В таких случаях говорят о «неопределённых условиях», а функция такого вида называется «частично определённой» или просто «частичной»Гивоне Д. Россер Р. (1983), с. 75..