Диз'юнкти́вна норма́льна фо́рма (ДНФ) в булевій логіці — нормальна форма в якій булева формула має вид диз'юнкції декількох кон'юнктів (де кон'юнктами називаються кон'юнкції декількох пропозиційних символів або їх заперечень).
Приклади
Наступні формули записані в ДНФ:
Наступні формули не є в ДНФ:
Проте ці формули еквівалентні наступним формулам записаним у диз'юнктивній нормальній формі:
Приведення булевої формули до ДНФ
Довільна може бути приведена до ДНФ за допомогою наступного алгоритму:
- Крок 1 : Усі логічні зв'язки виразити через кон'юнкцію, диз'юнкцію і заперечення.
- Крок 2 : Скасувати всі подвійні заперечення і використати, де можливо, закони де Моргана. Тобто замінити:
- на
- на
- на
- Крок 3 : Використати де можливо дистрибутивність кон'юнкції, тобто замінити:
- на
Втім, при цьому розмір булевої формули може зрости експоненціально. Так, наприклад, щоб записати наступну формулу буде потрібно 2n кон'юнктів:
КНФ цієї формули має вигляд:
Формальна граматика, що описує ДНФ
Наступна формальна граматика описує всі формули, приведені до ДНФ:
- <ДНФ> → <кон'юнкт>
- <ДНФ> → <ДНФ> ∨ <кон'юнкт>
- <кон'юнкт> → <літерал>
- <кон'юнкт> → (<кон'юнкт> ∧ <літерал>)
- <літерал> → <терм>
- <літерал> → ¬<терм>
де <терм> позначає довільну булеву змінну.
Див. також
Джерела
Shawn Hedman. A First Course in Logic. Oxford University Press 2004
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Diz yunkti vna norma lna fo rma DNF v bulevij logici normalna forma v yakij buleva formula maye vid diz yunkciyi dekilkoh kon yunktiv de kon yunktami nazivayutsya kon yunkciyi dekilkoh propozicijnih simvoliv abo yih zaperechen PrikladiNastupni formuli zapisani v DNF A B displaystyle A lor B A displaystyle A A B A displaystyle A land B lor neg A A B C D E F C D B displaystyle A land B land neg C lor neg D land E land F lor C land D lor B Nastupni formuli ne ye v DNF B C displaystyle neg B land C A B C D displaystyle A lor B land C lor D Prote ci formuli ekvivalentni nastupnim formulam zapisanim u diz yunktivnij normalnij formi B C displaystyle neg B lor neg C A B C B D displaystyle A lor B land C lor B land D Privedennya bulevoyi formuli do DNFDovilna mozhe buti privedena do DNF za dopomogoyu nastupnogo algoritmu Krok 1 Usi logichni zv yazki viraziti cherez kon yunkciyu diz yunkciyu i zaperechennya Krok 2 Skasuvati vsi podvijni zaperechennya i vikoristati de mozhlivo zakoni de Morgana Tobto zaminiti A displaystyle lnot lnot A na A displaystyle A A B displaystyle lnot A land B na A B displaystyle lnot A lor lnot B A B displaystyle lnot A lor B na A B displaystyle lnot A land lnot B dd Krok 3 Vikoristati de mozhlivo distributivnist kon yunkciyi tobto zaminiti A B C displaystyle A land B lor C B C A displaystyle B lor C land A na A B A C displaystyle A land B lor A land C dd Vtim pri comu rozmir bulevoyi formuli mozhe zrosti eksponencialno Tak napriklad shob zapisati nastupnu formulu bude potribno 2n kon yunktiv X1 Y1 X2 Y2 Xn Yn displaystyle X 1 lor Y 1 land X 2 lor Y 2 land dots land X n lor Y n KNF ciyeyi formuli maye viglyad X1 Xn 1 Xn X1 Xn 1 Yn Y1 Yn 1 Yn displaystyle X 1 vee cdots vee X n 1 vee X n wedge X 1 land cdots land X n 1 land Y n lor cdots lor Y 1 land cdots land Y n 1 land Y n Formalna gramatika sho opisuye DNFNastupna formalna gramatika opisuye vsi formuli privedeni do DNF lt DNF gt lt kon yunkt gt lt DNF gt lt DNF gt lt kon yunkt gt lt kon yunkt gt lt literal gt lt kon yunkt gt lt kon yunkt gt lt literal gt lt literal gt lt term gt lt literal gt lt term gt de lt term gt poznachaye dovilnu bulevu zminnu Div takozhKon yunktivna normalna forma Normalna forma formuli u logici predikativ Chislennya vislovlen Algoritm Blejka Doskonala diz yunktivna normalna formaDzherelaShawn Hedman A First Course in Logic Oxford University Press 2004 ISBN 0 19 852980 5