Кон'юнкти́вна норма́льна фо́рма (КНФ) в булевій логіці - нормальна форма в якій булева формула має вид кон'юнкції декількох диз'юнктів (де диз'юнктами називаються диз'юнкції декількох пропозиційних символів або їх заперечень). Кон'юнктивна нормальна форма широко використовується в автоматичному доведенні теорем, зокрема вона є основою для використання правила резолюції.
Приклади
Наступні формули записані в КНФ:
Наступні формули не є в КНФ:
Проте ці формули еквівалентні наступним формулам записаним у кон'юнктивній нормальній формі:
Приведення булевої формули до КНФ
Довільна може бути приведена до КНФ за допомогою наступного алгоритму:
- Крок 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, Інтернет
Kon yunkti vna norma lna fo rma KNF v bulevij logici normalna forma v yakij buleva formula maye vid kon yunkciyi dekilkoh diz yunktiv de diz yunktami nazivayutsya diz yunkciyi dekilkoh propozicijnih simvoliv abo yih zaperechen Kon yunktivna normalna forma shiroko vikoristovuyetsya v avtomatichnomu dovedenni teorem zokrema vona ye osnovoyu dlya vikoristannya pravila rezolyuciyi PrikladiNastupni formuli zapisani v KNF A B displaystyle A land B A displaystyle A A B A displaystyle A lor B land neg A A B C D E F C D B displaystyle A lor B lor neg C land neg D lor E lor F land C lor D land B Nastupni formuli ne ye v KNF 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 Prote ci formuli ekvivalentni nastupnim formulam zapisanim u kon yunktivnij normalnij formi 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 Privedennya bulevoyi formuli do KNFDovilna mozhe buti privedena do KNF 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 pravila 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 diz yunkciyi tobto zaminiti A B C displaystyle A lor B land C i B C A displaystyle B land C lor A na A B A C displaystyle A lor B land A lor C dd Vtim pri comu rozmir bulevoyi formuli mozhe zrosti eksponencialno Tak napriklad shob zapisati nastupnu formulu bude potribno 2n diz yunktiv X 1 Y 1 X 2 Y 2 X n Y n displaystyle X 1 land Y 1 lor X 2 land Y 2 lor dots lor X n land Y n KNF ciyeyi formuli maye viglyad X 1 X n 1 X n X 1 X n 1 Y n Y 1 Y n 1 Y n displaystyle X 1 vee cdots vee X n 1 vee X n wedge X 1 vee cdots vee X n 1 vee Y n wedge cdots wedge Y 1 vee cdots vee Y n 1 vee Y n Formalna gramatika sho opisuye KNFNastupna formalna gramatika opisuye vsi formuli privedeni do KNF lt KNF gt lt diz yunkt gt lt KNF gt lt KNF gt lt diz yunkt gt lt diz yunkt gt lt literal gt lt diz yunkt gt lt diz 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 takozhDiz yunktivna normalna forma Normalna forma formuli u logici predikativ Chislennya vislovlen Doskonala kon yunktivna normalna formaDzherelaShawn Hedman A First Course in Logic Oxford University Press 2004 ISBN 0 19 852980 5