Правило склеювання кліток і запису мінімальної ДНФ

1. Будується карта Карно, що відповідає даній функції.

 

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

 

3. В групу можні об'єднати тільки кількість кліток, що до­рівнює 2 ⁿ ­­_­­­­­­, n— 1, 2, 3,.... При цьому група може мати тільки прямокутну або квадратну форму.

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

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

 

6.Диз'юнкція всіх одержаних простих імплікант зображує результат мінімізації формули і є мінімально ДНФ.

 

 

Оскільки при мінімізації на множині ДНФ у склеюван­ні беруть участь тільки клітки, що містять одиниці, нулі в картах Карно, як правило, не вказують і мають на увазі, що порожні клітки містять нулі.

Приклад. Знайти мінімальну ДНФ функції з попереднього прикладу.

Розв'язок. Опускаючи нулі на рис. 4.3, записуємо вихідну карту Карно у такому вигляді (рис. 4.5).

Графічно склеювання позначається об'єднанням сусідніх одиниць таблиці у групи, результатом чого є дві імпліканти А і В (рис. 4.6).

 

 

 

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

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

37. Метод карт Карно-Вейча для мінімізації булевих функцій, представлених в ДКНФ. Приклади.

 

Мінімізація на множині КНФ

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

 

Розв'язок. Дана функція обертається на нуль на таких наборах:(0,0,0,0,0),(0,0,0,0,1),(0,0,1,0,0),(0,0,1,1,0), (0, 1, 1, 0, 0), (0, 1, 1, 1, 0), (1, 0, 0, 0, 0), (1, 0, 0, 0, 1), (1, 1, 1,0,0), (1, 0, 1, 1, 1). Побудуємо карту Карно для цієї функції (рис. 4.11).

 

 

 

Запишемо мінімальну КНФ, поєднавши знаками кон'юнкції елементарні диз'юнкції:

 

38. Мінімізація неповністю означених булевих функцій. Приклад.

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

Приклад. Функція f(x, у, z, t) дорівнює одиниці на на­борах (0, 0, 1, 0), (0, 1, 1, 0), (1, 0, 1, 0), (1, 0, 0, 0) і не визначена, якщо ху = 1. Необхідно побудувати мінімальну ДНФ.

Розв'язок. Складемо карту Карно для заданої функції (рис. 4.12).

Мінімальна ДНФ

/(х, у, z, t) = A v В - zt v xt.

 

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

 

39. Перетворення ДНФ у КНФ.

Будь-яку ДНФ можна привести до КНФ 3-ма способами:

1) Нехай деяка функція Р має вигляд ДНФ виконує наступне застосування закону подвійного заперечення:далі нижня риска згідно правила Де Моргана опускається на окремі висловлювання. Вираз під рискою приводить до вигляду ДНФ,після чого знову опускається риска на окремі висловлювання. Результат і буде КНФ

2) ДНФ перетворити до вигляду КНФ за дистрибутивною ознакою

А \/ ВС=(А\/В) (А\/С)

3) Нехай деяка формула Р має вигляд ДНФ знаходимо для неї двоїсту формулу р^* та приводить до ДНФ позначають її як а^* після цього знаходимо формулу,що є двоїстою до (а^*)^*=а вона і буде КНФ при чому згідно принципу двоїстості А=Р

 

Приклад. Привести до КНФ функцію,задану в ДНФ:

 

f(x,y,z) = x \/ у\/х

 

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

 

 

Використаємо до цього виразу закон Де Моргана отримаємо:

 

f(x,y,z) =

 

Це і є КНФ яку ми шукали для заданої функції.

 

40. Одержання мінімальних КНФ за допомогою диз'юнктивних форм. Приклад.

Логічні функції, подані у ДНФ, після мінімізації можна перетворити в

КНФ, використовуючи доведені нижче властивості логічних функцій.

Припустимо, що дана логічна функція F = F(х1, х2,..., хn), яка приймає

на наборах j1, j2, …, jm значення одиниці, а на наборах i1, i2, …, ip, де p=2ⁿ-m -

значення нуля. Тоді має місце така теорема.

Теорема 1. Диз'юнкція всіх конституент одиниці Ki1 \/ Ki2 \/ … \/ Kip,

що не входять до ДДНФ логічної функції F, є запереченням цієї функції:

Ki1 \/ Ki2 \/ … \/ Kip=

Теорема 2. КНФ логічної функції Р, одержана з мінімальної ДНФ

функції Р після її перетворення за допомогою формул де Моргана, також

Буде мінімальною.