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

⁰

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

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

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

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

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

СКНФ

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

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

Приклад СКНФ:$f(x,y,z) = (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 ) = \ bigvee \ limits_ ( f ( x ^ ( \ sigma_ ( 1 ) ) , x ^ ( \ sigma_ ( 2 ) ) ) , ... , x ^ ( \ sigma_ ( n ) )) = 0 ) ( x_ ( 1 ) ^ ( \ sigma_ ( 1 ) ) \ wedge x_ ( 2 ) ^ ( \ sigma_ ( 2 ) ) \ wedge ... \ wedge x_ ( n ) ^ ( \ sigma_ ( n ) )) $, де $ \sigma_ ( i ) $ позначає наявність або відсутність заперечення при $ x_ ( i ) $

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

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

Застосовуючи двічі до отриманого у правій частині виразу правило де Моргана, отримуємо: $ f(\vec x) = \bigwedge \limits_ ( f(x^ ( \sigma_1 ) , x^ ( \sigma_2 ) , \dots ,x^ ( \ sigma_n )) = 0 ) $ $(\neg ( x_1^ ( \sigma_1 ) ) \vee \neg ( x_2^ ( \sigma_2 ) ) \vee \dots \vee \neg ( x_n^ ( \sigma_n ) )) $

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

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

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

Приклад побудови СКНФ для медіани

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

x	y	z	$ \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	z	$ \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 = (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 = (\neg (x) \lor(y)) \land ((x) \lor \neg(y)) \land (\neg(x) \lor \neg(y) ) $

Виключне або: $ x \oplus y \oplus z = (\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)$

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

Поділіться роботою у соціальних мережах

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

Лекція 1.хх

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

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

, (2.7)

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

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

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

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

приклад 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) може бути представлена в СКНФ, причому таке уявлення єдине.

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

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

. (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 = x y.

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

f = x + y.

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

При визначенні мінімальної ДНФ функції використовуються такі правила. Усі клітини, що містять 1, об'єднуються у замкнуті прямокутні області, які називаються k-кубами, де k = log 2 K, K кількість 1 у прямокутній ділянці. При цьому кожна область повинна бути прямокутником з числом клітин 2 k , де k = 0, 1, 2, 3, …. Для k = 1 прямокутник називаєтьсяодин-куб і містить 21 = 2 одиниці; для k = 2 прямокутник містить 2 2 = 4 одиниці і називаєтьсядва-куб; при k = 3 область із 2 3 = 8 одиниць називаєтьсятри-куб ; і т. д. Одиниці, які неможливо об'єднати у прямокутники, можна назватинуль-кубами , які містять лише одну одиницю (2 0 = 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 змінних

Інші схожі роботи, які можуть вас зацікавити.
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
	Російська держава як правове явище насамперед має забезпечувати реалізацію призначення держави, а також її основних конституційних характеристик як демократичної федеративної правової соціальної світської держави з республіканською формою правління. Головне призначення держави визначається ст.

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

Енциклопедичний 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 = ¬ A ∨ B , (\displaystyle A\rightarrow B=\neg A\vee B,) A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B) . (\displaystyle A\leftrightarrow B=(\neg A\vee B)\wedge (A\vee \neg B).)
2) Замінити знак заперечення, що стосується всього висловлювання, знаками заперечення, що належать до окремих змінних висловлювань на підставі формул:
¬ (A ∨ B) = ¬ A ∧ ¬ B , (\displaystyle \neg (A\vee B)=\neg A\wedge \neg B,) ¬ (A ∧ B) = ¬ A ∨ ¬ B . (\displaystyle \neg (A\wedge B)=\neg A\vee \neg B.)
3) Позбутися знаків подвійного заперечення.
4) Застосувати, якщо потрібно, до операцій кон'юнкції та диз'юнкції властивості дистрибутивності та формули поглинання.

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

Наведемо до КНФ формулу
F = (X → Y) ∧ ((Y → Z) → X) . (\displaystyle F=(X\rightarrow Y)\wedge ((\neg Y\rightarrow Z)\rightarrow \neg X).)
Перетворимо формулу F (\displaystyle F)до формули, що не містить → (\displaystyle \rightarrow):
F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ Y ∨ Z) ∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\wedge (\neg (\neg Y\rightarrow Z)\vee \neg X)=(\neg X\vee Y)\wedge (\neg (\neg \ neg Y\vee Z)\vee \neg X).)
В отриманій формулі перенесемо заперечення до змінних і скоротимо подвійні заперечення:
F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X) . (\displaystyle F=(\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).)
Нормальна форма логічної формули не містить знаків імплікації, еквівалентності та заперечення неелементарних формул.
Нормальна форма існує у двох видах:
СКНФ
Досконала кон'юнктивна нормальна форма (СКНФ) -- це КНФ, яка задовольняє трьома умовами:
Будь-яка булева формула, яка не є тотожно істинною, може бути подана у СКНФ.
Правила побудови СКНФ за таблицею істинності
До кожного набору змінних, у якому функція дорівнює 0, записується сума, причому змінні, які мають значення 1, беруться із запереченням.

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

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

Малюнок 1.

Рішення:

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

Малюнок 2.

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

Диз'юнктивні та кон'юнктивні нормальні форми алгебри висловлювань.Для кожної функції логіки висловлювань можна скласти таблицю істинності. Зворотне завдання теж завжди можна розв'язати. Введемо кілька визначень.

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

одного разу.

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

Елементарними диз'юнкціями (диз'юнктами)називаються диз'юнкції змінних із запереченнями чи ні них.

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

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

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

1. Перейти до булевих операцій, використовуючи формули еквівалентних перетворень.

2. Перейти до формул із тісними запереченнями, тобто до формули, в якій заперечення розташовуються не вище, ніж над змінними – застосувати закони де Моргана.

3. Розкрити дужки – застосувати закони дистрибутивності.

4. Складники, що повторюються, взяти по одному разу – закон ідемпотентності.

5. Застосувати закони поглинання та напівпоглинання.

Приклад 6.Знайти ДНФ формули: .

В алгебрі Буля справедливий принцип двоїстості. Він полягає у наступному.

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

Приклад 7.Знайти функцію, подвійну до .

Серед елементарних функцій алгебри логіки 1 двояка 0 і навпаки, х подвійна х, подвійна, двоїста і навпаки.

Якщо у формулі F 1 представляє функцію всі кон'юнкції замінити

на диз'юнкції, диз'юнкції на кон'юнкції, 1 на 0, 0 на 1, то отримаємо формулу F * , Що представляє функцію * , подвійну.

Кон'юнктивна нормальна форма (КНФ) – двояке для ДНФ поняття, тому її легко побудувати за схемою:

Приклад 8.Знайти КНФ формули: .

Скориставшись результатом прикладу 6, маємо

Досконала диз'юнктивна та досконала кон'юнктивна нормальні форми.У кожному з типів нормальних форм (диз'юнктивних та кон'юнктивних) можна виділити клас досконалих форм СДНФ та СКНФ.

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

Будь-яку ДНФ можна спричинити СДНФ розщепленням кон'юнкцій, які містять в повному обсязі змінні, тобто. додаванням для відсутньої змінної x i множиться із застосуванням закону дистрибутивності

Приклад 9.Знайти СДНФ для ДНФ прикладу 6

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

Будь-яку КНФ можна призвести до СКНФ, додаючи член кон'юнкції, який не містить будь-якої змінної X i кон'юнкції і застосовуючи дистрибутивний закон

Приклад 10 .Привести КНФ до СКНФ:

Для побудови СКНФ можна скористатися схемою

Приклад 11.Знайти СКНФ формули прикладу 6.

Будь-яка функція має СДНФ і до того ж, єдину . Кожна функція має СКНФ і до того ж єдину .

Т.к. СДНФ та СКНФ визначені формулами однозначно, їх можна будувати за таблицею істинності формули.

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

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

приклад 12.Знайти СДНФ та СКНФ за таблицею істинності для формули прикладу 6.

У таблиці 14 наведено лише кінцеве значення F=10101101. У справедливості цього твердження слід переконатися самостійно, збудувавши розгорнуту таблицю істинності.

Таблиця 14

x y z