Карта карно

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

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

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

Сокращенная ДНФ[править]

Например:
содержится в .

Функцию можно записать с помощью сокращенной ДНФ не единственным способом.

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

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

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

X¯1X2X3X4∨X¯1X2X¯3X4=X¯1X2X4(X3∨X¯3)=X¯1X2X4⋅1=X¯1X2X4.{\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}.}

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

(X¯1∨X2∨X3∨X4)(X¯1∨X2∨X¯3∨X4)=X¯1∨X2∨X4∨X3X¯3=X¯1∨X2∨X4∨=X¯1∨X2∨X4.{\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}.}

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

A∨A¯=1;AA¯={\displaystyle A\vee {\overline {A}}=1;A{\overline {A}}=0.}

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

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

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

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

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

X¯1X¯2X¯3∨X1X¯2X¯3∨X¯1X¯2X3∨X1X¯2X3={\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}=}

=X¯2(X¯1X¯3∨X¯1X3∨X1X¯3∨X1X3)=X¯2(X¯1∨X1)(X¯3∨X3)=X¯2{\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}}

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

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

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

Пример

Найдем минимальную форму функции

Члены СДНФ в двоичной нотации:

• 0000 = 0
• 0001 = 1
• 0010 = 2
• 0011 = 3
• 0101 = 5
• 0111 = 7
• 1000 = 8
• 1010 = 10
• 1100 = 12
• 1101 = 13
• 1111 = 15

Группировка:

0000 = 0

1

• 0001 = 1
• 0010 = 2
• 1000 = 8

2

• 0011 = 3
• 0101 = 5
• 1010 = 10
• 1100 = 12

3

• 0111 = 7
• 1101 = 13

4

1111 = 15

Склейка 1:

• 0, 1 = 000-
• 0, 2 = 00-0
• 0, 8 = -000
• 1, 3 = 00-1
• 1, 5 = 0-01
• 2, 3 = 001-
• 2,10 = -010
• 8,10 = 10-0
• 8,12 = 1-00
• 3,7 = 0-11
• 5,7 = 01-1
• 5,13 = -101
• 12,13 = 110-
• 7,15 = -111
• 13,15 = 11-1

Группировка 2:

• 0, 1 = 000-
• 2, 3 = 001-
• *12,13 = 110-

• 0, 2 = 00-0
• 1, 3 = 00-1
• 8,10 = 10-0
• 5,7 = 01-1
• 13,15 = 11-1

• 1, 5 = 0-01
• *8,12 = 1-00
• 3,7 = 0-11

• 0, 8 = -000
• 2,10 = -010
• 5,13 = -101
• 7,15 = -111

Склейка 2:

• *0,1,2,3 = 00–
• *0,2,8,10 = -0-0
• *5,7,13,15 = -1-1
• *1,3,5,7 = 0–1

Итого, члены сокращенной формы:

• 12,13 = 110-
• 8,12 = 1-00
• 0,1,2,3 = 00–
• 0,2,8,10 = -0-0
• 5,7,13,15 = -1-1
• 1,3,5,7 = 0–1

Редукция:

Кружком обведены члены ядра.

Ядро, таким образом, включает члены -0-0 и -1-1. Для получения минимальной формы, нам нужно перекрыть дополнительно столбцы 1, 3, 12. Для этого можно взять, например, 0,1,2,3 = 00– и 12,13 = 110-:

\

Карта Карно:

Минимизация булевых функций

В данном сервисе для минимизации булевых функций используются метод Квайна и карт Карно-Вейча. После получения минимальной формы имеется возможность заново построить логическую схему. Если исходная схема понадобится в дальнейшем, то ее можно предварительно сохранить (меню Действия/Сохранить).

1. Kx v K ≡ K — тождество поглощения;
2. Kx v Kx ≡ K — тождество склеивания;
3. Kx v Ky ≡ K(xvy) — дистрибутивный закон,

K_iii_i

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

Операции►
Удалить

Операции

• Сохранить как docx
• Сохранить как png

Количество переменныхСетка

После минимизации можно получить логическую схему функции и построить таблицу истинности (кнопка Далее)
Далее

Этот метод используется для БФ не более, чем с шестью аргументами и основан на тождестве склеивания: Kx v Kx ≡ K — две элементарные конъюнкции (ЭК) склеиваются, если они отличаются только знаком инверсии одного аргумента. Чтобы облегчить нахождение таких пар (четверок, восьмерок,…) склеивающихся ЭК, используют специальное представление БФ в виде таблицы – карты Карно (другое название — диаграмма Вейча). Чтобы заполнить карту Карно необходимо щелкнуть левой мышкой на соответствующую ячейку.
Карта Карно обладает той особенностью, что две ПЭК, соответствующие соседним клеткам карты, отличаются знаком инверсии только одного аргумента, т.е. их можно склеивать. Причем соседними являются не только клетки, например, с номерами 1 и 3, но и клетки с номерами 12 и 8, 12 и 4, т.е. карту можно «сворачивать» в цилиндр, соединяя горизонтальные (вертикальные) ее границы.
Две единицы «склеиваются» каждый раз, когда они стоят рядом в строке или столбце (карту можно свернуть в цилиндр). В результате склеивания число букв, входящих в ПЭК, уменьшается на единицу.

3. Примеры

3.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).
Составим мин. КНФ:

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

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

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

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

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

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

Оптимально:

Составим минимальную КНФ:
Другой вариант той же самой Карты Карно:

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

3.3. Пример большой Карты Карно на восемь переменных

Предположим, по имеющейся таблице истинности составлена такая Карта Карно:
Найдём минимальную ДНФ:
Минимальная КНФ:

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

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

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

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

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

• Склейку клеток карты Карно можно осуществлять по единицам (если необходимо получить ДНФ) или по нулям (если требуется КНФ).
• Склеивать можно только прямоугольные области с числом единиц (нулей) 2n, где n — целое число, при этом рекомендуется брать максимальное из возможных значений n. В некоторых ситуациях в раскладке образуется единица или ноль, которую невозможно склеить с какой-либо областью. В этом случае единица склеивается «сама с собой». Для карт Карно с числом переменных более четырёх могут получаться более сложные области, о чём будет сказано в следующих разделах.
• Область, которая подвергается склейке, должна содержать только единицы (нули).
• Крайние клетки каждой горизонтали и каждой вертикали также граничат между собой (топологически карта Карно для четырёх переменных представляет собой тор) и могут объединяться в прямоугольники. Следствием этого правила является смежность всех четырёх угловых ячеек карты Карно для N=4. Если во всех четырёх угловых ячейках стоят единицы (нули), они могут быть объединены в квадрат, как показано на рис. 2в.
• Все единицы (нули) должны попасть в какую-либо область.
• С точки зрения минимальности ДНФ (КНФ) число областей должно быть как можно меньше (каждая область представляет собой терм), а число клеток в области должно быть как можно больше (чем больше клеток в области, тем меньше переменных содержит терм. Терм размером 2n ячеек содержит N—n переменных).
• Одна ячейка карты Карно может входить сразу в несколько областей. Это следует из очевидного свойства булевых функций: повторение уже существующего слагаемого (сомножителя) не влияет на функцию:

A∨A=A;A⋅A=A.{\displaystyle A\vee A=A;A\cdot A=A.}

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