Метод Вейча – Карномінімізації логічних функцій

Розглянутий у п. 2.6 метод Квайна придатний для мінімізації логічних функцій будь-якої кількості аргументів, з можливістю програмної реалізації. У той же час при розв’язанні завдань розробки дискретних пристроїв обробки даних, автоматики та управління ставиться задача мінімізації ЛФ невеликого числа змінних. Коли база ЛФ містить не більше 6 змінних, зручним інструментом мінімізації є метод, заснований на застосуванні карт Карно (діаграм або таблиць Вейча-Карно).

На карті Карно логічна функція n змінних задається спеціальною формою таблиці істинності – у вигляді розкресленого прямокутника, в якому кількість клітинок дорівнює 2ⁿ можливих наборів у базі ЛФ. Якщо кількість змінних n парна, то кількості рядків та стовпчикiв в таблиці дорівнюють 2^n/2, якщо непарна, то кількість рядків дорівнює , а кiлькiсть стовпців – .

Правила складання карт Карно передбачають подання вихідної ЛФ звичайною таблицею істинності або у вигляді ДДНФ (ДКНФ), що рівносильно в сенсі можливості виявлення повного переліку конституент одиниці (нуля).

Задання ЛФ таблицєю карти Карно здійснюється наступним чином: якщо вихідна функця подається у ДДНФ (ДКНФ), то слід записати одиниці (нулі) в клітинках, що відповідають наборам, на яких вона прймає значення 1 (0), а решту клітинок залишити порожніми. Для того щоб вибір клітинок був однозначним, потрібно шляхом розмітки таблиці забезпечити взаємно-однозначну відповідність між 2ⁿ клітинками таблиці і 2ⁿ можливими n-елементними наборами в базі ЛФ.

Рядки та стовпці таблиці в карті Карно розмічаються по гранях таблиці (зліва направо та зверху вніз) символами змінних із запереченням та без нього, наборами змінних в кількості від 1 до n–1. Набори змінних на гранях таблиці розмічаються так, що два сусідні набори в стовпці або рядку відрізняються значенням однієї змінної: в одному наборі вона з запереченням, а в сусідньому – без нього. При цьому вважається, що кожна клітинка таблиці, що примикає до грані таблиці, є сусідньою до клітинки, яка примикає до протилежній грані і розміщена на тієї ж горизонталі або вертикалі. Виконанням цих умов забезпечується входження кожної змінної в половину клітинок таблиці з запереченням, а в іншу половину – без заперечення. За такою розміткою кожна клітинка пов’язується відношенням взаємно-однозначної відповідності з єдиним набором із бази ЛФ, який являє собою об’єднання в кортеж довжиною n наборів змінних, якими помічені рядок і стовпець, на перетині котрих знаходиться ця клітинка. Цією відповідністю забезпечується однозначність вибору клітинки, в який може бути записано значення ЛФ на будь-якому з наборів із бази ЛФ.

Ілюстрацією розмітки таблиці на карті Карно може служити рис. 2.6, де в клітинках таблиці записані формули кон’юнкцій для 8 наборів функції f(x₁,x₂,x₃), поданої в ДДНФ, а верхними індексами відмічені десяткові номери цих наборів.

При заданні конкретної ЛФ у ДДНФ певні кон’юнкції мають статус конституент одиниці і замість них у відповідних клітинках таблиці (рис. 2.6) записують одиниці, а решта клітинок залишаються порожніми (1-й та 4-й стовпці таблиці вважаються сусідніми). Якщо ж у клітинках, що не відповідають конституентам одиниці, проставити нулі, то ми одержимо таблицю істинності ЛФ у кон’юнктивній формі, в якій дотримується взаємно-однозначна відповідність між наборами змінних ЛФ, значеннями ЛФ на цих наборах та кон’юнктивними доданками ДДНФ, включаючи конституенти одиниці та надлишкові кон’юнкції.

При завданні ЛФ у ДКНФ в клітинках таблиці з такою ж розміткою рядків і стовпців, як на рис. 2.6, будуть записані диз’юнкції тих самих змінних (рис. 2.7).

Для конкретної ЛФ певні диз’юнкції мають статус конституент нуля і замість них у відповідних клітинках таблиці записуються нулі, а решта клітинок залишаються порожніми. Якщо ж у клітинках, що не відповідають конституентам нуля, проставити одиниці, то ми одержимо таблицю істинності ЛФ у диз’юнктивній формі, в якій дотримується взаємно-однозначна відповідність між наборами змінних ЛФ, значеннями ЛФ на цих наборах та диз’юнктивними сумножниками ДКНФ, включаючи конституенти нуля та надлишкові диз’юнкції.

З порівняння рис. 2.6 і 2.7 можна помітити неоднакове розміщення номерів наборів, а значить, і значень ЛФ по клітинках таблиць. Цей недолік карти Карно для ДКНФ (рис. 2.7) можна усунути, помінявши місцями диз’юнкції, відповідні наборам за номерами 0 і 7, 1 і 6, 5 і 2, 3 і 4, в результаті чого розмітка клітинок в таблиці карти Карно стане такою як на рис. 2.8. Тут кожна диз’юнкція являє собою інверсію кон’юнкції з тієї ж клітинки таблиці рис. 2.6, наприклад, = (закон де Моргана).

Правомірність заповнення клітинок таблиці по формі рис. 2.8 випливає з того, що за правилами складання конституент одиниці та нуля (див. приклад 2.10, п. 2.6) для одного й того ж самого набору вони є взаємно інверсними. Отже, за умови запису конституент одиниці та нуля по формулах, наведених у табл. 2.6 і 2.8, можна скласти і використовувути в процедурі мінімізації ЛФ універсальну карту Карно, в якій клітинки таблиці, що відповідають конституентам одиниці у складі ДДНФ, заповняються одиницями, а решта клітинок – нулями (вони відповідають конституентам нуля у складі ДКНФ).

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

Процедура мінімізації ЛФ, поданої у ДДНФ (ДКНФ) або таблицею істинності (що рівносильно), за допомогою побудованої карти Карно здійснюється наступним чином.

Етап 1. Виконують побудову контурів, якi охоплюють клітинки з одиницями (нулями), дотримуючись наступних правил:

1) контур має бути замкненим (овальним, прямокутним або квадратним);

2) контур повинен охоплювати тільки клітинки з одиницями (нулями);

3) кількість клітинок всередині контуру повинна бути цілим степенем числа 2, тобто 1,2,4,8, ...;

4) кожний контур повинен охопити максимально можливу кiлькiсть одиниць (нулей), тому що чим більше одиниць (нулей) в контурі, тим коротша імпліканта (імпліцента), що покриває конституенти, відповідні клітинкам, які охоплені цим контуром;

5) всі одиниці (нулі) повинні бути охоплені контурами (у зв'язку з неповним склеюванням конституент допускається перетинання контурів);

6) при побудові контурів нижній і верхній рядки та лівий і правий стовпці таблиці вважаються сусідніми (змикаються при згортанні полотна таблиці у циліндр).

Етап 2. Одержують аналітичний вираз тупікової ДНФ (КНФ), маючі на увазі наступне:

а) спільною власною частиною всіх конституент одиниці (нуля), відповідних клітинкам, що охоплені контуром, визначається проста імпліканта (імпліцента), яка поглинає ці конституенти. Що більше одиниць (нулей) охоплює контур, то коротша імпліканта, яка покриває конституенти одиниці (нуля), відповідні клітинкам, що охоплені контуром. Якщо контур охоплює лише одну одиницю (нуль), тобто одну клітинку, то простою імплікантою (імпліцентою) буде відповідна конституента одиниці (нуля);

б) загальна кількість імплікант (імпліцент) в тупиковій ДНФ (КНФ) буде дорівнювати числу побудованих контурів, причому зайвих імплікант (імпліцент) не буде. Якщо варіант побудови системи контурів є єдиним, то одержана тупикова ДНФ (КНФ) буде мінімальною. У противному випадку з числа одержаних у різних варіантах побудови контурів тупикових ДНФ (КНФ) вибирають мінімальну за кількістю символів в її формулі.

Отже, вираз ЛФ у вигляді тупікової ДНФ (КНФ) записують за такими правилами:

1) кількість простих імплікант (імпліцент) дорівнює кількості контурів на карті Карно;

2) у кожній імпліканті (імпліценті) залишаються тільки ті змінні охоплених відповідним контуром конституент одиниці (нуля), які є іхньою спільною власною частиною, а ті змінні, по яким ці конституенти склеюються, в імпліканти (імпліценти) не включаються.

Помітимо, що метод мінімізації за допомогою карт Карно може застосовуватись також для неповністю (частково) визначених ЛФ, поданих у ДНФ (КНФ), і мінімізувати їх шляхом “вдалого” довизначення. У цьому випадку будуються також контури, що містять хоча б одну одиницю (нуль) і в які включаються, шляхом довизначення, додаткові одиниці (нулі).

Оскільки застосування карт Карно розглядається стосовно до задач мінімізації ЛФ, база яких містить невелику (не більше ніж 6) змінних, то найкращим способом засвоєння “технології” побудови карт Карно та розв’язання задач мінімізації ЛФ цим методом є розгляд зразкових прикладів. Для більшої наочності аргументи ЛФ будемо позначати прописними буквами A, B, C, D, G, V. Почнемо з простішого випадку, коли ставиться задача мінімізації логічної функції двох змінних.

Отже, карту Карно можна оформлювати з будь-якою розміткою рядків і стовпців таблиці, але тільки так, щоб кожна клітинка відповідала певному (і єдиному) набору з бази ЛФ і щоб сусідні набори, как по горизонталі так и по вертикалі, відрізнялись між собою тільки значенням однієї змінної: в однієї клітинці вона із запереченням, а в сусідньої – без нього. При цьому слід мати на увазі, що клітинки, розташовані на протилежних гранях таблиці у кожному рядку або стовпцю, також є сусідними.