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

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

Наприклад, є простий кон'юнкція,

диз'юнктивній нормальної формою (ДНФ) називається диз'юнкція простих кон'юнкція.

Наприклад, вираз є ДНФ.

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

Наприклад, вираз є ДНФ, але не СДНФ. вираз є СДНФ.

Аналогічні визначення (з заміною кон'юнкції на диз'юнкцію і навпаки) вірні для КНФ і СКНФ. Наведемо точні формулювання.

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

кон'юнктівной нормальної формою (КНФ) називається кон'юнкція простих диз'юнкцій (Наприклад вираз - КНФ).

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

Наприклад, вираз є СКНФ.

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

а) перехід від ДНФ до КНФ

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

Зауважимо, що КНФ можна отримати і з початкового виразу, якщо винести у за дужки;

б) перехід від КНФ до ДНФ

Цей перехід здійснюється простим розкриттям дужок (при цьому знову-таки використовується правило поглинання)

Таким чином, отримали ДНФ.

Зворотний перехід (від СДНФ до ДНФ) пов'язаний з проблемою мінімізації ДНФ. Детальніше про це буде розказано в розд. 5, тут же ми покажемо, як спростити ДНФ (або СДНФ) за правилом Блейка. Така ДНФ називається скороченою ДНФ;

в) скорочення ДНФ (або СДНФ) по правилом Блейка

Застосування цього правила складається з двох частин:

Якщо серед діз'юнктних доданків в ДНФ є складові , То до всієї диз'юнкції додаємо доданок До 1 До 2. Проробляємо цю операцію кілька разів (можна послідовно, можна одночасно) для всіх можливих пар доданків, а потім, застосовуємо звичайне поглинання;

Якщо додається доданок вже містилося в ДНФ, то його можна відкинути зовсім, наприклад,

або

Зрозуміло, скорочена ДНФ не визначається єдиним чином, але всі вони містять однакову кількість літер (наприклад, є ДНФ , Після застосування до неї правила Блейка можна прийти до ДНФ, равносильной даної):

в) перехід від ДНФ до СДНФ

Якщо в якийсь простий кон'юнкції бракує змінної, наприклад, z, Вставляємо в неї вираз, після чого розкриваємо дужки (при цьому повторюються діз'юнктние складові не пишемо). наприклад:

г) перехід від КНФ до СКНФ

Цей перехід здійснюється способом, аналогічним до попереднього: якщо в простій диз'юнкції не вистачає якоїсь змінної (наприклад, z, То додаємо в неї вираз (це не змінює самої диз'юнкції), після чого розкриваємо дужки з використанням розподільного закону):

Таким чином, з КНФ отримана СКНФ.

Зауважимо, що мінімальну або скорочену КНФ зазвичай отримують з відповідною ДНФ.

Нормальні форми логічних функцій Подання булевої функції в формі диз'юнкції кон'юнктивні термів констітуєнт одиниці Ki 2.7 називається диз'юнктивній нормальною формою ДНФ цієї функції. містять в точності по одній все логічні змінні взяті з запереченнями або без них то така форма представлення функції називається досконалою диз'юнктивній нормальною формою СДНФ цієї функції. Як видно при складанні СДНФ функції потрібно скласти диз'юнкцію всіх минтермов при яких функція приймає значення 1.

Якщо ця робота Вам не підійшла внизу сторінки є список схожих робіт. Так само Ви можете скористатися кнопкою пошук

лекція 1.хх

Нормальні форми логічних функцій

Подання булевої функції в формі диз'юнкції кон'юнктивні умов (констітуєнт одиниці)K i

, (2.7)

називається диз'юнктивній нормальною формою (ДНФ) цієї функції.

Якщо все кон'юнктівние терми в ДНФ єминтермов , Т. Е. Містять в точності по одній все логічні змінні, взяті з запереченнями або без них, то така форма представлення функції називаєтьсядосконалої диз'юнктивній нормальною формою (СДНФ ) Цієї функції. СДНФ називаєтьсядосконалої , Тому що кожен терм в диз'юнкції включає всі змінні;диз'юнктивній , Тому що головна операція у формулі диз'юнкція. поняття "нормальної форми"Означає однозначний спосіб запису формули, що реалізує задану функцію.

З урахуванням сказаного вище з теореми 2.1 випливає наступна теорема.

Теорема 2. Будь-яка булева функція(не дорівнює тотожно 0) може бути представлена \u200b\u200bв СДНФ, .

Приклад 3. Нехай маємо таблично задану функціюf (x 1, x 2, x 3) (табл. 10).

Таблиця 10

На підставі формули (2.6) отримуємо:

Як видно, при складанні СДНФ функції потрібно скласти диз'юнкцію всіх минтермов, при яких функція приймає значення 1.

Подання булевої функції в формі кон'юнкції діз'юнктівних умов (констітуєнт нуля)D i

, (2.8)

називається кон'юнктівной нормальною формою (КНФ) цієї функції.

Якщо все диз'юнктивні терми КНФ ємакстермамі , Т. Е. Містять в точності по одній все логічні змінні функції, Взяті з запереченнями або без них, то така КНФ називаєтьсядосконалої кон'юнктівной нормальною формою (СКНФ) цієї функції.

Теорема 3. Будь-яка булева функція(не дорівнює тотожно 1) може бути представлена \u200b\u200bв СКНФ, причому таке уявлення єдино.

Доказ теореми може бути проведено аналогічно доведенню теореми 2.1 на підставі наступної леми Шеннона про кон'юнктивний розкладанні.

Лемма Шеннона . Будь-яка булева функціяf (x 1, x 2, ..., x m) від m змінних може бути представлена \u200b\u200bтак:

. (2.9)

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

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

Приклад 4. Для функції f (x 1, x 2, x 3 ), Заданої табл. 10, написати її СКНФ.

На відміну від СДНФ, при складанні СКНФ в таблиці істинності логічної функції потрібно дивитися комбінації змінних, при яких функція приймає значення 0, і скласти кон'юнкцію відповідних макстермов,але змінні потрібно брати зі зворотним інверсією:

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

Приклад 5. Для функції f (x 1, x 2, x 3 ), Заданої табл. 10, спробувати перейти від СДНФ до СКНФ.

Використовуючи результат прикладу 2.3 отримаємо:

Як видно, під загальною інверсією вийшла СКНФ логічної функції, яка є зворотною по відношенню до функції, отриманої в прикладі 2.4:

т. к. містить всі макстерми, яких немає в вираженні для СКНФ аналізованої функції.

1. Використовуючи властивості операцій (див. Табл. 9) тотожність (), сума по модулю 2 (), імплікація (), переходимо до операцій І, АБО, НЕ (в базис Буля).

2. Використовуючи властивості заперечення і закони де Моргана (див. Табл. 9) добиваємося, щоб операції заперечення ставилися тільки до окремих змінним, а не до цілих виразів.

3. Використовуючи властивості логічних операцій І та АБО (див. Табл. 9), отримуємо нормальну форму (ДНФ або КНФ).

4. При необхідності переходимо до досконалим формам (СДНФ або СКНФ). Наприклад, для отримання СКНФ часто потрібно використовувати властивість:.

Приклад 6. Перетворити в СКНФ логічну функцію

Виконуючи по порядку кроки наведеного вище алгоритму, отримаємо:

Використовуючи властивість поглинання, отримаємо:

Таким чином, ми отримали КНФ функціїf (x 1, x 2, x 3 ). Щоб отримати її СКНФ, потрібно кожну диз'юнкцію, в якій не вистачає будь-якої змінної, повторити двічі з цієї змінної і з її запереченням:

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

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

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

метод Квайна

Мінімізується функція представляється в СДНФ, і до неї застосовуються всі можливі операції неповного склеювання

, (2.10)

а потім поглинання

, (2.11)

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

Зауважимо, що ліву частину рівняння (2.10) відразу можна було мінімізувати більш простим і очевидним способом:

Цей спосіб поганий тим, що при такій безпосередній мінімізації кон'юнктівние терми або зникають, хоча можливі ще випадки їх використання для склеювання і поглинання з рештою термами.

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

Метод карт Карно

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

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

Таблиці істинності і карти Карно для функцій І і АБО двох прове сних представлені на рис. 8. У кожну клітину карти записується зна чення функції на відповідному цій клітці наборі значень аргуменн тов.

А) І б) АБО

Мал. 8. Приклад карт Карно для функцій двох змінних

У карті Карно для функції І тільки одна 1, тому її ні з чим неможливо склеїти. У вираженні для мінімальної функції буде тільки терм, що відповідає цій 1:

f \u003d x y.

У карті Карно для функції АБО вже три 1 і можна скласти дві склеюються пари, при цьому 1, відповідна термуxy , Використовується двічі. У вираженні для мінімальної функції потрібно записати терми для склеюються пар, залишаючи в них всі змінні, які для цієї пари не змінюються, і прибираючи змінні, які змінюють своє значення. Для горизонтальної склейки отримаємоx , А для вертикальноїy , В результаті отримаємо вираз

f \u003d x + y.

На рис. 9 наведені таблиці істинності двох функцій трьох змінних (а ) І їх карти Карно (б і в). Функція f 2 відрізняється від першої тим, що на трьох наборах змінних вона не визначена (в таблиці це позначено прочерком).

При визначенні мінімальної ДНФ функції використовуються наступні правила. Всі клітини, що містять 1, об'єднуються в замкнуті прямокутні області, які називаютьсяk -куб, де k \u003d log 2 K, K кількість 1 в прямокутної області. При цьому кожна область повинна являти собою прямокутник з числом клітин 2k, де k \u003d 0, 1, 2, 3, .... Для k \u003d 1 прямокутник називаєтьсяодин-куб і містить 2 +1 \u003d 2 одиниці; для k \u003d 2 прямокутник містить 22 \u003d 4 одиниці і називаєтьсядва-куб; при k \u003d 3 область з 2 3 \u003d 8 одиниць називаєтьсятри-куб ; і т. д. Одиниці, які неможливо об'єднати в прямокутники, можна назватинуль-кубами , Які містять тільки одну одиницю (20 \u003d 1). Як видно, при парномуk області можуть мати форму квадрата (але не обов'язково), а при непарномуk тільки прямокутників.

Мал. 9. Приклад карт Карно для функцій трьох змінних

Ці області можуть перетинатися, т. Е. Одні й ті ж клітини можуть входити в різні області. Потім записується мінімальна ДНФ функції як диз'юнкція всіх кон'юнктивні термів, відповіднихk - кубів.

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

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

Для функції по карті Карно на рис. 9,б знаходимо

оскільки для верхньої замкнутої області змінніx 1 і x 2 мають значення без інверсій, для нижньоїx 1 має значення з інверсією, аx 3 без інверсії.

Неопредёленние значення в карті на рис. 9,в можна доопределить, замінивши нулем або одиницею. Для даної функції видно, що обидва невизначених значення вигідніше замінити 1. При цьому утворюються дві області, які є різними видами 2-кубів. Тоді вираз для мінімальної ДНФ функції буде наступним:

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

Карти Карно можна малювати різними способами (рис. 10).

а б

Мал. 10. Різні способи зображення карт Карно
для функції 3 змінних

Але найзручнішими варіантами карт Карно для функцій 2-4 змінних є показання на рис. 11 таблиці, т. К. В них для кожного осередку показа ни всі змінні в прямому або інверсному вигляді.

а б

Мал. 11. Найбільш зручний зображення карт Карно
для функцій 3 (а) і 4 (б) змінних

Для функцій 5 і 6 змінних більше підходить спосіб, показаний на рис. 10,в.

Мал. 12. Зображення карти Карно для функції 5 змінних

Мал. 13. Зображення карти Карно для функції 6 змінних

Нормальна форма логічної формули не містить знаків імплікації, еквівалентності і заперечення неелементарних формул.

Нормальна форма існує в двох видах:

кон'юнктивна нормальна форма (КНФ) - кон'юнкція декількох диз'юнкцій, наприклад, $ \\ left (A \\ vee \\ overline (B) \\ vee C \\ right) \\ wedge \\ left (A \\ vee C \\ right) $;

діз'юнктівная нормальна форма (ДНФ) - диз'юнкція кількох кон'юнкція, наприклад, $ \\ left (A \\ wedge \\ overline (B) \\ wedge C \\ right) \\ vee \\ left (B \\ wedge C \\ right) $.

СКНФ

Досконала кон'юнктивна нормальна форма (СКНФ) - це КНФ, яка задовольнить трьом умовам:

не містить однакових елементарних диз'юнкцій;

жодна з диз'юнкцій не містить однакових змінних;

кожна елементарна диз'юнкція містить кожну змінну з вхідних в дану КНФ.

Будь-яка булева формула, яка не є тотожно істинною, може бути представлена \u200b\u200bв СКНФ.

Правила побудови СКНФ по таблиці істинності

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

СДНФ

Досконала діз'юнктівная нормальна форма (СДНФ) - це ДНФ, яка задовольнить трьом умовам:

не містить однакових елементарних кон'юнкція;

жодна з кон'юнкція не містить однакових змінних;

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

Будь-яка булева формула, яка не є тотожно хибною, може бути представлена \u200b\u200bв СДНФ, до того ж єдиним чином.

Правила побудови СДНФ по таблиці істинності

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

Приклади знаходження СКНФ і СДНФ

приклад 1

Записати логічну функцію по її таблиці істинності:

Малюнок 1.

Рішення:

Скористаємося правилом побудови СДНФ:

Малюнок 2.

Отримаємо СДНФ:

Скористаємося правилом побудови СКНФ.

Введемо поняття елементарної диз'юнкції.

Елементарної диз'юнкція називається вираз виду

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

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

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

Використання правила інверсії, якщо операція заперечення застосована до логічного виразу;

Використання аксіоми дистрибутивности щодо множення:

Використання операції поглинання:

Винятки в диз'юнкцій повторюваних змінних або їх заперечень;

Видалення всіх однакових елементарних диз'юнкцій, крім однієї;

Видалення всіх диз'юнкцій, в які одночасно входять змінна і її заперечення.

Справедливість перерахованих операцій випливає з основних аксіом і тотожних співвідношень алгебри логіки.

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

Перетворення КНФ до досконалої КНФ здійснюється шляхом виконання наступних операцій:

Додавання до кожної елементарної диз'юнкції кон'юнкція змінних і їх заперечень, якщо вони не входять в дану елементарну диз'юнкцію;

Використання аксіоми дистрибутивности;

Видалення всіх однакових елементарних диз'юнкцій, крім однієї.

У досконалої КНФ може бути представлена \u200b\u200bбудь-яка логічна функція, крім

тотожно що дорівнює одиниці (). Відмітною властивістю досконалої КНФ є те, що подання до неї логічної функції єдино.

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

Логічна функція константа нуля в досконалої КНФ представляється кон'юнкція 2nконстітуент нуля. Сформулюємо правило складання СКНФ логічної функції за таблицею відповідності.

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

Приклад 3.4.Для логічної функції z (x), заданої таблицею відповідності 2.2, визначимо досконалу кон'юнктівную форму.

Для першого рядка таблиці, яка відповідає нульовому набору функції 000, знаходимо конституенту нуля. Виконавши аналогічні операції для другої, третьої та п'ятої рядків, визначимо шукану досконалу КНФ функції:

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