2.1. Мінімізація логічних функцій.

Алгебра, утворена деякою множиною В разом із усіма можливими операціями над нею, називається алгеброю логіки. Логічною функцією від n змінних називається n-арна операція на В. Логічна функція може приймати значення 0 і 1. Множина всіх логічних функцій позначається, множина всіх логічних функційn-змінних - (n).

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

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

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

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

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

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

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

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