Графічний метод мінімізації функцій
Одержати МДНФ перемикальної функції, минаючи етапи формування скороченої і тупикової ДНФ, можна, застосувавши діаграми Вейча або карти Карно.
Діаграми Вейча і карти Карно для перемикальних функцій двох, трьох і чотирьох аргументів відповідно зображені на рис. 2.1,а, б. Усередині клітинок вказані номери наборів.
Рис. 2.1. Графічний метод мінімізації перемикальних функцій:
а – діаграми Вейча; б – карти Карно
Графічні методи призначені для ручної мінімізації. Наочність цих методів зберігається за невеликої кількості аргументів. При цьому відшукання імплікант не формалізоване, і успіх мінімізації цілком визначається кваліфікацією оператора.
Кожна
клітинка відповідає конституенті.
Прямокутник, що містить
клітинок (
),
відповідає імпліканті. Прямокутник
максимального розміру відповідає
простій імпліканті.
Обґрунтуванням графічного методу мінімізації є той факт, що розташовані поруч клітинки відповідають сусіднім наборам аргументів, що відрізняються значенням однієї змінної і, таким чином. Можуть бути склеєні за методом Квайна. За змінних кожна клітинка має сусідніх клітинок.
Чим більше клітинок містить прямокутник, тим менше букв входить у записі імпліканти. Імпліканта містить тільки ті змінні, котрі приймають однакові значення для всіх клітинок прямокутника.
Наведемо етапи мінімізації перемикальних функцій графічним методом.
1. Заповнити діаграму Вейча або карту Карно. Значення функцій записують у клітинки, що відповідають номерам наборів.
2.Виконати об’єднання одиниць в прямокутники з максимально можливою кількістю клітинок (число клітинок, що можуть поєднуватися, має дорівнювати ). При цьому кожна одиниця повинна входити як мінімум в один прямокутник. Прямокутник може містити й одну клітинку.
3. Визначити МДНФ. Сукупності простих імплікант, що входять у МДНФ, відповідає мінімальна множина прямокутників, що покривають усі одиниці.
Слід
зазначити, що не обов’язково
позначати всі можливі прямокутники в
діаграмі Вейча. Достатньо тільки покрити
всі одиниці хоча б один раз. Наприклад,
у розглянутому прикладі в таблиці для
функції
можна ще виділити прямокутник, що
відповідає імпліканті
,
але ця імпліканта є зайвою, бо всі одиниці
зазначеного прямокутника вже належать
іншим прямокутникам.
Сусідні клітинки можуть бути розташовані у протилежних рядках (колонках) таблиці (див. наступний приклад).
Приклад. Виконати мінімізацію перемикальної функції трьох аргументів, заданою таблицею істинності, за допомогою діаграм Вейча.
Таблиця 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 |
Рис. 2. 2. Діаграма Вейча
Заповнимо діаграму Вейча і знайдемо мінімальну кількість прямокутників максимального розміру, що покривають усі одиниці
(рис. 2. 2).
У результаті отримаємо МДНФ заданої функції:
.
Сусідні клітинки можуть бути розташовані у протилежних рядках (стовпцях) таблиці.