Карта Карно

Зазвичай, значні обчислення потрібні для отримання мінімального виду булевої функції, однак карта Карно зменшує потребу таких обчислень завдяки:

• Використанню можливості людського розуму по розпізнаванню шаблонів для визначення які терми мають бути поєднані для отримання найпростішого виразу.
• Дозволяє швидко визначити та видалити потенційні стани гонитв, які неминучі в булевих рівняннях.
• Забезпечує найкращу допомогу в спрощенні до шістьох змінних, однак з більшою кількістю змінних стає складно розрізнити оптимальні шаблони.
• Допомагає в навчанні про булеві функції та їх мінімізацію.

Карта Карно зазвичай становиться важкою для розпізнання при збільшені кількості змінних. Загальне правило таке, карта Карно добре працює до чотирьох-п'яти змінних, і не має використовуватись з більше ніж шістьома змінними. Для виразів з більшою кількістю змінних може бути використаний Метод Куайна — Мак-Класкі. Сьогодні здебільшого для процесу мінімізації використовуються комп'ютери, для яких евристичний алгоритм еспресо став стандартною програмою мінімізації.

Кожна змінна має два значення: початкове та обернене. Змінні впорядковуються згідно з кодом Грея, тобто тільки одна змінна змінюється між двома суміжними комірками. У відповідні комірки записуємо вихідні значення функції.

Коли карта Карно заповнена, для отримання мінімізованої функції "1"-ці або "0"-лі групуються в найбільші можливі прямокутні групи, в яких кількість комірок в групі має дорівнювати степеню 2.[1] Наприклад, група може складатися з 4 комірок в лінію, 2 в висоту і 4 в ширину, 2 на 2 і так далі. Байдужий стан (зазвичай позначений Х) групується тільки тоді, коли група отримана з його використанням більша ніж без нього. Комірки можуть бути використані більше ніж один раз тільки якщо завдяки цьому утворюється менша кількість груп. Кожна "1" або "0" має бути задіяна як мінімум в одній групі.

У випадку використання карти Карно для частково заданих функцій в комірках, що відповідають невикористаним вхідним наборам проставляємо "Х" (зірочки, тильди тощо). Ці комірки при необхідності включаються в контури разом з "1" (при отримані формули на базі ДНФ), або "0" (при отримані формули на базі КНФ). При цьому функція після мінімізації виявляється простішою. Розглянемо карту Карно представлену на малюнку праворуч. Якщо при побудові функції не враховувати байдужі стани, то отримаємо функцію утворену трьома контурами ${\displaystyle f(E,F,G,H)=({\overline {E}}{\overline {F}}G)+(E{\overline {F}}{\overline {G}}{\overline {H}})+({\overline {E}}{\overline {F}}H)}$ на наступному кроці отримаємо ${\displaystyle f(E,F,G,H)=({\overline {E}}{\overline {F}}(G+H))+(E{\overline {F}}{\overline {G}}{\overline {H}})}$. Ця функція значно спроститься якщо використовувати байдужі стани при виділенні контурів. При цьому утворюється лише один контур (на малюнку вказаний пунктиром). В результаті отримаємо ${\displaystyle f(E,F,G,H)=({\overline {F}})}$.

Кожна отримана в карті Карно група продукує кон'юнкцію змінних, що не міняють своє значення в межах окресленої області, якщо змінна нульова, тоді в кон'юнкції ставимо заперечення. Аналогічні дії виконуємо для всіх груп (контурів). Кон'юнкції об'єднуємо диз'юнкцією.

Для побудови інверсної функції групуємо "0" замість "1".

Діаграма Венна для 4 множин з числами (0-15). Відповідає раніше показаній карті Карно для чотирьох зміних A, B, C, D.

Кожна комірка карти Карно відповідає мінтерму. Малюнок праворуч показує розташування кожного мінтерма на карті. Діаграма Венна для чотирьох множин названих A, B, C, D посилається на карту Карно представлену на попередньому малюнку:

• Змінна А карти Карно відповідає множині А діаграми Вена; і так далі.
• Мінтерм m0 карти Карно відповідає ділянці 0 в діаграмі Вена; і так далі.
• Мінтерм m9 це ABCD (1001) в карті Карно відповідає перетину ділянок А і D.

Таким чином, кожен мінтерм визначає унікальний перетин всіх чотирьох множин. Діаграма Вена може містити безкінечну кількість множин і все ще відповідати відповідній карті Карно. Із збільшенням множин і змінних, і діаграма Вена, і карта Карно стають складнішими для малювання і управління.

Решітка є тороїдально зв'язна, таким чином прямокутні групи можуть утворюватися через края. Наприклад, m9 може бути згрупована з m1; так само як m0, m8, m2, та m10 можуть утворити групу 4*4.

Розмір карти Карно для n булевих змінних становить 2ⁿ.

• 
  k-карта для 2-х змінних
• 
  k-карта для 3-х змінних
• 
  k-карта для 4-х змінних

Використавши визначені мінтерми, наступна таблиця істинності може бути створена.

#	${\displaystyle A}$	${\displaystyle B}$	${\displaystyle C}$	${\displaystyle D}$	${\displaystyle f(A,B,C,D)}$
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	1
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0

K-карта показує мінтерми і комірки, що покривають бажані мінтерми. Коричневий регіон є місцем перетину червоного і зеленого регіонів.

Існує 16 варіантів комбінації вхідних змінних, таким чином карта Карно має 16 позицій, і організована у вигляді решітки 4*4.

Двійкові цифри в карті показують вихід функції для будь-якої комбінації на вході. Таким чином 0 вписаний в верхню ліву комірку решітки через те, що ƒ = 0 коли A = 0, B = 0, C = 0, D = 0. Зауважте, що значення впорядковані згідно з кодом Грея, значить рівно одна змінна змінюється між двома суміжними комірками.

Після конструювання карти Карно наше завдання знайти мінімальні терми для використання в кінцевому виразі. Ці терми знаходяться шляхом окреслення груп 1-ць в карті. Група має бути прямокутною і мати площу, що дорівнює ступеню двійки (тобто 1, 2, 4, 8…). Прямокутник має бути максимально великим і без 0-в. Оптимальне групування в матриці позначене зеленим, червоним і синім. Зауважте, що групи можуть перетинатися. Зона перетинання червоної і зеленої групи позначена коричневим.

Решітка тороїдально зв'язна, що означає, що прямокутні групи обгортатися навколо країв, таким чином ${\displaystyle \scriptstyle A{\overline {D}}}$ правильний терм, хоч і не частина мінімального набору, він покриває мінтерми 8, 10, 12 і 14.

Можливо важче уявити такий терм ${\displaystyle \scriptstyle {\overline {B}}\,{\overline {D}}}$, який обгортається навколо всіх чотирьох вершин, він покриває такі терми 0, 2, 8, 10.

Коли карта Карно побудована і отримані групи, розв'язок може бути отриманий шляхом виключення надлишкових змінних використавши аксіоми булевої алгебри.

Для червоної групи:

• Змінна ${\displaystyle A}$ має одне й те саме значення (1) в кожній комірці групи, значить вона має бути включена в терм червоної групи.
• Змінна ${\displaystyle B}$ змінює своє значення, отже має бути виключена.
• ${\displaystyle C}$ завжди 0. Через те, що ${\displaystyle C}$ 0, вона має бути обернена (записана із символом інверсії, ${\displaystyle {\overline {C}}}$) перед включенням.
• ${\displaystyle D}$ змінюється.

Таким чином перший терм виглядає ${\displaystyle A{\overline {C}}.}$

Для зеленої групи ми бачимо, що ${\displaystyle A}$ та ${\displaystyle B}$ зберігають одне значення, а ${\displaystyle D}$ змінюється. ${\displaystyle B}$ - 0 і має бути обернене перед включенням. Отже другий терм ${\displaystyle A{\overline {B}}.}$

Аналогічно, синя група дає ${\displaystyle BC{\overline {D}}.}$

Розв'язки усіх груп об'єднуються в: ${\displaystyle A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}.}$

Інверсія функції знаходиться таким самим шляхом, тільки групуються 0.

Три терма, що покривають інверсну функцію показані сірими прямокутниками з границями різного кольору.

• коричнева—${\displaystyle {\overline {A}}\,{\overline {B}}}$
• золота—${\displaystyle {\overline {A}}\,{\overline {C}}}$
• синя—${\displaystyle BCD}$

Це породжує інверсію:

${\displaystyle {\overline {F}}={\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD}$

Після використання законів де Моргана, може бути визначена КНФ:

${\displaystyle {\overline {\overline {F}}}={\overline {{\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD}}}$

${\displaystyle F=\left(A+B\right)\left(A+C\right)\left({\overline {B}}+{\overline {C}}+{\overline {D}}\right)}$

Попередня к-карта з доданим ${\displaystyle A{\overline {D}}}$ термом для уникнення стану гонитви

Карта Карно корисна для виявлення та виключення станів гонитви. Їх дуже легко визначити використовуючи карту Карно через те, що умови гонитви існують, коли рухаєшся між будь-якою парою суміжних але роз'єднаних, груп окреслених на карті.

• В попередньому прикладі, потенційно умови гонитви існують, коли C 1 і D 0, A 1, і B змінюється з 1 на 0 (пересуваємось із синьої зони в зелену). В цьому випадку, вихід має залишатися рівним 1, але через те, що цей перехід не покритий специфічним термом в рівнянні, існує потенційна небезпека глюка (коротокочасного переходу в виходу в стан 0).
• Другий глюк може важче помітити: коли D 0 і A та B обидва 1, зі зміною C з 1 в 0 (при переході з блакитного стану в червоний).

Який з цих глюків може статися залежить від фізичної реалізації, і чи потрібно нам хвилюватися залежить від програми.

В цьому випадку, додатковий терм ${\displaystyle A{\overline {D}}}$ виключить можливість станів гонитв, ставши мостом між зеленим і синім вихідними станами, а також між синім і червоним вихідними станами: це показано як жовтий регіон.

Цей терм зайвий в системах статичної логіки, але така надлишковість часто потрібна в реальних динамічних системах.

Аналогічно, додатковий терм ${\displaystyle {\overline {A}}D}$ має бути доданим в інверсну функцію для уникнення потенційних станів гонитви. Застосував закони де Моргана створюємо інший добуток сум для F, з новим чинником ${\displaystyle \left(A+{\overline {D}}\right)}$.

Далі наведені усі можливі к-карти від двох змінних 2 × 2. Для кожного варіанта прописана мінімальні пряма і інверсна функції стійкі до стану гонитви.

• 
  ${\displaystyle \sum _{}}$(0); K = 0
• 
  ${\displaystyle \sum _{}}$(1); K = A′B′
• 
  ${\displaystyle \sum _{}}$(2); K = AB′
• 
  ${\displaystyle \sum _{}}$(3); K = A′B
• 
  ${\displaystyle \sum _{}}$(4); K = AB
• 
  ${\displaystyle \sum _{}}$(1,2); K = B′
• 
  ${\displaystyle \sum _{}}$(1,3); K = A′
• 
  ${\displaystyle \sum _{}}$(1,4); K = A′B′ + AB
• 
  ${\displaystyle \sum _{}}$(2,3); K = AB′ + A′B
• 
  ${\displaystyle \sum _{}}$(2,4); K = A
• 
  ${\displaystyle \sum _{}}$(3,4); K = B
• 
  ${\displaystyle \sum _{}}$(1,2,3); K = A′ + B′
• 
  ${\displaystyle \sum _{}}$(1,2,4); K = A + B′
• 
  ${\displaystyle \sum _{}}$(1,3,4); K = A′ + B
• 
  ${\displaystyle \sum _{}}$(2,3,4); K = A + B
• 
  ${\displaystyle \sum _{}}$(1,2,3,4); K = 1