Мінімізація логічних функцій.
Досконала диз’юнктивна (або кон’юнктивна) форма хоч і містить в своїй назві слово «досконала», не є такою для її реалізації електронними схемами. Отримані форми ДДНФ (ДКНФ) можуть бути перетворені (не завжди) до виду, що містить менше число змінних і операцій в порівнянні з початковим. Таке перетворення називається мінімізацією.
Перетворення функції можна розділити на два етапи:
- на першому етапі здійснюється перехід від канонічної форми (ДДНФ або ДКНФ) до так званої скороченої форми;
- на другому етапі – перехід від скороченої форми до мінімальної форми.
На першому етапі, застосовуючи основні закони алгебри логіки, можна було б аналітично зменшити складність отриманого виразу ДДНФ.
Уявімо, що задана функція F представлена в ДДНФ. Для здійснення спрощення виконуються дві дії:
1. Операція склеювання;
2. Операція поглинання.
Операція склеювання зводиться до знаходження пар членів, відповідних виду wÙx або 
, і перетворенню їх в наступні вирази:
Результати склеювання w тепер грають роль додаткових членів.
Потім виконується операція поглинання. Вона заснована на рівності
(член w поглинає вираз wÙz). Унаслідок цієї дії з логічного виразу викреслюються всі члени, що поглинаються іншими змінними, результати яких отримані в операції склеювання. Обидві операції можуть виконаються до тих пір, поки це може бути здійснено.
Приклад: Логічна функція F(x1, x2, x3) задана наведеною таблицею істинності.
| x1 | x2 | x3 | F(x1, x2, x3) |
ДДНФ для цієї функції виглядатиме так:
Використовуючи властивість ідемпотентності до четвертого доданка, можна дописати ще один шостий член:
Склеюючи перший і четвертий члени, другий і третій та п’ятий і шостий отримаємо:
В отриманому виразі склеюючи другий і третій члени, будемо мати:
Подальше проведення операцій склеювання і поглинання виявляється неможливим. Таким чином отримана скорочена форма вираження заданої функції (в даному випадку вона збігається з мінімальною формою), яка значно простіша її початкової версії. Структурна схема реалізації отриманої функції матиме вид, представлений на рисунку.
Компактною і дуже зручною формою запису логічної функції, що використовується поряд з таблицею істинності, є карта Карно[25]. Карта Карно є спеціальною компактною формою таблиці істинності, яка дозволяє не лише представити функцію, але і подати її в скороченому виді. Кількість кліток в карті Карно дорівнює кількості рядків в таблиці істинності. Кожна клітка відповідає одному рядку таблиці. Комбінації вхідних змінних розподіляються по двох сторонах прямокутника, а відповідні значення функції в клітках таблиці, що знаходяться на перетині рядків, і стовпчиків, відповідних вибраним станам змінних. Розподіл комбінацій вхідних змінних по сторонах повинен бути таким, щоб різниця в двох сусідніх рядках або стовпчиках була не більше ніж в одному розряді.
Якщо потрібно отримати карту Карно для деякої функції, спочатку треба записати цю функцію в ДДНФ або у вигляді звичайної таблиці істинності. Кожен доданок логічного виразу в ДДНФ, або кожна одиниця в стовпчику функції вихідної таблиці істинності, задається на карті Карно одиницею у відповідній клітці. Координати цієї клітки містять ті ж вхідні змінні і їх інверсії, що і даний доданок ДДНФ логічного виразу (або даний рядок вихідної таблиці істинності).
Карти Карно можуть застосовуватися для функцій навіть від 8–12 змінних. Нижче наводяться карти Карно для кількості змінних 2, 3, 4, …, 6.
Метод Карно заснований на законі склеювання. Склеюються набори, що відрізняються один від одного лише значенням одного розряду. Такі набори називаються сусідніми, і вони відповідають сусіднім кліткам карти Карно. Зауважимо, що в картах Карно верхній рядок є сусіднім з нижнім, а правий стовпчик сусідній з лівим.
Якщо в карті Карно зустрічаються групи з 2-х, 4-х, 8-ми і т.д. сусідніх кліток, що містять одиниці, і які можна виділити контуром у вигляді квадрата або прямокутника[26], то така група може бути описана одним логічним добутком. Клітки можуть одночасно входити до складу кількох груп. У цей добуток входять лише змінні даної групи, значення яких для всіх вічок групи залишаються незмінними.
Виокремлені логічні добутки (кон’юнкції) об’єднуються через диз’юнкцію. В результаті скорочена функція є логічною сумою логічних добутків, відповідних окремим групам
Якщо потрібна КНФ, то розглядаються ті клітки які містять нулі.
Як приклад скорочення за допомогою карти Карно побудуємо скорочені ДНФ для логічних функцій, що визначають вихідні сигнали у вже розглянутому однорозрядному суматорі. Скористуємось готовою таблицею істинності. Заповнимо клітки карти Карно для трьох змінних Аі, Ві, Рі–1 для функції, що визначає суму Si (рис. а) і клітки такої ж карти для функції, що визначає перенос в старший розряд Рi (рис. б).
а) б)
На карті Карно для логічної функції, що визначає суму Si неможливо виокремити прямокутники Карно, а отже, спростити наведену вище канонічну ДДНФ неможливо, вона такою ж і залишається:
На Карті Карно для логічної функції, що визначає перенос в старший розряд Рi, виокремлено три прямокутника, кожний із двох кліток. В кон’юнкції, що відповідають прямокутникам входять тільки змінні, які в межах прямокутника не змінюють свого значення. Отже, отримуємо скорочену ДНФ, рівну отриманій вище канонічній ДДНФ:
На другому етапі здійснюється перехід від скороченої форми до мінімальної форми. Як і на першому етапі, в отриманих логічних виразах можуть міститися члени, усунення яких жодним чином не вплине на кінцевий результат. Отже, наступний етап мінімізації – вилучення таких змінних. Кінцевий вираз досягається за рахунок повторного використання операцій склеювання і поглинання.
Для отриманих на першому етапі скорочених форм ДНФ у прикладі розглянутого двійкового суматора ці операції здійснити не вдасться, що свідчить про те, що отримані скорочені форми і є мінімальними.
На основі отриманих виразів можна скласти схему пристрою, що реалізовує задані функції. Структурна схема реалізації зазначених функцій наводиться на рисунку.
Завдання для розрахунково-графічної роботи № 3
Завдання № 1. Побудувати таблиці істинності для логічних виразів:
- 
;
- 
;
- 
;
- 
.
Завдання № 2. Для заданої таблиці істинності побудувати відповідний логічний вираз.
| X | Y | F |
Завдання № 3. Маємо три прості логічні змінні: А, В і С. Записати логічний вираз, що відповідає заданій таблиці істинності, і спростити його.
| А | В | С | F |
Завдання № 4. Який з пропонованих виразів еквівалентний формулі:
?
1. АÙВ
2. А
3. АÚВ
4. ВÙ(АÚВ)
Завдання № 5. На обидва входи логічної схеми подається один і той же сигнал А, який може приймати значення «1» або «0».
Яке значення буде на виході F схеми?
Завдання № 6. Задана логічна схема.
При яких значеннях X і Y на вході схеми на її виході F буде «1» (істина)?
Завдання № 7. На один вхід логічної схеми «І» подається сигнал А, який може приймати значення «1» або «0», а на інший його заперечення (його інвертоване значення).
Яке значення буде на виході схеми?
Завдання № 8. Записати формулу, що відображує логічне перетворення, яке виконується поданою схемою.
Завдання № 9. За заданими таблицями істинності побудувати схеми логічних пристроїв.
1.
| A | B | C | F(A,B,C) |
2.
| A | B | C | F(A,B,C) |
3.
| A | B | C | F(A,B,C) |
Завдання № 10. Синтезувати логічні схеми, що реалізують наступні логічні функції:
