Мінімізація методом діаграм Вейча
Найпоширеніші способи графічного представлення перемикальних функцій від невеликого числа змінних – це карти Карно та їхній різновид – діаграми Вейча.
Діаграма Вейча являє собою організовану особливим чином таблицю істинності перемикальної функції. Розташування клітинок цієї таблиці дозволяє легко визначити члени, що склеюються між собою. Через особливості геометричного представлення діаграми Вейча й інтерпретації одержуваних за її допомогою результатів, найбільш розповсюдженими є діаграми Вейча для функцій трьох чи чотирьох логічних змінних.
На рис.3, приведена діаграма Вейча для функції трьох змінних. Кожній клітинці діаграми відповідає визначений набір значень змінних. У дужках зазначені номери наборів таблиці істинності, що відповідають даній клітинці діаграми Вейча.
а)
б)
в)
Рис.3. Діаграма Вейча для функції трьох змінних:
а – представлення за таблицею істинності;
б – представлення за ДДНФ;
в – представлення за ДКНФ
Якщо дану таблицю розглядати як циліндр, утворений з'єднанням першого й останнього стовпчиків, то тоді склеювані між собою конституенти одиниці (рис.3,б) чи нуля (рис.3,в) у діаграмах Вейча будуть розташовані в сусідніх клітинках. При цьому прямокутники, що покривають 2k сусідніх клітинок, описують імліканту (імпліценту), що має ранг (n-k), де n – число змінних, від яких залежить функція.
Положення змінних, що задають координати клітинок діаграми Вейча, може бути іншим. Однак при цьому повинна забезпечуватися можливість завдання на діаграмі всіх наборів змінних. Природно, що при таких змінах поміняються номери клітинок, але на процес і результат мінімізації перемикальної функції дана обставина впливу не зробить.
Клітинки, що містять у діаграмі Вейча одиниці, будемо називати 1-клітинками, а клітинки, що містять нулі – 0-клітинками. Основна властивість діаграм Вейча полягає в тому, що будь-яка первинна імпліканта рангу n-m утворить на ній прямокутник і тільки прямокутник 1-клітинок площею 2m, де n – кількість змінних, від яких залежить функція. Такі прямокутники називають m-кубами (m=0,1,…,n...; 0-кубу відповідає мінтерм, а n-кубу – константа "одиниця"). Так, будь-яка пара одиниць у сусідніх клітинках діаграми Вейча для логічної функції трьох змінних представляється імплікантою другого рангу. Чотири одиниці, що утворять прямокутник, виражаються однією змінною (з запереченням чи без нього).
Щоб записати первинну імпліканту, що представляє собою деякий m-куб на діаграмі Вейча, необхідно просто скласти кон’юнкцію тих змінних, котрі в межах даного m-куба зберігають постійні значення (тільки прямі чи тільки інверсні).
Таким чином, одержання мінімальної ДНФ за допомогою діаграм Вейча зводиться до відшукання мінімального числа m-кубів максимального розміру, що складаються з 1-клітинок, і складання диз'юнкції імплікант, що відповідають цим m-кубам (кожна 1-клітинка повинна ввійти хоча б в один m-куб, будь-яка 1-клітинка може входити одночасно в кілька різних m-кубів).
При одержанні МДНФ за допомогою діаграми Вейча необхідно звернути увагу на наступне:
m-кубу, що покриває 2m 1-клітинок, відповідає первинна імпліканта, яка не залежить від m змінних, причому виключаються ті m змінних, котрі в прямокутній області на діаграмі Вейча, що складається з 1-клітинок, мають різне значення (пряме та інверсне);
прямокутні області на діаграмі Вейча, що використовуються при мінімізації, можуть складатися тільки з 2m сусідніх клітинок, де m = 0,1,…,n;
кожна клітинка на діаграмі Вейча, поза залежністю від способу розмітки цієї діаграми, має рівно n сусідніх клітинок; у зв'язку з цим діаграма Вейча представляється нанесеною на поверхню відповідного тіла (циліндра – для випадку трьох змінних, тора – для випадку чотирьох змінних);
пошук мінімального покриття 1-клітинок варто починати з вибору тих 1-клітинок, які можуть ввійти в один і тільки один m-куб, а потім обрані у такий спосіб 1-клітинки покриваються m-кубами максимального розміру; якщо після цього на діаграмі залишаються 1-клітинки, що не ввійшли ні в один з m-кубів, то варто розглянути кілька варіантів покриття цих клітинок з метою мінімізації результату.
Одержання мінімальної КНФ проводиться аналогічним чином стосовно 0-клітинок.
На рис.4 приведена діаграма Вейча для функції чотирьох змінних. Кожній клітинці діаграми відповідає визначений набір значень змінних. У дужках зазначені номери наборів таблиці істинності, що відповідають даній клітинці. Необхідно відзначити, що, як і у випадку трьох змінних, положення клітинок діаграми, що відповідають тому чи іншому номеру набору таблиці істинності, міняється при зміні розмітки таблиці щодо змінних. Однак на результат мінімізації це не впливає.
Перший та останній стовпчики діаграми, а також верхній та нижній рядок варто вважати сусідніми. Тому діаграму Вейча для функції чотирьох змінних варто представляти нанесеною на поверхню тора.
а)
б)
в)
Рис. 4. Діаграма Вейча для функції чотирьох змінних
а) представлення за таблицею істинності;
б) представлення за ДДНФ;
в) представлення за ДКНФ
Приклад 3. Одержати методом діаграм Вейча мінімальну ДНФ для наступної ФАЛ:
Етап 1: занести значення функції на діаграму Вейча:
|
¯d |
d |
¯d |
|
|
a |
|
|
|
|
¯c |
|
1 |
1 |
|
c |
|
¯a |
|
1 |
1 |
1 |
|
1 |
|
|
1 |
¯c |
|
|
b |
¯b |
|
||
Етап 2: відзначити на діаграмі 1-клітинки, що входять у єдиний m-куб:
|
¯d |
d |
¯d |
|
|
a |
|
|
|
|
¯c |
|
1 |
1 |
|
c |
|
¯ |
|
1 |
1 |
1 |
|
1 |
|
|
1 |
¯c |
|
|
b |
¯b |
|
||
a
Етап 3: набір 2, що залишився непокритим, включити в m-куб максимального розміру. Через те, що обидва альтернативних покриття являють собою 1-куби, функція буде мати дві мінімальні ДНФ:
|
¯d |
d |
¯d |
|
|
a |
|
|
|
|
¯c |
|
1 |
1 |
|
c |
|
¯ a |
|
1 |
1 |
1 |
|
1 |
|
|
1 |
¯c |
|
|
b |
¯b |
|
||
|
¯d |
d |
¯d |
|
|
a |
|
|
|
|
¯c |
|
1 |
1 |
|
c |
|
¯ a |
|
1 |
1 |
1 |
|
1 |
|
|
1 |
¯c |
|
|
b |
¯b |
|
||
Приклад 4. Одержати методом діаграм Вейча мінімальну ДНФ для ФАЛ, задану скороченим записом ДДНФ:
Етап 1: занести значення функції на діаграму Вейча:
|
¯d |
d |
¯d |
|
|
a |
|
|
1 |
|
¯c |
1 |
|
1 |
1 |
c |
|
¯a |
|
1 |
1 |
1 |
|
|
|
|
1 |
¯c |
|
|
b |
¯b |
|
||
Етап 2: відзначити на діаграмі 1-клітинки, що входять у єдиний m-куб:
|
¯d |
d |
¯d |
|
|
a |
|
|
1 |
|
¯c |
1 |
|
1 |
1 |
c |
|
¯a |
|
1 |
1 |
1 |
|
|
|
|
1 |
¯c |
|
|
b |
¯b |
|
||
Етап 3: оскільки всі 1-клітинки ввійшли в який-небудь з m-кубів, то залишилося тільки записати мінімальну ДНФ:
Необхідно звернути
увагу на те, що, як вказувалося вище, не
слід починати пошук покриттів з відшукання
m-кубів
максимально можливої площини. Так, у
даному випадку 1-клітинки (2,3,10,11) можна
було б включити в 2-куб (
c).
Однак при цьому все рівно збереглася б
необхідність покриття інших 1-клітинок
1-кубами. Тому даний 2-куб в остаточний
варіант покриття входити не повинен.
|
¯d |
d |
¯d |
|
|
a |
|
|
1 |
|
¯c |
1 |
|
1 |
1 |
c |
|
¯a |
|
1 |
1 |
1 |
|
|
|
|
1 |
¯c |
|
|
b |
¯b |
|
||
Приклад 5. Одержати методом діаграм Вейча мінімальні КНФ і ДНФ логічної функції, заданої у вигляді скороченого запису ДКНФ:
Одержання мінімальної КНФ
Етап 1: занести значення функції на діаграму Вейча, представлену на рис. 4а, поміщаючи нулі в клітинки, що відповідають зазначеним при завданні функції наборам:
|
¯d |
d |
¯d |
|
|
a |
|
0 |
|
|
¯c |
0 |
|
0 |
0 |
c |
|
¯a |
0 |
0 |
0 |
0 |
|
|
0 |
|
|
¯c |
|
|
b |
¯b |
|
||
Етап 2: відзначити на діаграмі 0-клітинки, що входять у єдиний m‑куб:
|
¯d |
d |
¯d |
|
|
a |
|
0 |
|
|
¯c |
0 |
|
0 |
0 |
c |
|
¯a |
0 |
0 |
0 |
0 |
|
|
0 |
|
|
¯c |
|
|
b |
¯b |
|
||
Етап 3: оскільки всі 0-клітинки ввійшли в який-небудь з m-кубів, то записати єдину мінімальну КНФ:
Одержання мінімальної ДНФ
Етап 1: заповнити 1-клітинки для заданої перемикальної функції, поміщаючи одиниці в клітинки, що залишилися незаповненими в процесі одержання МКНФ:
|
¯d |
d |
¯d |
|
|
a |
1 |
|
1 |
1 |
¯c |
|
1 |
|
|
c |
|
¯a |
|
|
|
|
|
1 |
|
1 |
1 |
¯c |
|
|
b |
¯b |
|
||
Етап 2: відзначити на діаграмі 1-клітинки, що входять у єдиний m‑куб:
|
¯d |
d |
¯d |
|
|
a |
1 |
|
1 |
1 |
¯c |
|
1 |
|
|
c |
|
¯a |
|
|
|
|
|
1 |
|
1 |
1 |
¯c |
|
|
b |
¯b |
|
||
Відзначимо, що 1-клітинки (0,4,8,12) у сукупності на поверхні тора, утвореного діаграмою Вейча, складають 2‑ куб.
Етап 3: оскільки всі 1-клітинки ввійшли в який-небудь з m-кубів, то запишемо єдину мінімальну ДНФ:
