-
Вступ
- 1 Принципи мінімізації
- 2 Опис
- 3 Приклади
- 3.1 Приклад 1
- 3.2 Приклад Карти Карно на п'ять змінних
- 3.3 Приклад великий Карти Карно на вісім змінних
Мал. 1 Приклад Карти Карно
Карта Карно - графічний спосіб мінімізації перемикальних (булевих) функцій, що забезпечує відносну простоту роботи з великими виразами і усунення потенційних гонок. Являє собою операції попарного неповного склеювання і елементарного поглинання. Карти Карно розглядаються як перебудована відповідним чином таблиця істинності функції. Карти Карно можна розглядати як певну плоску розгортку n-мірного булева куба.
Карти Карно були винайдені в 1952 Едвардом В. Вейч і вдосконалені в 1953 Морісом Карно, фізиком з «Bell Labs», і були покликані допомогти спростити цифрові електронні схеми.
В карту Карно булеві змінні передаються з таблиці істинності і упорядковуються за допомогою коду Грея, в якому кожне наступне число відрізняється від попереднього тільки одним розрядом.
1. Принципи мінімізації
Основним методом мінімізації логічних функцій, представлених у вигляді СДНФ або СКНФ, є операція попарного неповного склеювання і елементарного поглинання. Операція попарного склеювання здійснюється між двома термами (членами), що містять однакові змінні, входження яких (прямі і інверсні) збігаються для всіх змінних, крім однієї. В цьому випадку всі змінні, крім однієї, можна винести за дужки, а що залишилися в дужках пряме і інверсне входження однієї змінної піддати склейці. наприклад:
Аналогічно для КНФ:
Можливість поглинання випливає з очевидних рівностей
Таким чином, головним завданням при мінімізації СДНФ і СКНФ є пошук термів, придатних до склейки з подальшим поглинанням, що для великих форм може виявитися досить складним завданням. Карти Карно надають наочний спосіб відшукання таких термів.
Як відомо, булеві функції N змінних, представлені у вигляді СДНФ або СКНФ, можуть мати в своєму складі 2 N різних термів. Всі ці члени складають деяку структуру, топологічно еквівалентну N -мірним кубу, причому будь-які два терми, з'єднані ребром, придатні для склеювання і поглинання.
На малюнку зображена проста таблиця істинності для функції з двох змінних, що відповідає цій таблиці 2-мірний куб (квадрат), а також 2-мірний куб з позначенням членів СДНФ і еквівалентна таблиця для угруповання термів:
У разі функції трьох змінних доводиться мати справу з тривимірним кубом. Це складніше і менш наочно, але технічно можливо. На малюнку як приклад показана таблиця істинності для булевої функції трьох змінних і відповідний їй куб.
Як видно з малюнка, для тривимірного випадку можливі більш складні конфігурації термів. Наприклад, чотири терма, що належать одній грані куба, об'єднуються в один терм з поглинанням двох змінних:
У загальному випадку можна сказати, що 2 K термів, що належать одній K -мірною межі гіперкуба, склеюються в один терм, при цьому поглинаються K змінних.
Для спрощення роботи з булевими функціями великого числа змінних був запропонований наступний зручний прийом. Куб, що представляє собою структуру термів, розгортається на площину як показано на малюнку. Таким чином з'являється можливість представляти булеві функції з числом змінних більше двох у вигляді плоскої таблиці. При цьому слід пам'ятати, що порядок кодів термів в таблиці (00 01 11 10) не відповідає порядку проходження двійкових чисел, а клітини, що знаходяться в крайніх стовпчиках таблиці, сусідять між собою.
Аналогічним чином можна працювати з функціями чотирьох, п'яти і більше змінних. Приклади таблиць для N = 4 і N = 5 наведені на малюнку. Для цих таблиць слід пам'ятати, що сусідніми є клітини, які знаходяться в відповідних клітинах крайніх стовпців і відповідних клітинах верхньої і нижньої лінійки. Для таблиць 5 і більше змінних потрібно враховувати також, що квадрати 4х4 віртуально знаходяться один над одним в третьому вимірі, тому відповідні клітини двох сусідніх квадратів 4х4 є сосоеднімі, і відповідні їм терми можна склеювати.
2. Опис
Карта Карно може бути складена для будь-якої кількості змінних, однак зручно працювати при кількості змінних не більше п'яти. По суті Карта Карно - це таблиця істинності складена в 2-х вимірному вигляді. Завдяки використанню коду Грея в ній верхній рядок є сусідній з нижньої, а правий стовпець сусідній з лівим, таким чином вся Карта Карно згортається в фігуру тор (бублик). На перетині рядка і стовпця проставляється відповідне значення з таблиці істинності. Після того як Карта заповнена, можна приступати до мінімізації.
Якщо необхідно отримати мінімальну ДНФ, то в Карті розглядаємо тільки ті клітини які містять одиниці, якщо потрібна КНФ, то розглядаємо ті клітини, які містять нулі. Сама мінімізація проводиться за такими правилами (на прикладі ДНФ):
- об'єднуємо суміжних клітин, що містять одиниці, в область так, щоб одна область містила 2 n (n ціле число = 0 ...) клітин (пам'ятаємо про те, що крайні рядки і стовпці є сусідніми між собою), в області не повинно знаходитися клітин, що містять нулі;
- область повинна розташовуватися симетрично осі (їй) (осі розташовуються через кожні чотири клітини);
- НЕ суміжні області, розташовані симетрично осі (їй), можуть об'єднуватися в одну;
- область повинна бути якомога більше, а кількість областей якомога менше;
- області можуть перетинатися;
- можливо кілька варіантів накриття.
Далі беремо першу область і дивимося які змінні не змінюються в межах цієї області, виписуємо кон'юнкцію цих змінних, якщо незмінний змінна нульова, проставляємо над нею інверсію. Беремо наступну область, виконуємо те ж саме що і для першої, і т. Д. Для всіх областей. Кон'юнкції областей об'єднуємо диз'юнкція.
Наприклад (для Карт на 2-ве змінні):
Для КНФ все те ж саме, тільки розглядаємо клітини з нулями, не змінюються змінні в межах однієї області об'єднуємо в диз'юнкції (інверсії проставляємо над одиничними змінними), а диз'юнкції областей об'єднуємо в кон'юнкцію. На цьому мінімізація вважається закінченою. Так для Карти Карно на рис.1 вираження в форматі ДНФ матиме вигляд:
У форматі КНФ:
Так само з ДНФ в КНФ і назад можна перейти використавши Закони де Моргана.
3. Приклади
3.1. приклад 1
У хлопчика Колі є мама, тато, дідусь і бабуся. Коля піде гуляти на вулицю, якщо йому дозволять хоча б двоє родичів.
Для стислості позначимо родичів Коли через букви:
мама - х1
папа - х2
дідусь - х3
бабуся - х4
Домовимося позначати згода родичів одиницею, не згода нулем. Можливість піти погуляти позначимо літерою f, Коля йде гуляти - f = 1, Коля гуляти не йде - f = 0.
Складемо таблицю істинності:
Перерісуем таблицю істинності в 2-х мірний вид:
Переставимо в ній рядки і стовпці відповідно до кодом Грея. Отримали Карту Карно:
Маємо таку таблицю істинності:
Карта Карно буде виглядати наступним чином (для кращого візуального сприйняття в Карту нулі не записує):
Неправильно (на прикладі ДНФ):
- - Область S1 - накрита правильно;
- - Область S2 - порушує п.1;
- - Область S3 - порушує п.2;
- -Області S4 і S6 - не виконують п.3, це не є помилкою - вираз вийде більше ніж якби S4 і S6 представляли собою одну область;
- - Область S5 - порушує п.1 за кількістю клітин і по неприпустимість знаходження нулів в області.
Правильно, але не оптимально:
Ця карта Карно мінімізована неоптимально, так як можна об'єднати одиниці, що входять в члени S3 і S5.
Мінімізувавши цю Карту отримуємо наступну ДНФ:
Складемо мінімальну КНФ:
Інший варіант тієї ж самої Карти Карно:
Нічого не змінюється тільки в рядках записано три змінних, а в стовпчиках дві.
3.3. Приклад великий Карти Карно на вісім змінних
Припустимо, за наявною таблиці істинності складена така Карта Карно:
Знайдемо мінімальну ДНФ: