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

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

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

кон'юнктивна нормальна форма (КНФ) - кон'юнкція декількох диз'юнкцій, наприклад, $ \\ 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.

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

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

Нормальні форми логічних функцій Подання булевої функції в формі диз'юнкції кон'юнктивні термів констітуєнт одиниці 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

			f (x 1, x 2, x 3)

На підставі формули (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).

									x 2 x 3

а б

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

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

а б

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

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

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

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

Інші схожі роботи, які можуть вас заінтересовать.вшм\u003e
9020.		Принципом двоїстості. РОЗКЛАДАННЯ булевих функцій за змінними. ДОСКОНАЛІ диз'юнктивного І кон'юнктивна нормальна форма	96.34 KB
	Дана теорема носить конструктивний характер, так як вона дозволяє для кожної функції побудувати реалізовує її формулу у вигляді досконалої д. Н. ф. Для цього в таблиці істинності для кожної для функції відзначаємо всі рядки, в яких
6490.		Опис і мінімізація логічних функцій	187.21 KB
	У словесній формі виражається взаємозв'язок між аргументами функції і її значеннями. Приклад: функція трьох аргументів приймає значення коли будь-які два або більше аргументів функції рівні. Складається в побудові таблиці істинності містить значення функції для всіх наборів значень аргументів. В даному прикладі по таблиці істинності отримуємо такий запис у вигляді ДНФ ...
6707.		Проектування реляційних баз даних. Проблеми проектування в класичному підході. Принципи нормалізації, нормальні форми	70.48 KB
	Що таке проект реляційної бази даних Це набір взаємозв'язаних відносин в яких визначені всі атрибути задані первинні ключі відносин і задані ще деякі додаткові властивості відносин які відносяться до принципів підтримки цілісності. Тому проект бази даних повинен бути дуже точний і вивірений. Фактично проект бази даних це фундамент майбутнього програмного комплексу який буде використовуватися досить довго і багатьма користувачами.
4849.		Форми і методи здійснення функцій держави	197.3 KB
	Термін «функція» має у вітчизняній і зарубіжній науковій літературі далеко не однакове значення. У філософському і общесоциологическом плані, він розглядається, як «зовнішній прояв властивостей якого-небудь об'єкта в даній системі відносин»; як сукупність звичайних або ж специфічних дій окремих осіб або органів
17873.		Формування логічних УУД в учнів 3 класу	846.71 KB
	Психолого-педагогічні аспекти проблеми формування логічних універсальних дій у молодших школярів Методики оцінки сформованості логічних УУД. Розробка концепції розвитку універсальних навчальних дій в системі загальної освіти відповідає новим соціальним запитам. Найважливішим завданням сучасної системи освіти є формування універсальних навчальних дій УУД. Сформованість універсальних навчальних дій є запорукою профілактики шкільних труднощів.
2638.		Технічна реалізація логічних зв'язків в системах автоблокування	1.04 MB
	Технічна реалізація логічних зв'язків в системах автоблокування Технічна реалізація алгоритмів управління тризначною і чотиризначною АБ може бути досягнута за допомогою релейних контактних і безконтактних дискретних та інтегральних логічних елементів ...
10203.		ЗАСТОСУВАННЯ КОНЦЕПЦІЇ РИЗИК орієнтованого ПІДХОДУ ДЛЯ ПОБУДОВИ СТРУКТУРНО-ЛОГІЧНИХ МОДЕЛЕЙ ВИНИКНЕННЯ І РОЗВИТКУ НС	70.8 KB
	Загальний аналіз ризику Виробниче середовище насичується потужними технологічними системами і технологіями які роблять працю людини продуктивним і менш важким фізично однак більш небезпечним. Для ризику характерні несподіванка і раптовість настання небезпечної ситуації. Щодня ми стикаємося з численними ризиками але більша частина з них залишається потенційними т. Теорія ризику передбачає кількісну оцінку негативного впливу на людину а також нанесення шкоди його здоров'ю і життю.
11576.		Поняття, види і форми угод. Наслідки недотримання необхідної форми угод	49.82 KB
	Визнання угоди недійсною види недійсною угоди. Прикладна цінність курсової роботи полягає в спрощенні поняття угоди тобто публічного його подання до більш доступній формі.
6213.		наближення функцій	3.08 MB
	Перша полягає в заміні деякої функції заданий аналітично або таблично інший функцією близькою до вихідної але більш простий і зручною для обчислень. Наприклад заміна функції многочленом дозволяє отримувати прості формули чисельного інтегрування і диференціювання; заміна таблиці наближає функцією дозволяє отримувати значення в її проміжних точках. Виникає також і друге завдання відновлення функції на деякому відрізку по заданих на цьому відрізку значень функції в дискретній множині точок. Відповідь на таке питання ...
14058.		Еволюція функцій держави	29.99 KB
	Російська держава як правове явище перш за все повинно забезпечувати реалізацію призначення держави а також його основних конституційних характеристик як демократичного федеративного правової соціальної світської держави з республіканською формою правління. Головне призначення держави визначається ст.

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

проста диз'юнкція

• повна, Якщо в неї кожна змінна (або її заперечення) входить рівно один раз;
• монотонна, Якщо вона не містить заперечень змінних.

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

Приклад КНФ: $ F (x, y) \u003d (x \\ lor y) \\ land (y \\ lor \\ neg (z)) $

СКНФ

Досконала кон'юнктивна нормальна форма, СКНФ (Англ. Perfect conjunctive normal form, PCNF) - це така КНФ, яка задовольняє умовам:

• в ній немає однакових простих диз'юнкцій
• кожна проста диз'юнкція повна

Приклад СКНФ: $ F (x, y, z) \u003d (x \\ lor \\ neg (y) \\ lor z) \\ land (x \\ lor y \\ lor \\ neg (z)) $

теорема: Для будь-якої булевої функції $ f (\\ vec (x)) $, не рівної тотожною одиниці, існує СКНФ, її задає.

Доведення: Оскільки інверсія функції $ \\ neg (f) (\\ vec x) $ дорівнює одиниці на тих наборах, на яких $ f (\\ vec x) $ дорівнює нулю, то СДНФ для $ \\ neg (f) (\\ vec x) $ можна записати в такий спосіб:

$ \\ Neg (f) (\\ vec x) \u003d \\ bigvee \\ limits_ (f (x ^ (\\ sigma_ (1)), x ^ (\\ sigma_ (2)), ..., x ^ (\\ sigma_ (n ))) \u003d 0) (x_ (1) ^ (\\ sigma_ (1)) \\ wedge x_ (2) ^ (\\ sigma_ (2)) \\ wedge ... \\ wedge x_ (n) ^ (\\ sigma_ (n ))) $, де $ \\ sigma_ (i) $ позначає наявність або відсутність заперечення при $ x_ (i) $

Знайдемо інверсію лівої і правої частини виразу:

$ F (\\ vec x) \u003d \\ neg ((\\ bigvee \\ limits_ (f (x ^ (\\ sigma_ (1)), x ^ (\\ sigma_ (2)), ..., x ^ (\\ sigma_ (n ))) \u003d 0) (x_ (1) ^ (\\ sigma_ (1)) \\ wedge x_ (2) ^ (\\ sigma_ (2)) \\ wedge ... \\ wedge x_ (n) ^ (\\ sigma_ (n ))))) $

Застосовуючи двічі до отриманого в правій частині виразу правило де Моргана, отримуємо: $ f (\\ vec x) \u003d \\ bigwedge \\ limits_ (f (x ^ (\\ sigma_1), x ^ (\\ sigma_2), \\ dots, x ^ (\\ Останній вираз і є СКНФ. Так як СКНФ отримана з СДНФ, яка може бути побудована для будь-якої функції, не рівної тотожному нулю, то теорема доведена.

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

У таблиці істинності відзначаємо ті набори змінних, на яких значення функції дорівнює $ 0 $.

• Для кожного зазначеного набору записуємо диз'юнкцію всіх змінних за таким правилом: якщо значення деякої змінної є $ 0 $, то в диз'юнкцію включаємо саму змінну, інакше її заперечення.
• Всі отримані диз'юнкції пов'язуємо операціями кон'юнкції.
• Приклад побудови СКНФ для медіани

1). У таблиці істинності відзначаємо ті набори змінних, на яких значення функції дорівнює $ 0 $.

z

x	y	$ \\ Langle x, y, z \\ rangle $
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

2). Для кожного зазначеного набору записуємо кон'юнкцію всіх змінних за таким правилом: якщо значення деякої змінної є $ 0 $, то в диз'юнкцію включаємо саму змінну, інакше її заперечення.

x	y	$ \\ Langle x, y, z \\ rangle $
0	0	0	0	$ (X \\ lor y \\ lor z) $
0	0	1	0	$ (X \\ lor y \\ lor \\ neg (z)) $
0	1	0	0	$ (X \\ lor \\ neg (y) \\ lor z) $
0	1	1	1
1	0	0	0	$ (\\ Neg (x) \\ lor y \\ lor z) $
1	0	1	1
1	1	0	1
1	1	1	1

3). Всі отримані диз'юнкції пов'язуємо операціями кон'юнкції.

$ \\ Langle x, y, z \\ rangle \u003d (x \\ lor y \\ lor z) \\ land (\\ neg (x) \\ lor y \\ lor z) \\ land (x \\ lor \\ neg (y) \\ lor z) \\ land (x \\ lor y \\ lor \\ neg (z)) $

Приклади СКНФ для деяких функцій

Стрілка Пірса: $ x \\ downarrow y \u003d (\\ neg (x) \\ lor (y)) \\ land ((x) \\ lor \\ neg (y)) \\ land (\\ neg (x) \\ lor \\ neg (y) ) $

Що виключає або: $ x \\ oplus y \\ oplus z \u003d (\\ neg (x) \\ lor \\ neg (y) \\ lor z) \\ land (\\ neg (x) \\ lor y \\ lor \\ neg (z)) \\ land (x \\ lor \\ neg (y) \\ lor \\ neg (z)) \\ land (x \\ lor y \\ lor z) $

Стандартний базис. Елементарні формули - літерали. Елементарна кон'юнкція (диз'юнкція). Диз'юнктивна (Кон'юнктивна) нормальна форма і досконала форма. Теорема: будь-яка булева функція, відмінна від 0 (від 1) представимо у вигляді СДНФ (СКНФ). Повнота стандартного базису. Приклади повних базисів: базис Жегалкина, штрих Шеффера, стрілка Пірса.

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

Тут ми будемо називати літералом змінну x або її заперечення x і позначати x. Булево перетин кількох литералов, що визначаються різними змінними, тобто вираз виду X \u003d x 1 x 2. . . x л, називається елементарної кон'юнкція . Вимога, щоб всі змінні були різні обумовлюється наступним. Якщо в кон'юнкцію входить кілька однакових літералів, то в силу коммутативности, асоціативності і ідемпотентності кон'юнкції можна, переходячи до еквівалентної формулою, залишити лише один літерал (наприклад, x 1 x 1 \u003d x 1). Якщо в кон'юнкцію входить змінна і її заперечення, то формула еквівалентна константі 0, оскільки x x \u003d 0 і для будь-якої формули Y маємо Y x x \u003d 0.

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

x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5.

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

x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4

є досконала форма.

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

Теорема 1.4. Будь-яка булева функція, відмінна від константи 0 подана в вигляді СДНФ.

◀ Домовимося під x σ розуміти формулу x, якщо σ \u003d 1, і формулу x, якщо σ \u003d 0. Нехай функція f (y 1,..., Yn) приймає значення 1 на векторі (t 1,..., Tn ) (такий вектор називають констітуенти одиниці ). Тоді елементарна кон'юнкція також приймає значення 1 на цьому наборі, але звертається в нуль на всіх інших n-мірних бульових векторах. Розглянемо формулу

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

Неважко помітити, що формула Φ звертається в 1 при тих, і тільки при тих значеннях змінних, при яких звертається в 1 розглянута функція. Значить, формула Ψ представляє функцію f.

Слідство 1.1. Стандартний базис є повним.

◀ Дійсно, якщо функція не є константою 0, то вона подана або у вигляді СДНФ, яка є формулою над стандартним базисом. Константу 0 можна уявити, наприклад, формулою f (x 1, x 2,..., X n) \u003d x 1 x 1.

Приклад 1.2. Розглянемо функцію трьох змінних m (x 1, x 2, x 3) (табл. 1.4), яка називається мажоритарною опцією ̆. Ця функція приймає значення 1, якщо більше половини її аргументів мають значення 1. Тому її часто називають функцією голосування. Побудуємо для неї СДНФ.

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

Приклад 1.3. Безліч з операцій додавання по модулю 2, множення і константи 1 називають базисом Жегалкина . Додавання за модулем 2 і множення - базові операції кільця Z2, вирази, складені з їх допомогою - це многочлени над кільцем Z2. Кон- Стант 1 в даному випадку необхідна для запису вільного члена. Оскільки xx \u003d x, то все співмножники в многочлене мають ступінь 1. Тому при записі многочлена можна обійтися без поняття ступеня. Приклади формул над базисом Жегалкина:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

Будь-яку таку формулу називають поліномом Жегалкина. Фактично поліном Жегалкина - це многочлен над кільцем Z2.

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

x + y \u003d x⊕y⊕xy, x \u003d x⊕1.

Тому базис Жегалкина - повне безліч.
Можна показати, що для будь-якої булевої функції поліном Жегалкина визначено однозначно

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

Приклад 1.4. Розглянемо безліч з єдиною функції - штриха Шеффера *. Це безліч повно, що випливає з наступних легко перевіряються тотожностей:

x \u003d x | x, xy \u003d x | y \u003d (x | y) | (x | y), x + y \u003d x | y \u003d (x | x) | (y | y).

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

* Штрих Шеффера - бінарна, але не асоціативність. Тому при використанні інфіксной форми слід бути уважним: результат залежить від порядку виконання операцій. В цьому випадку рекомендується явно вказувати порядок операцій за допомогою дужок, наприклад писати (x | y) | z, а не x | y | z, хоча обидві форми рівнозначні.

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

енциклопедичний YouTube

• 1 / 5

  формули в КНФ:

  ¬ A ∧ (B ∨ C), (\\ displaystyle \\ neg A \\ wedge (B \\ vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E), (\\ displaystyle (A \\ vee B) \\ wedge (\\ neg B \\ vee C \\ vee \\ neg D) \\ wedge ( D \\ vee \\ neg E),) A ∧ B. (\\ Displaystyle A \\ wedge B.)

  формули не в КНФ:

  ¬ (B ∨ C), (\\ displaystyle \\ neg (B \\ vee C),) (A ∧ B) ∨ C, (\\ displaystyle (A \\ wedge B) \\ vee C,) A ∧ (B ∨ (D ∧ E)). (\\ Displaystyle A \\ wedge (B \\ vee (D \\ wedge E)).)

  Але ці 3 формули не в КНФ еквівалентні такими формулами в КНФ:

  ¬ B ∧ ¬ C, (\\ displaystyle \\ neg B \\ wedge \\ neg C,) (A ∨ C) ∧ (B ∨ C), (\\ displaystyle (A \\ vee C) \\ wedge (B \\ vee C),) A ∧ (B ∨ D) ∧ (B ∨ E). (\\ Displaystyle A \\ wedge (B \\ vee D) \\ wedge (B \\ vee E).)

  побудова КНФ

  Алгоритм побудови КНФ

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

  A → B \u003d ¬ A ∨ B, (\\ displaystyle A \\ rightarrow B \u003d \\ neg A \\ vee B,) A ↔ B \u003d (¬ A ∨ B) ∧ (A ∨ ¬ B). (\\ Displaystyle A \\ leftrightarrow B \u003d (\\ neg A \\ vee B) \\ wedge (A \\ vee \\ neg B).)

  2) Замінити знак заперечення, що відноситься до всього висловом, знаками заперечення, що відносяться до окремих змінним висловлювань на підставі формул:

  ¬ (A ∨ B) \u003d ¬ A ∧ ¬ B, (\\ displaystyle \\ neg (A \\ vee B) \u003d \\ neg A \\ wedge \\ neg B,) ¬ (A ∧ B) \u003d ¬ A ∨ ¬ B. (\\ Displaystyle \\ neg (A \\ wedge B) \u003d \\ neg A \\ vee \\ neg B.)

  3) Позбутися від знаків подвійного заперечення.

  4) Застосувати, якщо потрібно, до операцій кон'юнкції і диз'юнкції властивості дистрибутивности і формули поглинання.

  Приклад побудови КНФ

  Наведемо до КНФ формулу

  F \u003d (X → Y) ∧ ((¬ Y → Z) → ¬ X). (\\ Displaystyle F \u003d (X \\ rightarrow Y) \\ wedge ((\\ neg Y \\ rightarrow Z) \\ rightarrow \\ neg X).)

  перетворимо формулу F (\\ displaystyle F) до формули, яка не містить → (\\ displaystyle \\ rightarrow):

  F \u003d (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) \u003d (¬ X ∨ Y) ∧ (¬ (¬ ¬ Y ∨ Z) \u200b\u200b∨ ¬ X). (\\ Displaystyle F \u003d (\\ neg X \\ vee Y) \\ wedge (\\ neg (\\ neg Y \\ rightarrow Z) \\ vee \\ neg X) \u003d (\\ neg X \\ vee Y) \\ wedge (\\ neg (\\ neg \\ В отриманій формулі перенесемо заперечення до змінних і скоротимо подвійні заперечення:

  F \u003d (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X). (\\ Displaystyle F \u003d (\\ neg X \\ vee Y) \\ wedge ((\\ neg Y \\ wedge \\ neg Z) \\ vee \\ neg X).)

  Наприклад, наступна формула записана в 2-КНФ:

  (A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C). (\\ Displaystyle (A \\ lor B) \\ land (\\ neg B \\ lor C) \\ land (B \\ lor \\ neg C).)

  Популярне