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

Задана конкретна таблиця істинності для функції, яка залежить від трьох аргументів:

Якщо виписати відповідні кон’юнкти напроти одиничних значень , ми отримаємо ДДНФ:

.

Якщо ми випишемо диз’юнкти напроти нульових значень , то в результаті отримаємо вже ДКНФ:

.

Нарешті, ДПНФ утворюється шляхом заміни в ДДНФ на +, на

.

Взаємно скоротив усі однакові доданки, які входять до формули парне число разів, отримаємо:

.

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

У логіці Буля діють закони склеювання:

.

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

З попереднього приклада приведемо відповідні форми представлення функції . Отже, маємо

та для ДКНФ, тобто мінімальну КНФ:

Змінні та називають термами. Саме повний набір з термів утворює констітуєнту. У процесі ж мінімізації деякі терми з констітуєнт зникнуть. Тоді частину диз’юнкту або кон’юнкту, що залишилася, називаютьімплікантою.

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

 

Метод Куайна. Задані номери наборів чотирьох змінних, на яких логічна функція приймає значення 1:

Представимо цю логічну функцію у ДДНФ (символ кон’юнкції писати не будемо). Цифри десятичної системи счислення переведемо у двоїчну систему:

1 – 1 7 - 111 13 – 1101

2 – 10 8 – 1000 14 - 1110

3 – 11 9 – 1001

4 – 100 10 – 1010

5 – 101 11 – 1011

6 – 110 12 – 1100

Отже, нашу логічну функцію ми можемо записати у ДДНФслідуючим чином:

.

На першому етапі мінімізації початкову ДДНФ можна спростити за рахунок використання закону склеювання. При цьому необхідно пам’ятати, що одну і ту ж констітуєнту (імпліканту) можна склеювати з іншими констітуєнтами (імплікантами) багатократно, тому що в логіці Буля діє закон ідемпотентності:

,

отже, склеюмо першу констітуєнту з третьою, першу з п’ятою, другу з четвертою, другу з сьомою, третю з четвертою, п’яту з восьмою, шосту з сьомою, третю з восьмою, шосту з восьмою:

На другому етапі скористуємося таблицею Куайна, в відповідності з якою даний метод мінімізації отримав свою назву – метод Куайна.

 

Число рядків дорівнює числу отриманих первинних імплікант мінімізуємої функції. Число стовпців співпадає з числом констітуєнт ДДНФ. Якщо в деяку констітуєнту ДДНФ входить будь-яка з імплікант, то на перетині відповідного стовпця та рядку ставиться мітка.

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

Отже, у нас є два стовпця, де стоїть одна мітка (1 та 5). Таким чином, істотною буде імпліканта . Ця імпліканта покриває наступні констітуєнти: ,. Якщо в стовпцях, які відповідають цим констітуєнтам, є ще мітки, то вони виключаються з розгляду. З констітуєнт, що залишилися, імпліканта покриває дві констітуєнти: та . Імпліканта покриває констітуєнти та .

Таким чином, після всіх перетворень ми отримали слідуючу мінімальну функцію:

.