Ikkilik qonuni. Normal formalar

Ikkilik qonuni. Normal formalar Reja: 1.Ikkilik qonuni. 2.Normal formalar. 3.Mukammal normal formalar. ta'rif. MA ning formulasida faqat , , mantiq amallari qatnashib, faqat propozitsional ûzgaruvchilarga tegishli bûlsa, u sholda keltirilogan formula ( forma ) deyiladi. Lemma . Agar MA ning formulasi keltirilgan formula bûlsa, MA ning formulaga teng kuchli keltirilgan formulasi mavjud. Teorema. MA ning ishtiyoriy formulasiga teng kuchli keltirilgan formula mavjud. Isbot. Formula rangi bûyicha matematik induksiya metodi bilan isbot qilinadi. Agar formulaning rangi 0 ga teng bûlsa, u propozitsional ûzgaruvchi bûlibb isbot ravshan. Ishtiyoriy natural k 1 uchun rangi k dan kichik formulaga teng kuchli keltirilgan formula mavjud bûlsin. U sholda, formula ta'rifiga kûra formula , , , , formulalardan biri kûrinishida bûladi. , - keltirilgan formulalar, uchun esa lemmaga asosan teng kuchli keltirilgan formula mavjud. formulani formula bilan , formulani ( ) ( ) formula bilan, bu formuladagi , formulalarni lemmaga asosan teng kuchli keltirilgan formulalar bilan almashtiramiz. Natijada berilgan formulaga teng kuchli keltirilgan formula shosil bûladi. Shunday qilib, formulaga teng kuchli keltirilgan formula mavjud. - keltirilgan formula, yani formulada , , - mantiq amallarigina qatnashib, faqat propozitsional ûzgaruvchilargagina tegishli bûlsin. ta'rif. MA ning * formulasi formuladan konyunksiyani dizyunksiya bilan , dizyunksiyani esa konyunksiya bilan almashtirish natijasida shosil qilingan bûlsa, u sholda * va formulalar ûzaro qûshma formulalar deyiladi. Teorema. Agar va formulalar teng kuchli formulalar bûlsa , u sholda * va * formulalar sham teng kuchli formulalar bûladi. 1, 2, . . . , n ( n 1 ) MA ning formulalari bûlsin, u sholda (. . .( ( 1 2 ) 3 ). . . n ) -formula 1, 2, . . . ,n - formulalarning konyunksiyasi deyiladi va 1 . . . n orqali belgilanadi. (. . .( ( 1 2 ) 3 ) . . . n ) - formula esa 1 , 2 , . . . , n - formulalarning dizyunksiyasi deyiladi va ( 1, . . . ,n)- orqali belgilanadi. ta'rif. Propozitsional ûzgaruvchilar yoki ularning inkorlaridan tuzilgan iùtiyoriy konyunksiya ( dizyunksiya) elementar konyunksiya (dizyunksiya ) deyiladi. ta'rif. Elementar konyunksiyalarning iùtiyoriy dizyunksiyasi - dizyunktiv normal forma (dnf), elementar dizyunksiyalarning iùtiyoriy konyunksiyasi- konyunktiv normal forma (knf) deyiladi. Misol . X1,X2,X3 - propozitsional ûzgaruvchilar berilgan bûlsin, u ùolda ( X1 X2) X3 - dnfga , ( X1X2) (X1X3) - knfga misol bûladi. ta'rif. formula X1,X2,. . . ,Xn - propozitsional ûzgaruchilardan tuzilgan elementar konyunksiya bûlsin. Agar ùar bir propozitsional ûzgaruvchi, inkori ùam ùisoblanganda, ...