1. 4. 4. Графічний метод мінімізації функцій

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

Діаграми Вейча і карти Карно для перемикальних функцій двох, трьох і чотирьох аргументів відповідно зображені на рис. ,а, б. Усередині клітинок вказані номери наборів.

Графічні методи призначені для ручної мінімізації. Наочність цих методів зберігається за невеликої кількості аргументів. При цьому відшукання імплікант не формалізоване, і успіх мінімізації цілком визначається кваліфікацією оператора.

Кожна клітинка відповідає конституенті. Прямокутник, що містить клітинок ( ), відповідає імпліканті. Прямокутник максимального розміру відповідає простій імпліканті.

Обґрунтуванням графічного методу мінімізації є той факт, що розташовані поруч клітинки відповідають сусіднім наборам аргументів, що відрізняються значенням однієї змінної і, таким чином. Можуть бути склеєні за методом Квайна. За змінних кожна клітинка має сусідніх клітинок.

Чим більше клітинок містить прямокутник, тим менше букв входить у записі імпліканти. Імпліканта містить тільки ті змінні, котрі приймають однакові значення для всіх клітинок прямокутника.

Наведемо етапи мінімізації перемикальних функцій графічним методом.

1. Заповнити діаграму Вейча або карту Карно. Значення функцій записують у клітинки, що відповідають номерам наборів.

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

3. Визначити МДНФ. Сукупності простих імплікант, що входять у МДНФ, відповідає мінімальна множина прямокутників, що покривають усі одиниці.

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

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

Приклад. Виконати мінімізацію перемикальних функцій трьох аргументів, заданих таблицею істинності за допомогою діаграм Вейча.

Таблиця істинності

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	0 1 1 1 0 1 1 0	1 0 0 1 1 1 1 1	0 1 1 1 1 1 0 1

Заповнимо діаграми Вейча і знайдемо мінімальну кількість прямокутників максимального розміру, що покривають усі одиниці (рис. ).

У результаті отримаємо МДНФ функцій :

;

;

.

Приклад. За допомогою метода Вейча виконати мінімізацію перемикальної функції чотирьох аргументів, заданої ДНФ загального вигляду

.

Числами визначені номери наборів. Які відповідають одиничним значенням конституенти та імплікант.

Заповнимо діаграму Вейча і знайдемо мінімальну кількість прямокутників максимального розміру, що покривають ядро функції (рис. )

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

;

;

;

.

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

Діаграми (карти) Вейча Діаграми (карти) Карно

Рис. 1. 9. Діаграми (карти) Вейча і Карно: а) для двох змінних;

б) для трьох змінних; в) для чотирьох змінних.

Кожна клітинка діаграми відповідає набору змінних булевої функції в її таблиці істиності. На рис. 1. 9 показана ця відповідність. Якщо булева функція приймає одиничне значення на деякому наборі, в клітинці діаграми, що відповідає даному набору, ставиться одиниця. Нульові значення булевої функції в діаграмі не ставляться. Для булевої функції трьох змінних діаграми Вейча та Карно мають вигляд, показаний на рис. 1. 9, б. Додавання до неї ще такої ж таблиці дає діаграму для функції 4-х змінних (рис. 1. 9, в). Таким же чином, тобто приписуванням ще одної діаграми 4-х змінних до щойно розглянутої, можна одержати діаграму для функції 5-ти змінних і т. д. Однак діаграми для функцій з числом змінних більше 4-х застосовуються рідко.

Для діаграм Вейча (чи Карно) властиве наступне:

- кожній клітинці діаграми відповідає свій набір;

- сусідні набори розташовані поряд в рядку чи в стовпці. Сусідніми називаються набори, що відрізняються одною компонентою. Нагадаємо, що конституенти, відповідні таким наборам, склеюються. Наприклад, для функції, заданої табл. 1. 15, конституенти, відповідні парі одиниць в стовпці лівої частини діаграми склеюються і породжують елементарний добуток із 2-х букв:

Таблиця 1. 15

Стовпці, розташовані на краях діаграми, теж

вважаються сусідніми:

	1
1	1		1

Відзначимо, що одержуваний елементарний добуток легко визначити одразу по діаграмі: це добуток змінних, що приймають одне й те ж значення в обох клітинках.

Для нашого прикладу наявне ще одне склеювання для пари одиниць в лівій частині діаграми. В результаті даного склеювання одержуємо елементарний добуток : . Із розглянутих раніше методів мінімізації нам відомо, що можливе подальше склеювання одержуваних елементарних добутків. На діаграмах Вейча чи Карно вони також розташовуються поряд.

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

Мінімізація булевої функції полягає в знаходженні мінімального накриття всіх одиниць діаграми блоками із одиниць, розташованих у сусідніх клітинках діаграми. При цьому завжди вважається, що лівий край діаграми

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

Розглянемо кілька прикладів.

Приклад 1. Булева функція має ДДНФ вигляду

.

Знайти мінімальну ДНФ за допомогою діаграми Вейча.

Діаграма Вейча, відповідна функції представлена в табл. 1. 16. В

даному випадку мінімальне накриття всіх

Таблиця 1. 16 одиниць діаграми можливе тільки блоками по

дві одиниці. Кожному такому блоку відповідає

своя кон’юнкція:

	1	1	1
	1		1

;

;

.

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

.

Очевидно, проста імпліканта не потрібна для одержання МДНФ.

Приклад 2. Булеві функції , , , , , задані таблицею істиності (табл. 1. 17). Знайти їх мінімальні ДНФ. Таблиця 1. 17

0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1	0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1	0 0 0 1 0 1 1 0 0 0 1 1 1 0 1 1	0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0	0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0	0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1	1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1

Записуємо одиниці у клітинки діаграм Вейча, котрі відповідають наборам, на яких функції приймають значення 1. Діаграми Вейча булевих функцій зображені на рис. 1. 10, там же показані мінімальні

					1
1	1				1	1	1	1
	1	1			1		1
	1	1				1

	1	1				1	1
1			1		1			1
1			1			1	1
	1	1				1	1

	1	1			1			1
1	1	1	1		1	1	1
1	1	1	1			1	1
	1	1			1			1

Рис. 1. 10. Діаграми Вейча булевих функцій , , , , , .

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

.

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

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

Мінімальне накриття всіх одиниць діаграми функції можливе трьома блоками: блоком з двох одиниць і двома блоками з чотирьох одиниць кожний. Мінімальна ДНФ має вигляд: .

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

Мінімальне накриття всіх одиниць на діаграмі Вейча функції здійснюється трьома блоками: один блок із двох одиниць і два блоки із чотирьох одиниць. Мінімальна ДНФ функції має вигляд:

.

З наведених прикладів видно, що кожній імпліканті функції відповідає на діаграмі прямокутник, котрий містить клітинок з одиницями ( .

Чим більше клітинок містить прямокутник, тим менше букв входить у представлення імпліканти. Імпліканта містить тільки ті змінні, котрі приймають однакове значення для всіх клітинок прямокутника.

Отже, в загальному випадку для мінімізації булевих функцій за допомогою діаграм (карт) Вейча чи Карно необхідно:

- одержати ДДНФ заданої функції;

- згідно таблиці істиності даної функції нанести одиниці на діаграму (карту) Вейча чи Карно;

- об’єднати сусідні одиниці діаграми в блоки для одержання мінімального накриття всіх одиниць на діаграмі;

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

- об’єднати одержані елементарні імпліканти (по одній у кожному блоці) операцією АБО.

Одержаний в результаті цих дій вираз і є не що інше як мінімальна ДНФ булевої функції.