Метод діаграм Вейча

булеві Функції

Метод діаграм Вейча.

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

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

Додавання до неї ще такий же таблиці дає діаграму для функції 4-х змінних (табл. 4.4.3).

Таким же чином, т. Е. Приписуванням ще однієї діаграми 3-х змінних до щойно розглянутої, можна отримати діаграму для функції 5-ти змінних і т. Д. Однак діаграми для функцій з числом змінних більше 4-х використовуються рідко. Для наведених діаграм характерно наступне:
  • кожній клітині діаграми відповідає свій набір;
  • сусідні набори розташовані поруч в рядку або в стовпці.
Сусідніми наборами називаються набори, що відрізняються однією компонентою. Нагадаємо, що констітуенти, відповідні таким наборам, склеюються (див. Метод Квайна- Мак-Класки). Наприклад, для функції, заданої табл. 9.22,

констітуенти, відповідні парі одиниць в лівій частині таблиці, склеюються і породжують елементарне твір з 2-х букв:


Про парі одиниць в правій частині діаграми можна сказати те ж саме:


Відзначимо, що получающееся елементарне твір легко визначити відразу по діаграмі: це твір змінних, що приймають одне і те ж значення в обох клітинах.
Ще одне важливе зауваження: стовпці, розташовані по краях діаграми, теж вважаються сусідніми. Для нашого прикладу це означає, що має місце ще одне склеювання, в результаті якого, слідуючи вказаному правилу, отримуємо елементарне твір x2 / x3 З розглянутих раніше методів нам відомо, що можливе подальше склеювання одержуваних елементарних творів. На діаграмах Вейча вони теж розташовуються поруч. Загальне правило склеювання на діаграмах Вейча можна сформулювати наступним чином: склеюванню підлягають прямокутні конфігурації, заповнені одиницями і містять число клітин, що є ступенем 2. Получающееся нове елементарне твір визначається як добуток змінних, які не змінюють свого значення на всіх склеюваних наборах. Число m залишилися змінних в елементарному творі визначається легко:


де n - число змінних функції, М - число, що склеюються наборів. Метод широко використовується на практиці, завдяки простоті і зручності. Після невеликого тренування досягається елементарний навик визначення мінімальної ДНФ по діаграмі "з першого погляду". Мінімізація булевої функції полягає в знаходженні мінімального накриття всіх одиниць діаграми Вейча блоками з одиниць (зазначеної конфігурації), розташованих в сусідніх клітках діаграми. При цьому завжди вважається, що лівий край діаграми Bейча 4-х змінних примикає до її правому краю, а верхній oкрай діаграми примикає до нижнього її краю. Після отримання мінімального накриття всіх одиниць діаграми Вейча, мінімальна ДНФ булевої функції записується як диз'юнкція елементарних кон'юнкція, відповідних виділеним блокам одиниць в діаграмі. Розглянемо кілька прикладів.

Приклад. Булева функція f має наступну СДНФ:


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

Отже, мінімальна ДНФ функції має вигляд:

Схожі статті