Ноу Інти, лекція, мінімізація логічних схем

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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


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


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

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

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

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

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

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

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