Мінімізація логічних формул
Однозначна залежність складності логічної формули та функціональної схеми логічного устрою призводять до висновку необхідності мінімізації структурної формули логічного устрою. Мінімізація здійснюється з використанням основних співвідношень, законів та теорем алгебри логіки.
Розрахунковий метод мінімізації
Застосування цього методу полягає у послідовному застосуванні до деякої формули законів та правил тотожних перетворень алгебри логіки. При цьому широко використовують такі прийоми: додавання одного або декількох членів, що входять до СДНФ, оскільки X ∨ X ∨ X = X; виділення членів, що містять множник; використання правила склеювання та ін. Отримана в результаті мінімізації алгебраїчна формула називаєтьсятупиковой.Функція може мати кілька тупикових форм.
Приклад: Мінімізувати функцію СДНФ мажоритарного елемента (див. п.2.2) та реалізувати його схему на елементах основного базису.
Склеюючи перші три мінтерми з четвертим, отримуємо ДНФ функції мажоритарного елемента, яка простіше за СДНФ:
Мінімізована функціональна схема мажоритарного елемента наведено малюнку 7.
Малюнок 7 Функціональна схема мажоритарного елемента, реалізована на основі мінімізованої функції ДНФ
Зі порівняння схем, наведених на малюнках 3 і 7 випливає, що в мінімізованій схемі число за Квайном зменшилося з 19 до 9.
Метод мінімізуючих карт Карно
Карти Карно- це графічне уявлення таблиць істинності логічних функцій. Вони містять по 2 n осередків, де n – число логічних змінних. Наприклад, карта Карно для функції трьох змінних містить 2 n = 2 3 = 8 осередків, для чотирьох змінних - 2 4 = 16 осередків.
Карта розмічається системою координат,відповідних значень вхідних змінних. Звернемо особливу увагу на те, що координати стовпців (а також рядків, якщо n>3), слідують не в природному порядку зростання двійкових кодів, а так: 00 01 11 10. Це робиться для того, щоб сусідні набори (у тому числі і стовпців 1 і 4) відрізнялися лише однією цифрою у якомусь розряді.
Процес мінімізації полягає у формуванні правильних прямокутників, що містять по 2 k осередків, де k — ціле число. У прямокутники поєднуються сусідні осередки, які відповідають сусіднім елементарним творам (тобто відрізняються лише в одному розряді).
Незважаючи на те, що карти Карно зображуються на площині, сусідство квадратів встановлюється на поверхні тора. Верхня і нижня межі карти склеюються, утворюючи поверхню циліндра. При склеюванні бічних кордонів виходить поверхню тора.
Приклад: Мінімізувати функцію трьох змінних, задану таблицею істинності (таблиця 6).
Таблиця 6 Таблиця істинності функції трьох змінних