1. Складання логічних виразів по таблиці істинності
2. Мінімізація за допомогою карт Карно

Анотація: Розглядається взаємозв'язок різних способів опису роботи логічних схем і принципи їх мінімізації.

Складання логічних виразів по таблиці істинності

Канонічна сума минтермов

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

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

1. У заданої таблиці істинності підраховується - кількість рядків таблиці, в якій значення функції дорівнює 1.
2. Потім записується логічна сума повних творів.
3. Далі в кожному творі розставляються інверсії над змінними відповідно до їх значенням в рядку таблиці.

Для прикладу, представленого на Мал. 1.6 , Канонічна сума минтермов буде виглядати так:

З порівняння (1.1) і (2.1) видно, що однією і тією ж таблиці істинності ( Мал. 1.6 , Б) відповідають два різних логічних вирази, причому (1.1) записується більш компактно, але можливості мінімізації для нього ще є. Отже, є можливість мінімізувати і логічну схему, представлену на Мал. 1.6, a .

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

Мінімізація за допомогою карт Карно

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

Призначення карти Карно - знайти логічні суми прямого і інверсного значення змінних. Для будь-якої змінної, наприклад, , Така сума дорівнює при будь-якому значенні : при це буде , при це . Тому при винесенні за дужки у виразі:

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

1. Вертикальна вісь розмічається незалежно від горизонтальної.
2. Починати розмітку можна з будь-якого поєднання змінних.
3. Всі поєднання змінних повинні бути перераховані.
4. Для сусідніх клітин карти поєднання змінних має відрізнятися не більше ніж одним знаком, причому сусідніми є крайні клітини рядка (стовпчика).

Для функції двох змінних карта Карно - це квадрат 2x2 клітини. У цих клітинах розміщуються 4 значення функції з останнього стовпця таблиці істинності ( Мал. 2.2 ).

Мал.2.2.

Таблиця істинності (а) і карта Карно (б) для функції 2 змінних.

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

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

Для функції п'яти змінних карта Карно являє собою вже об'ємну фігуру - куб 4x4x4 клітини, тому для мінімізації логічних виразів вона не застосовується.

Таблиця істинності (а) і приклади заповнення карти Карно (б, в, г, д) для логічної функції 3 змінних.
збільшити зображення
Мал. 2.4. Таблиця істинності (а) і приклади заповнення карти Карно (б, в) для логічної функції 4 змінних.

У конкретних випадках замість значень функцій в загальному вигляді в клітини карти проставляються конкретні значення (логічні 0 і 1) з відповідних рядків таблиці істинності. Потім розглядаються тільки ті клітини, які заповнені одиницями. Всі ці одиниці повинні бути обведені контурами за такими правилами складання контурів:

1. Контури повинні бути прямокутними і містити кількість одиниць, що дорівнює , де - ціле число. Таким чином, в контурі може бути або одна, або дві, або чотири, або вісім одиниць.
2. Кількість одиниць в контурі повинно бути максимальним, при цьому контури можуть перетинатися між собою. Потрібно враховувати, що крайні рядки є сусідніми і крайні стовпчики також є сусідніми, тому контури можуть бути "розірваними".
3. Кількість контурів має бути мінімальним, але все одиниці повинні бути охоплені контурами. Не можна забувати про окремо розташованих одиницях. Кожна така одиниця - це контур, якому відповідав би повне логічне твір всіх змінних.

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

Приклад 1. Написати мінімальне вираження для таблиці істинності, представленої на Мал. 2.5 , А й намалювати по ньому логічну схему.

При одному варіанті розмітки осей ( Мал. 2.5 , Б) перший контур, що складається з чотирьох одиниць, виходить розірваним. Якщо ж прийняти розмітку, показану на Мал. 2.5 , В, то контур матиме нормальні обриси, а вираз, йому відповідне, залишиться без змін. З огляду на, що при даному горизонтальному зображенні карти Карно крайні стовпчики є сусідніми, її можна уявити собі як циліндр, розгорнутий на площині. на Мал. 2.5 , Б представлена ​​розгортка такого циліндра, "розрізана" між комбінаціями , рівними і . А на Мал. 2.5 , В представлена ​​розгортка цього ж циліндра, "розрізана" між творами , рівними і .

Перший контур охоплює чотири одиниці, йому відповідає сума минтермов: , В якій не змінюється тільки змінна . Другий контур охоплює дві одиниці. Йому відповідає сума минтермов , В якій змінна приймає обидва можливих значення, а твір залишається незмінним. Таким чином, отримуємо мінімальну вираз:

Йому відповідає логічна схема на Мал. 2.5 , Г.

Мал.2.5.

Мінімізація функції трьох змінних

Для порівняння запишемо максимальне вираження:

Різниця між (2.2) і (2.3) очевидна і коментарів не потребує, за винятком того, що схема, реалізована по (2.3), буде на порядок складніше і, відповідно, менш надійна, ніж схема, показана на Мал. 2.5 , Г.

Приклад 2. Написати мінімальне вираження для таблиці істинності, представленої на Мал. 2.6 , А, і намалювати по ньому логічну схему.

Мінімізація функції чотирьох змінних

При спочатку обраної розмітці осей ( Мал. 2.6 , Б) перший контур, що складається з чотирьох одиниць з номерами 1.1, 1.2, 1.3 і 1.4, розташованих по кутах карти, виходить розірваним. Якщо ж прийняти розмітку, показану на Мал. 2.7 , То контур матиме обриси квадрата, а вираз, йому відповідне, залишиться без змін. З огляду на, що крайні стовпчики є сусідніми і крайні рядки є сусідніми, карту Карно для функції чотирьох змінних можна уявити собі як торроід, розгорнутий на площині. Простіше уявити собі зворотний процес отримання торроіда з плоскої фігури - квадрата. Для цього треба спочатку з'єднати подумки крайні рядки - отримаємо циліндр. Після цього підстави циліндрів треба подумки з'єднати. Вийде торроід. на Мал. 2.6 , Б представлена ​​розгортка такого торроіда, "розрізана" між комбінаціями , рівними і і між поєднаннями , рівними і . А на Мал. 2.7 представлена ​​розгортка цього ж торроіда, "розрізана" між комбінаціями , рівними і і між творами , рівними і . Після аналізу контурів отримаємо мінімальне вираження . Відповідна йому схема приведена на Мал. 2.8 .

До мінімізації логічної функції чотирьох змінних
Мал. 2.8. Логічна схема для минимизированного логічного виразу