Пример Карты Карно на пять переменных

Карта Карно

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

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

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

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

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

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

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

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

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

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

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

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

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

Аналогичным образом можно работать с функциями четырёх, пяти и более переменных. Примеры таблиц для N=4 и N=5 приведены на рисунке. Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки. Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4х4 виртуально находятся друг над другом в третьем измерении, поэтому соответственные клетки двух соседних квадратов 4х4 являются сосоедними, и соответствующие им члены можно склеивать.

Описание

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

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

1. объединяем смежные клетки содержащие единицы в область, так чтобы одна область содержала 2ⁿ (n целое число = 0… ) клеток(помним про то что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток содержащих нули;
2. область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки);
3. не смежные области расположенные симметрично оси(ей) могут объединятся в одну;
4. область должна быть как можно больше, а кол-во областей как можно меньше;
5. области могут пересекаться;
6. возможно несколько вариантов накрытия.

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

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

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

Примеры

Пример 1

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

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

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

Заполним её значениями из таблицы истинности:

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

1. 1. Все области содержат 2^n клеток;
2. 2. Так как Карта Карно на четыре переменные оси располагаются на границах Карты и их не видно (подробнее смотри пример Карты на 5 переменных);
3. 3. Так как Карта Карно на четыре переменные все области симметрично осей — смежные между собой (подробнее смотри пример Карты на 5 переменных);
4. 4. Области S3, S4, S5, S6 максимально большие;
5. 5. Все области пересекаются (не обязательное условие);
6. 6. В данном случае рациональный вариант только один.

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

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

Составим мин. КНФ:

Пример Карты Карно на пять переменных

Имеем такую таблицу истинности:

Карта Карно будет выглядеть следующим образом (для лучшего визуального восприятия в Карту нули не записываем):

Неправильно (на примере ДНФ):

• — Область S1 — накрыта правильно;
• — Область S2 — нарушает п.1;
• — Область S3 — нарушает п.2;
• -Области S4 и S6 — не выполняют п.3, это не является ошибкой — выражение получится больше чем если бы S4 и S6 представляли собой одну область;
• — Область S5 — нарушает п.1 по кол-ву клеток и по недопустимости нахождения нулей в области.

Правильно, но не оптимально:

Эта карта Карно минимизирована неоптимально, так как можно объединить единицы, входящие в члены S3 и S5.

Минимизировав эту Карту получаем следующую ДНФ:

Оптимально:

Составим минимальную КНФ:

Другой вариант той же самой Карты Карно:

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: