для чего нужна карта карно

15.10.202325.06.2023 admin 0 Comments

Карта Карно

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

Является одним из эквивалентных способов описания или задания логический функций наряду с таблицей истинности или выражениями булевой алгебры. Преобразование карты Карно в таблицу истинности или в булеву формулу и обратно осуществляется элементарным алгоритмом.

Удобство и наглядность такого представления логической функции обусловлено тем, что логические термы, к которым могут быть применены операции попарного неполного склеивания и элементарного поглощения группируются в карте Карно в виде визуально очевидных прямоугольных массивов, содержащих в своих ячейках одинаковые значения (нули и единицы).

История

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

Основные принципы

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

Принципы минимизации

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

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

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

A ∨ A ¯ = 1 ; A A ¯ = 0. =1;A=0.>

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

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

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

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

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

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

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

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

Стили представления карт Карно

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

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

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

Порядок работы с картой Карно

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

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

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

Принципы склейки

Прямоугольную область в карте Карно, которая состоит из 2k одинаковых значений (единиц или нулей в зависимости от того, какую форму нужно получить) будем называть склейкой, группой или областью. Распределение всех имеющихся в карте Карно нулей (единиц) по склейкам будем называть покрытием. С целью минимизации булевой функции необходимо построить такое покрытие карты Карно, чтобы количество склеек было минимальным, а размер каждой склейки максимально возможным. Для этого необходимо руководствоваться следующими правилами.

Карты с неопределёнными значениями

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

Такие клетки могут произвольным образом включаться в любые склейки, а также могут не включаться ни в какие склейки, то есть их по желанию можно доопределять и как 1, и как 0.

Преобразование карты в формулу

Описание

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

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

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

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

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

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

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

Примеры

Пример 1

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

Для краткости обозначим родственников Коли через буквы:
мама — X1
папа — X2
дедушка — X3
бабушка — X4

Условимся обозначать согласие родственников единицей, несогласие — нулём. Возможность пойти погулять обозначим буквой f, Коля идёт гулять — f = 1, Коля гулять не идёт — f = 0.
Составим таблицу истинности:

Перерисуем таблицу истинности в 2-мерный вид:

Переставим в ней строки и столбцы в соответствии с кодом Грея (последний и предпоследний столбец меняют местами). Получили Карту Карно:

Заполним её значениями из таблицы истинности (первая строка не соответствует таблице истинности, так как f=0 и разрешения на гулять нет):

Минимизируем в соответствии с правилами:

= X 3 X 4 ∨ X 1 X 2 ∨ X 2 X 4 ∨ X 1 X 4 ∨ X 1 X 3 ∨ X 2 X 3

Теперь по полученной минимальной ДНФ можно построить логическую схему:

Из-за отсутствия в наличии шестивходового элемента ИЛИ, реализующего функцию дизъюнкции, пришлось каскадировать пяти- и двух-входовые элементы (D7, D8).

= ( X 1 ∨ X 2 ∨ X 3 ) ( X 1 ∨ X 3 ∨ X 4 ) ( X 2 ∨ X 3 ∨ X 4 ) ( X 1 ∨ X 2 ∨ X 4 )

Источник

Электростанции

Меню раздела

Метод карт Карно

Метод карт Карно служит для наглядного представления и упрощения нормальной формы ИЛИ. Он был придуман математиком Карно, и его еще называют методом диаграмм Карно.

Карта Карно для двух переменных

Карты Карно могут быть представлены в виде таблиц истинности для полных конъюнкций.
3—2114
Карты Карно всегда имеют количество полей, равное количеству возможных полных конъюнкций.
При двух переменных возможны 4 полные конъюнкции. Таким образом, карта Карно для двух переменных должна иметь 4 поля (см. рис. 5.12). По краям карты записываются переменные. Каждая переменная величина должна быть представлена в инвертированной и в неинвертированной форме (рис. 5.12).
Переменные по краям являются координатной сеткой. Они определяют, какая полная конъюнкция какому полю принадлежит. На рис. 5.13 по своим полям расписаны 4 полных конъюнкции.

Поле полной конъюнкции А а В обозначено координатами А и В
(рис. 5.13). Соответственно поле полной конъюнкции А а В находится по
координатам А и В. Так как полные конъюнкции определяются координатами, то нет необходимости записывать их в полной форме, как на рис. 5.13. Наличие полной конъюнкции может обозначаться 1 в соответствующем поле.
1 в поле карты Карно означает наличие полной конъюнкции.
На карте Карно (рис. 5.14) отмечены полные конъюнкции А а В и А а В. Карта Карно отражает следующую нормальную форму ИЛИ:
Z = (AaB)v(AaB).
Символ Z в верхнем левом углу карты на рис. 5.14 показывает, что полные конъюнкции относятся к Z.
Отсутствующие полные конъюнкции обозначены нулем в соответствующем поле, или поле не заполняется.
Присваивание переменных координатам карты Карно производится произвольным образом.
Также возможно менять местами А и В на карте (рис. 5.15). Разумеется, переменные могут иметь совершенно другие обозначения, например Ег и Ег Прямое и инверсное значения переменной должны обязательно находиться на одной стороне карты.
Другое распределение координатных переменных ведет, естественно, к другому распределению полных конъюнкций по полям карты.
Желательно придерживаться определенной схемы распределения переменных и не менять ее без причины. Для облегчения работы рекомендуется первую переменную, например А, и ее инверсию все время ставить на верхнюю часть карты. Вторую переменную (например В) и ее инверсию ставить на левую часть карты.

Покажем на примере заполнение карты Карно нормальной формой ИЛИ и восстановление нормальной формы ИЛИ по карте Карно.
Пример 1
Занесите в карту Карно нормальную форму ИЛИ:
Z = (Л л В) v (А л В) v (Л а В).
Сначала нужно нарисовать карту Карно с данными координатами. Затем найти поля с полными конъюнкциями, присутствующими в нормальной форме и обозначить их 1. Результат показан на рис. 5.16.

Пример 2—————————————————————
Запишите нормальную форму ИЛИ, представленную на карте Карно (рис. 5.17).
Нормальная форма ИЛИ содержит 2 полные конъюнкции: одна А д В, вторая АлВ. Следовательно, нормальная форма:
W = (АлВ)ч(АлВ).
Представленная на карте Карно нормальная форма ИЛИ может быть упрощена при наличии определенных условий.
«Соседние» полные конъюнкции можно объединять в «группы».
Соседними считаются полные конъюнкции, клетки которых имеют общие стороны (рис. 5.18). Если клетки с полными конъюнкциями имеют только общий угол, то они не являются соседними.

Рис. 5.18. Соединение и несоединение конъюнкции

В одной группе могут быть объединены 2 или 4 соседние полные конъюнкции.
Каждая группа имеет определенные координаты. Группа слева наверху на карте Карно (рис. 5.18) имеет по одной стороне координату Д по другой —
координату А и А.
Содержание группы характеризуется ее координатами. Переменные, чьи координаты присутствуют в прямой и инверсной форме одновременно, исключаются.
Представленная на рис. 5.19 группа имеет координаты А, В ж В. Переменная В имеет как прямую, так и инверсную формы. Следовательно, она исключается. Значение группы будет А. Нормальная форма ИЛИ

Это упрощение может быть проверено с помощью алгебры логики.

Особый случай представляет группа из 4 полных конъюнкций (рис. 5.20).
Она имеет координаты А, А, В, В. Значит, переменные Аж В исключаются. Значение группы равно 1. Справедливость этого можно доказать с помощью таблицы истинности. Алгебра логики также приведет к этому результату:
Z = (А а В) v (А а В^ v (А а В> v [А а В^;
Z = [А а (В v 5)] v \_А а (В v 5)];
Z = (AaI)v(AaI);
Z = Av А;
Z = l.

На одной карте можно образовать несколько групп (рис. 5.21). Одна полная конъюнкция может присутствовать в нескольких группах.
При наличии нескольких групп упрощенное уравнение получается в результате логического сложения значений отдельных групп.
Для карты (рис. 5.21) значения групп получаются равными А и В.
Упрощенное уравнение:
Z = AvB.
На карте Карно (рис. 5.20) можно образовать также две группы из двух полей. Тогда получится упрощенное уравнение, но не в самом простом виде. Покажем это. На рис. 5.22 показана карта Карно с такой группировкой. Значения групп равны В ж В. Упрощенное уравнение, следовательно:
Z = Bv В.
Сложение переменной величины с ее инверсией дает в итоге по правилам алгебры логики 1. Поэтому самой простой формой уравнения является Z = 1.
Для максимального упрощения уравнения необходимо образовывать группы как можно большего размера.
Чтобы закрепить полученные знания, решим следующий пример.
Пример 3——————————————————-
Максимально упростите при помощи карты Карно нормальную форму ИЛИ. Запишите упрощенное уравнение:
X = (AaB)v(AaB)v(AaB).
Сначала полные конъюнкции заносятся в карту (рис. 5.23).

Рис. 5.23. Карта Карно

Затем образуются две группы по два поля. Они имеют значения А и В. Упрощенное уравнение:
X = А а В.

Карта Карно для трех переменных

Для трех переменных возможны 8 различных полных конъюнкций (рис. 5.24). Следовательно, карта Карно для трех переменных должна иметь 8 клеток.
Распределение переменных по координатам может происходить, как и в карте для двух переменных любым образом. Однако целесообразно первые переменные поместить на верхнюю сторону диаграммы, а вторые величины — на левую сторону диаграммы. Третья переменная величина размещается на нижней стороне диаграммы. Для переменных величин А, В и С карта Карно изображена на рис. 5.25.

Рис. 5.28. Группировка по принципу расширенного соседства

Карту Карно сложно представлять в виде цилиндра. Поэтому предпочитают форму на рис. 5.25, соблюдая принцип расширенного соседства. На рис. 5.28 представлены соседние полные конъюнкции и их группировки.
Группа из двух клеток на верхней диаграмме имеет в итоге значение В и С.
Группа из четырех клеток на нижней диаграмме имеет значение С. Группа должна быть прямоугольной или квадратной. Группа, изображенная на рис. 5.28а, недопустима.

Рис. 5.28а. Недопустимая группа карты Карно

Рассмотрим несколько примеров работы с картами Карно для трех переменных.
Пример 1——————————————————————-
Заполните карту Карно полными конъюнкциями следующего уравнения:
Y — <^А а В а v а В а v а В а v [А а В а С).
Сначала надо правильно разместить полные конъюнкции по ячейкам (рис. 5.29). Запись лучше производить в алгебраической форме, тогда можно легко контролировать правильность выбора ячейки.
Каждую полную конъюнкцию обозначим 1 (рис. 5.30). При отсутствии затруднений можно сразу же рисовать обычную карту Карно.

Пример 2———————————————————————
Занесите данную нормальную форму ИЛИ в карту Карно и максимально упростите:
Z — (А а В а С) v <А а В л С) v <А а В л С) v а В л С1).
Имеющиеся полные конъюнкции обозначаются 1 (рис. 5.31). Затем производится группировка. Группу из четырех элементов образовать невозможно. Зато можно образовать 3 группы из двух клеток. Однако выделенная пунктиром группа является избыточной, так как двумя основными серыми группами все 1 уже охвачены. Если бы мы выбрали пунктирную группу в качестве основной, найденное уравнение не было бы максимально простым.

Рис. 5.31. Карта Карно к примеру 2
Верхняя серая группа (рис. 5.31) имеет значение А а В. Значение нижней серой группы — В а С. (Переменная А выпадает, так как встречается в координатах этой группы как в прямой, так и в инверсной формах.) Значения групп логически складываются. При этом получается упрощенное уравнение:
Z = (AaB)v(B аС).
Пример 3————————————————————-
Запишите нормальную форму ИЛИ, заключенную в карте Карно (рис. 5.32).

Рис. 5.32. Карта Карно к примеру 3

Максимально упростите нормальную форму ИЛИ.
Нормальная форма ИЛИ по карте Карно:
Z = [А аВ aC^v (А а В aC)v <А аВ aC^v <А а В aC>v (А аВ aC^v А аВ аС.
Могут быть образованы 2 группы из четырех клеток. Одна имеет значение В, другая С. Упрощенное уравнение:
Z = BvC.
Так как возможно образование двух больших групп из четырех клеток, то получается значительное упрощение нормальной формы.

Карта Карно для четырех переменных

Карта Карно для четырех переменных должна иметь 16 клеток, так как возможны 16 различных полных конъюнкций (рис. 5.33). Карта Карно для четырех переменных изображена на рис. 5.34.

Переменные обозначены, как и раньше, А, В и С. Плюс добавлена переменная величина D. Разумеется, переменные могут быть обозначены иначе, например Ev Е2, Е3, Ег 16 полных конъюнкций показаны на рис. 5.35.
Для карт Карно с четырьмя переменными действуют правила, ранее установленные для карт Карно, со следующими дополнениями:

Рис. 5.35. Карта карно для четырех переменных с занесенными полными конъюнкциями

В одной группе могут быть объединены 2, 4, 8 или 16 соседних полных конъюнкций.
Карта Карно для четырех переменных имеет форму шара. Поэтому клетки, находящиеся в противоположных концах одной строки или столбца, являются соседними.
Разъясним подробнее принцип расширенного соседства. Рассмотрим рис. 5.36. Карта (а) показывает, что группы из двух клеток можно образовать не только из полных конъюнкций, которые находятся на концах одной строки, но и из полных конъюнкций, находящихся на концах одного столбца.

Рис. 5.36. Группировка по принципу расширенного соседства

‘ <А /\ В аС a (А л В лС л Z)).
Для большей наглядности полные конъюнкции отмечены серыми номерами. Они обозначают соответствующие клетки. На рис. 5.38 показана искомая диаграмма.

Рис. 5.38. Карта Карно к примеру 1

Пример 2—————————————————————-
Для задач управления требуется схема, удовлетворяющая таблице истинности (рис. 5.39). Эта схема должна быть максимально простой.