Задача мінімізації логічних функцій

Якщо в склад проектованої схеми повинні входити елементи І, АБО, НЕ, то представлення функцій у довільній із розглянутих канонічних форм уже дає можливість побудови такої схеми. Легко підрахувати, яка кількість і яких елементів буде потрібно для реалізації конкретної логічної функції. На розглянутому вище прикладі очевидно, що використання ДДНФ дасть більш просту реалізацію.

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

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

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

Вирази ДДНФ із вищенаведеного приклада спрощуються в такий спосіб:

.

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

X₂ X₂ X₃

0 1 00 01 11 10

X₁ X₁

0 0 1 0 0 1 3 2

1 2 3 1 4 5 7 6

Рис. 2. Карти Карно для двох і трьох змінних

X₃ X₄

X₁ X₂ 00 01 11 10

00 0 1 3 2

01 4 5 7 6

11 12 13 15 14

10 8 9 11 10 Рис. 3. Карта Карно для чотирьох змінних

X₃ X₄ X₅

X₁ X₂ 000 001 011 010 110 111 101 100

00 0 1 3 2 6 7 5 4

01 8 9 11 10 14 15 13 12

11 24 25 27 26 30 31 29 28

10 16 17 19 18 22 23 21 20

Рис. 4 Карта Карно для п'ятьох змінних

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

Якщо в двох сусідніх клітинах заповненої матриці Карно знаходяться однакові символи (0 або 1), то відповідні цим клітинам вирази можна склеювати, що рівнозначно усуненню змінної, яка у рамках групи, що склеюється, змінює значення. Сусідні клітини, що утворюють пари, об'єднуються замкненою лінією для позначення можливості склеювання. Можливі варіанти склеювання для функцій чотирьох змінних наведені на рис. 5.

Розглянемо приклад. Нехай із таблиці істинності отримана ДДНФ, і вона мінімізується аналітичним методом за допомогою склеювання

Матриця Карно для даного випадку буде мати вигляд, показаний на рис. 3.6.

Рис. 5. Варіанти склеювання для функції чотирьох змінних

00 01 11 10

00

1 0 0 1

01 0 0 0 0

11 0 0 0 0

1 0 0 1

10

Рис. 6. Матриця Карно для приклада

Методика мінімізації логічних функцій за допомогою карт Карно використовується при автоматизованому проектуванні вузлів сучасних ЕОМ і розробці логічних моделей об'єктів і процесів гірничо-металургійного виробництва.