Деякі логічні функції двох змінних

Якщо булева функція не дорівнює тотожно нулю, то її можна представити у вигляді ДДНФ за її таблицею істинності таким чином: обираються тільки ті набори змінних (х ₁, х ₂, …, х_n), для яких f (х ₁, х ₂, …, х_n) = 1, і складається проста кон'юнкція для цього набору (якщо х_i = 0, то беремо в цій кон’юнкції, якщо х_i = 1, то беремо ); отримані елементарні кон’юнкції об'єднуються знаками диз’юнкції.

У випадку, коли булева функція не дорівнює тотожно одиниці, то її можна представити у вигляді ДКНФ за її таблицею істинності таким чином: обираються тільки ті набори змінних (х ₁, х ₂, …, х_n), для яких f (х ₁, х ₂, …, х_n) = 0, і складається проста диз’юнкція для цього набору (якщо х_i = 1, то беремо в цій диз’юнкції, якщо х_i = 0, то беремо .); отримані елементарні диз’юнкції об'єднуються знаками кон’юнкції.

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

Існує два методи мінімізації: метод алгебраїчних перетворень і графічний метод (карти Карно, діаграми Вейча).

Аналітичний (табличний) метод (метод алгебраїчних перетворень) мінімізації складається з таких кроків:

1. Записується перемикальних функція у формі ДДНФ.

2. Виконуються всі операції неповного склеювання послідовно до всіх конституент одиниці, потім до імплікант рангу, , і так далі, поки формування нових імплікант можливе.

3. Виконуються всі можливі поглинання, в результаті чого визначаються всі прості імпліканти, які складають скорочену ДНФ.

4. Будується таблиця покриття (імплікантна матриця) для подальшого спрощення запису функції

5. Виконується завдання покриття всіх значень функції (міні­термів або максітермів) набором простих імплікант (імпліцент) в результаті чого виходить безліч тупикових форм функції.

6. Серед безлічі тупикових форм вибирається одна, яка за певними критеріями визнається мінімальною. Найчастіше це критерій мінімальної кількості змінних (букв) в аналітичному виразі однієї з тупикових форм функції.

Мінімізація з використанням діаграм Вейча (карт Карно) має наступні етапи:

1. Функцію призводять до диз’юнктивної нормальної форми (ДНФ). Для цього її необхідно виразити у вигляді логічної суми простих кон’юнкцій.

2. Після цього заповнюють прямокутну таблицю, в якій число клітин дорівнює N = 2 ⁱ – кількості можливих комбінацій змінних. При числі змінних i = 2 N = 4, при i = 3 N = 8 і т.д. Потім, використовуючи таблицю істинності, у відповідну клітину таблиці ставиться «1», якщо на цьому наборі змінних ЛФ = 1 і 0 - якщо ЛФ = 0 або нічого не ставиться, якщо ЛФ не визначена.

Для булевої функції трьох змінних діаграма Вейча має такий вигляд (рис. 9.1).

3. В заповненій таблиці обводять прямокутними контурами всі «1» і потім записують мінімізовану ЛФ у вигляді суми логічних добутків, що описують ці контури. При проведенні контурів дотримуються наступних правил:

Рис. 9.1. Вигляд діаграми Вейча для трьох змінних

- контури повинні бути прямокутними і охоплювати, в сукупності всі одиниці;

- всередині контуру повинні бути клітини заповнені тільки одиницями;

- число клітин, що знаходяться всередині контуру, має бути цілим ступенем числа 2. Тобто число клітин може дорівнювати 2, 4, 8, 16 і т.д.

- одні й ті ж клітини, заповнені одиницями, можуть входити в декілька контурів.

- при проведенні контурів сама верхня і сама нижня рядка вважаються сусідніми. Теж саме справедливе для крайнього лівого та крайнього правого стовпців;

- число контурів повинно бути якомога меншим, а самі контури якомога більшими.

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

Правила мінімізації з використанням карт Карно

1. У карті Карно групи одиниць (для отримання ДНФ) і групи нулів (для отримання КНФ) необхідно обвести чотирикутними контурами. Усередині контуру повинні знаходитися тільки однойменні значення функції. Цей процес відповідає операції склеювання або знаходження імплікант даної функції (кількість клітин усередині контуру має бути цілим ступенем двійки (1, 2, 4, 8, 16...)).

2. При проведенні контурів крайні рядки карти (верхні і нижні, ліві і праві), а також кутові клітини, вважаються сусідніми (для карт до 4-х змінних).

3. Кожен контур повинен включати максимально можливу кількість клітин. У цьому разі він буде відповідати простій імпліканті.

4. Всі одиниці (нулі) в карті (навіть поодинокі) повинні бути охоплені контурами. Будь-яка одиниця (нуль) може входити в контури довільну кількість разів.

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

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

Увага! Для наведених діаграм характерне наступне: кожній клітині діаграми відповідає свій набір; сусідні набори розташовані поруч у рядку або в стовпчику.