Мінімізація булевих функцій методом карт Карно (діаграм Вейча)

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

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

(0, 1) і (1, 0) відрізняються значеннями обох змінних. У кар­тах Карно інтерпретації двох змінних розташовуються у такій послідовності: (0, 0), (0, 1), (1, 1), (1,0). У цій послідовності перша та остання інтерпретації також відрізняються значенням тільки однієї змінної, тому перший і останній рядки (стовпці) таблиці вважаються сусідніми (протилежні границі таблиці вважаються співпадаючими). При такому розташуванні мінтер-ми, до яких застосовна операція склеювання, розташовуються у сусідніх клітках карти, і склеювання проводиться графічно за допомогою об єднання кліток у групи.

Карти Карно для функцій двох змін­них мають вид таблиці 2х2, де стовпці відповідають значенням першої змінної, а рядки — значенням другої змінної. На рис. 4.1 зображено структури карти Кар­но, в клітках вказано відповідні мінтерми у виді формул з абстрактними змінними.

Структура карти Карно для функцій трьох змінних має вид таблиці 2 х 4, де стовпці відповідають всіляким наборам значень перших двох змінних, а рядки — значенням Oil третьої змінної (рис. 4.2). В клітках структури вказано відповідні мінтерми з абстрактни­ми змінними.

Для конкретної булевої функції карта Карно заповнюєть­ся таким чином. У клітках, що відповідні інтерпретаціям, на яких функція дорівнює одиниці, записують одиниці. Ці клітки відповідають конституентам одиниці, що присутні у ДДНФ функції. В інші клітки записують нулі.

Розв'язок. Побудова карти Карно для заданої функції: поміщаємо одиниці до кліток, що відповідають мінтермам, які присутні в даній ДДНФ, і нулі — в решту кліток (рис. 4.3).

До конституентів одиниці, що відповідають будь-яким двом сусіднім кліткам, можна застосувати операцію склею­вання, оскільки вони відрізняються тільки однією змінною. Зауважимо, що на карті Карно для функції трьох змінних кожна клітка має три сусідні клітки, на карті Карно для функ­ції чотирьох змінних — чотири, на карті Карно для функції п'яти змінних — п'ять тощт. При цьому для кліток на кар­ті Карно функції трьох змінних, розташованих у крайньому правому або у крайньому лівому стовпцях, сусідніми є кліт­ки, що розташовані безпосередньо зліва (або справа), вище (або нижче) у сусідньому рядку, і крайня ліва (або права) у тому ж рядку. Як приклад на рис. 4.4 відзначено клітки, сусідні з клітками А і В.