Карта Карно

Карты Карно были предложены в 1952 году Эдвардом В. Вейчем[2] и усовершенствованы в 1953 году физиком из «Bell Labs» Морисом Карно (Maurice Karnaugh), чтобы упростить проектирование цифровых систем[3].

Карта Карно представляет собой таблицу истинности, отформатированную особым образом, пригодным для наглядной ручной минимизации. Результатом минимизации является либо дизъюнктивная нормальная форма (ДНФ), либо конъюнктивная нормальная форма (КНФ). В первом случае работа ведётся с клетками карты, где находятся единицы, во втором — с клетками, где находятся нули. В исходной карте, как и в таблице истинности, каждая единица соответствует одному терму cовершенной дизъюнктивной нормальной форме (СДНФ), а каждый ноль — одному терму cовершенной конъюнктивной нормальной форме (СКНФ).

Рядом расположенные группы единиц или нулей на карте Карно объединяют в прямоугольные области или «склейки» размером ${\displaystyle 2^{a}\times 2^{b}}$ клеток. Каждая такая группа в итоговой логической формуле будет соответствовать одному терму (если считать, что операция логического «ИЛИ» — это «суммирование», а операция логического «И» — это «перемножение», то один терм соответствует одному слагаемому в случае ДНФ, или одному сомножителю в случае КНФ), содержащему ${\displaystyle n-a-b}$ переменных, это группирование обычно называют «склейкой»[4]. Таким образом, работа с картой сводится к выделению оптимального набора нескольких групп единиц (нулей) и преобразование их в логическое выражение.

Основным методом минимизации логических функций, представленных в виде СДНФ или СКНФ, является операция попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания осуществляется между двумя термами, содержащими одинаковые переменные, вхождения которых (прямые и инверсные) совпадают для всех переменных, кроме одной. В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть поглощению. Например:

${\displaystyle {\overline {X}}_{1}X_{2}X_{3}X_{4}\vee {\overline {X}}_{1}X_{2}{\overline {X}}_{3}X_{4}={\overline {X}}_{1}X_{2}X_{4}(X_{3}\vee {\overline {X}}_{3})={\overline {X}}_{1}X_{2}X_{4}\cdot 1={\overline {X}}_{1}X_{2}X_{4}.}$

Аналогично для КНФ:

${\displaystyle ({\overline {X}}_{1}\vee X_{2}\vee X_{3}\vee X_{4})({\overline {X}}_{1}\vee X_{2}\vee {\overline {X}}_{3}\vee X_{4})={\overline {X}}_{1}\vee X_{2}\vee X_{4}\vee X_{3}{\overline {X}}_{3}={\overline {X}}_{1}\vee X_{2}\vee X_{4}\vee 0={\overline {X}}_{1}\vee X_{2}\vee X_{4}.}$

Возможность поглощения следует из очевидных равенств:

${\displaystyle A\vee {\overline {A}}=1;A{\overline {A}}=0.}$

Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для функций многих логических переменных может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов.

Булевы функции N переменных, представленные в виде СДНФ или СКНФ, могут иметь в своём составе не более чем ${\displaystyle 2^{n}}$ различных термов. Все эти элементарные термы можно представить в виде некоторой структуры, топологически эквивалентной ${\displaystyle n}$-мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения.

На рисунке изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2-мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов:

В случае функции трёх переменных приходится иметь дело с трёхмерным кубом. Это сложнее и менее наглядно, но технически возможно. На рисунке в качестве примера показана таблица истинности для булевой функции трёх переменных и соответствующий ей куб.

Как видно из рисунка, для трёхмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных:

${\displaystyle {\overline {X}}_{1}{\overline {X}}_{2}{\overline {X}}_{3}\vee X_{1}{\overline {X}}_{2}{\overline {X}}_{3}\vee {\overline {X}}_{1}{\overline {X}}_{2}X_{3}\vee X_{1}{\overline {X}}_{2}X_{3}=}$

${\displaystyle ={\overline {X}}_{2}({\overline {X}}_{1}{\overline {X}}_{3}\vee {\overline {X}}_{1}X_{3}\vee X_{1}{\overline {X}}_{3}\vee X_{1}X_{3})={\overline {X}}_{2}({\overline {X}}_{1}\vee X_{1})({\overline {X}}_{3}\vee X_{3})={\overline {X}}_{2}}$

В общем случае можно сказать, что ${\displaystyle 2^{k}}$ термов, принадлежащие одной что ${\displaystyle k}$-мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются ${\displaystyle k}$ переменных.

Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскость, как показано на рисунке. Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) не соответствует порядку следования двоичных чисел записанных в лексикографическом порядке (00 01 10 11), а клетки, находящиеся в крайних столбцах таблицы, соседствуют между собой.

Аналогичным образом можно работать с логическими функциями большего числа переменных.

Традиционно существует несколько стилей представления карт Карно. Часто в шапке и левой колонке проставляются численные значения переменных, подобно тому, как они указаны в таблице истинности (а). В этом стиле наиболее очевидно, что карта Карно является своеобразной формой представления таблицы истинности. Однако клетки карты Карно следуют в несколько ином порядке, чем строки в таблице истинности, так как в таблице истинности принято строки упорядочивать в лексикографическом нарастании двоичных чисел. Например, в карте Карно для четырёх переменных порядок следования ячеек карты и строк таблицы истинности совпадёт, если переставить местами третий-четвёртый столбцы и третью-четвёртую строки карты.

Каждая строка таблицы истинности и каждая клетка карты Карно соответствует одному слагаемому ДНФ, поэтому в шапке и левой колонке карты можно указывать вхождения переменных (прямые и инверсные), как они выглядят в СДНФ (б). Существует сокращённый вариант этого стиля представления, где во вспомогательных строках и колонках указывается, в каком виде, прямом или инверсном, представлена каждая переменная в соответствующей строке или столбце карты (в).

Наконец, в некоторых случаях на краях карты линиями указываются столбцы и строки, где соответствующая переменная представлена в прямом виде (г).

а) б) в) г)

Исходной информацией для работы с картой Карно является таблица истинности минимизируемой функции. Таблица истинности содержит полную информацию о логической функции, задавая её значения на всех возможных 2ⁿ наборах входных переменных X₁ … X_n. Карта Карно также содержит 2ⁿ клеток, каждая из которых ассоциируется с уникальным набором входных переменных X₁ … X_n. Таким образом, между таблицей истинности и картой Карно имеется взаимно однозначное соответствие, и карту Карно можно считать соответствующим образом отформатированной таблицей истинности.

В данном разделе в качестве примера используется функция четырёх переменных, заданная таблицей истинности, изображённой на рис. 2а. Карта Карно для той же функции изображена на рис. 2б.

Рис. 2. Пример работы с картой Карно

Карта Карно может быть построена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно — это таблица истинности, представленная в виде матрицы в 2-мерном виде.

Каждая клетка этой карты соответствует одной строке в классической таблице истинности и обозначается строкой переменных с инверсиями и без инверсий. Например, пусть в таблице истинности для функции 4 переменных ${\displaystyle x_{1},x_{2},x_{3},x_{4},}$ одна из строк имеет вид: 0 1 1 0 | 1, тогда клетка в карте Карно, соответствующая этой строке, будет иметь имя ${\displaystyle {\overline {x}}_{1},x_{2},x_{3},{\overline {x}}_{4}}$ и в этой клетке ставится 1. Указание имён клеток в карте Карно обычно выполняется дополнительной строкой сверху и дополнительным столбцом слева.

Существенно, что в карте Карно соседние клетки обязательно имеют соседние, в смысле расстояния Хэмминга коды, то есть расстояние Хэмминга между соседними клетками равно 1, и различаются только состоянием — с инверсией или без, одной и только одной из переменных. Соседними клетками считаются клетки, примыкающие друг к другу стороной, также соседними клетками считаются клетки крайнего левого и крайнего правого столбцов и клетки первой и последней строк. Таком образом, карта Карно на плоскости топологически эквивалентна поверхности тора в трёхмерном пространстве, или гипертору в пространстве с размерностью на 1 больше размерности соответствующей многомерной карты Карно.

Так как перестановка переменных в логической функции не изменяет саму функцию, то есть, например, ${\displaystyle F(x_{1},x_{2},x_{3},x_{4})=F(x_{4},x_{2},x_{3},x_{1})}$ или, что то же самое, — перестановка столбцов переменных в таблице истинности не изменяет функцию, существует несколько вариантов отображения таблицы истинности на карту Карно с сохранением «соседства» клеток. Но практически наиболее часто карту Карно заполняют, используя нарастающий код Грея для обозначения строк и столбцов. Такой подход гарантирует порождение карты Карно с избеганием субъективных ошибок.

При заполнении карты на пересечении строки и столбца проставляется соответствующее значение из таблицы истинности — 0 или 1. После того как карта заполнена, приступают к минимизации.

Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки, которые содержат единицы, если нужна КНФ, то рассматриваем те клетки, которые содержат нули. Сама минимизация производится по следующим правилам (на примере ДНФ).

1. Объединяем смежные клетки, содержащие единицы, в область так, чтобы одна область содержала ${\displaystyle 2^{n}}$ (${\displaystyle n}$ целое число = 0…${\displaystyle \infty }$) клеток (помним про то, что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток, содержащих нули;
2. Область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки);
3. Несмежные области, расположенные симметрично оси(ей), могут объединяться в одну;
4. Область должна быть как можно больше, а количество областей как можно меньше;
5. Области могут пересекаться;
6. Возможно несколько вариантов покрытия.

Далее берём первую область и смотрим, какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных; если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое, что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией.
Например (для Карт на 2 переменные):

${\displaystyle {\overline {X_{1}}}\ {\overline {X_{2}}}}$

${\displaystyle {\overline {X_{1}}}\ X_{2}}$

${\displaystyle X_{1}\ X_{2}\ }$

${\displaystyle X_{1}\ {\overline {X_{2}}}}$

${\displaystyle {\overline {X_{2}}}}$

${\displaystyle {\overline {X_{1}}}}$

${\displaystyle {X_{2}}\ }$

${\displaystyle {X_{1}}\ }$

${\displaystyle S_{1}\vee S_{2}=}$

${\displaystyle S_{1}\vee S_{2}=}$

${\displaystyle S_{1}\vee S_{2}=}$

${\displaystyle S_{1}\vee S_{2}=}$

${\displaystyle S_{1}\vee S_{2}=}$

${\displaystyle S_{1}\vee S_{2}=}$

${\displaystyle =X_{1}X_{2}\vee }$

${\displaystyle =X_{1}{\overline {X_{2}}}\vee }$

${\displaystyle =X_{2}\vee X_{1}}$

${\displaystyle =X_{1}\vee {\overline {X_{2}}}}$

${\displaystyle ={\overline {X_{1}}}\vee {\overline {X_{2}}}}$

${\displaystyle =X_{2}\vee {\overline {X_{1}}}}$

${\displaystyle \vee {\overline {X_{1}}}\ {\overline {X_{2}}}}$

${\displaystyle \vee {\overline {X_{1}}}X_{2}}$

Для КНФ всё то же самое, только рассматриваем клетки с нулями, неменяющиеся переменные в пределах одной области объединяем в дизъюнкции (инверсии проставляем над единичными переменными), а дизъюнкции областей объединяем в конъюнкцию. На этом минимизация считается законченной. Так, для Карты Карно на рис. 1, выражение в формате ДНФ будет иметь вид:

${\displaystyle f(X_{1},X_{2},X_{3},X_{4})=S_{1}\vee S_{2}\vee S_{3}={\overline {X_{1}}}\ {\overline {X_{4}}}\vee X_{1}\ X_{2}\ X_{4}\vee {\overline {X_{4}}}{\overline {X_{2}}}.}$

В формате КНФ:

${\displaystyle f(X_{1},X_{2},X_{3},X_{4})=S_{1}S_{2}S_{3}=(X_{1}\vee {\overline {X_{4}}})(X_{2}\vee {\overline {X_{4}}})({\overline {X_{1}}}\vee {\overline {X_{2}}}\vee X_{4}).}$

Так же из ДНФ в КНФ и обратно можно перейти, использовав Законы де Моргана.

• ДНФ
• КНФ
• СДНФ
• СКНФ
• Минимизация логических функций методом Куайна
• Минимизация комбинационных схем
• en:Espresso heuristic logic minimizer
• Метод Куайна — Мак-Класки

• Veitch E.W. (May 1952) A Chart Method for Simplifying Truth Functions. Proceedings, Association for Computing Machinery, Pittsburgh, Pa., May 2, 3, 1952, pp. 127—133. DOI:10.1145/609784.609801.
• Karnaugh M. (November 1953) The Map Method for Synthesis of Combinational Logic Circuits. Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics. 72 (5): 593—599. DOI:10.1109/TCE.1953.6371932.
• Токхейм Р. Основы цифровой электроники: Пер. с англ. — М.: Мир, 1988. — 392 с.. ил. (Глава 4, страницы 88—95)
• Гивоне Д. Россер Р. Микропроцессоры и микрокомпьютеры: Вводный курс: Пер. с англ. — М.: Мир, 1983.— 464 с., ил.

• Using Karnaugh maps in practical applications, Разработка схемы управления светофором.

Программное обеспечение

• Karnaugh Minimizer, Коммерческое Windows-приложение (часто работает некорректно, например для этого уравнения: 0,1,5,8,10,13).
• Logic Minimizer, Коммерческое Windows-приложение, но можно сделать, чтобы запускалось на Unix.
• Kmap minimizer Онлайн-приложение (Flash).
• GKMap, свободное ПО на SourceForge.net.
• Karnaugh Map Minimizer, бесплатное (но часто некорректно работающее) ПО на SourceForge.net.
• Gorgeous Karnaugh, коммерческое ПО Gorgeous Karnaugh для минимизации по картам Карно.

• Карты Карно. Лекция. Youtube.