1 - t a ’ r i f . Elementar muloxazalarning xamma kiymat lar satrlarida fakat chin kiymatni kabul kiluvchi formula aynan chin (doimo chin) formula yoki t avt ologiya deb ataladi va J bilan belgilanadi. A formulaning tavtologiya ekanligi yoki emasligi k,iy matlar jadvalini tuzish orkali aniklanadi. M i s o l l a r . J= xl(x->u)->u formula tavtologiyadir. Xakikatan: 2-ta’rif. Elementar muloxazalarning xamma kiymatlar satrlarida fakat yolgon kiymatni kabul kiluvchi formulalar aynan yo lt n (doimo yo lt n ) yoki baj arilmaydigan formulalar deyiladi va J bilan belgilanadi. Masalan, J = (x v u) a (x —> u) aynan yolgon formuladir: Ma’lumki, aynan chin formulaning inkori aynan yolgon formula buladi va aksincha. A ynan chin va ynan yolgon formulalar unga kiradigan uzgaruvchilarga boglik, bulmay. fakat bitta kiymat kabul kiladi. 3-ta’rif. Agar (A{0} В) т авт ология булса, у холда А ва В м ант илий эквивалент деб аталади. Агар (А^В) тавтология булса, у холда В формула А нинг мантилий хулосаси деб аталади. Энди Э .М ндельсоннинг [39] китобида баён этилган тавтологияларга оид айрим теоремаларни келтирамиз. 1-теорема. Агар А ва А^>V aynan chin formulalar (tavtologiyalar) bulsa, u xolda V formula xom tavtologiya buladi. Isbot. A va A-> V tavtologiyalar bulsin. A va V f orm ulalarning tarkibiga kiruvchi uzgaruvchilarning bi ror Kiymatlar satrida V formula yolgon kiymat kabul kilsin. A formula tavtologiya bulganligi uchun zgaruvchilarning usha kiymatlar satrida A chin kiymat kabul kiladi. U holda (A^>V) formula yolgon kiymat kabul kiladi. Bu natija (A-»B) ning tavtologiya degan farazimizga karama-karshidir. Demak, V tavtologiyadir. 2-teorema. Agar x g x2, ..., xp uzgaruvchilarga boglik bulgan A formula t avt ologiya va V formula A formuladan x x, x2, ..., xp uzgaruvchilar urniga mos ravishda A v A2, ..., Ap formulalarni kuyish nat ij asida xosil kilingan bulsa, u xolda V formula tavtologiya buladi, yaʼni tavtologiyada urniga kuyish yana tavtologiyani keltirib chikaradi. Isbot. A tavtologiya bulsin va V formula tarkibiga kiruvchi uzgaruvchi muloxazalarning ixtiyoriy kiymatlar satri berilgan bulsin. U xolda A g A2, ..., Ap formulalar u g u 2, ..., u p (xar bir x(. ch yoki yo kiymat kabul kiladi) kiymatlar kabul kiladi. Agar x {, x2, ..., xya ga mos ravishda u g u g, ..., u p kiymatlarni bersak, u xolda A ning natijaviy kiymati V ning chinlik kiymatiga mos keladi. A tavtologiya bulganligi uchun V formula tarkibiga kirgan uzgaruvchilarning berilgan ixtiyoriy kiymatlar satrida ch kiymat Kabul kiladi. SH unday kilib, V doim o ch kiymat kabul kiladi va u tavtologiya buladi. 3-teorema. Agar A t formula tarkibiga bir yoki kup marta kirgan A formula urniga V formulani kuyish natij asida V{ formula xosil silinsa, u xolda ((u4<-4 5)->(u4,<->5,)) tavtologiya buladi. Demak, A va V lar mantiliy ekvivalent bulsa, u xolda A { va Bi xam mantiliy ekvivalent buladi. Isbot. Agar A va V formulalar uzgaruvchilarning ixtiyoriy kiymatlar satrida karama-karshi chinlik iymatlariga ega bulsa, u xolda (A<n>V) ning chinlik kiymati yo buladi va natijada ((L< -»/?)-> (/1,^ 5,)) formula ch kiymat Kabul kiladi. Agar A va V lar uzgaruvchilarning ixtiyoriy kiymatlar satrida bir xil chinlik kiymati kabul kilsa, u xolda A } va Vx formulalar xam bir xil chinlik kiymati kabul kiladi, chunki teoremaning shartiga asosan , formula A x formuladan A ning urniga V ni kuyish natijasida xosil kilingan. D yem ak , bu xolda (A<^>V) xam, (/!,<-»£,) xam ch kiymat kabul kiladi. SH uning uchun ((A < -^ B )^ (A t <r-> V ,)) formula xam ch kiymat kabul kiladi. Dem ak, ((A<t->V)-+ —>(/4, 5 ,)) formula tavtologiya buladi. 4-taʼrif. Elementar muloxazalarning kamida bitta Kiymatlar satrida chin kiymat kabul щ luvchi va aynan chin bulmagan formula baj ariluvchi f ormula deb ataladi. Masalan, (x a U) (x l u ) ; [(x ou)l(xu^)]->g; xwy; x — formulalar bajariluvchi formulalar xisoblanadi. A ynan chin formulalar katta axamiyatga ega bulib, ular mantik, k,onunlarini if odalaydi. SH u m unosabat bilan kuyidagi masala tugiladi: shunday metodni topish kerakki, u chekli mikdordagi amallar yordamida mantik, algebrasining ixtiyoriy muayyan formulasini aynan chin yoki aynan chin emasligini anikugasin. Bunday metod yechiluvchi met od, yoki algoritm, yoki yechiluvchi protsedura deyiladi. Kuyilgan masalaning uzi esa «yechilish muammosi” deyiladi. Bu muammo fak,at muloxazalar algebrasi uchungina em as, balki boshk,a mantiliy sistemalar uchun xam kuyiladi. U muloxazalar algebrasi uchun ijobiy xal etiladi. Bu yerda yechiluvchi protsedura sif atida chinlik jadvalini olish imiz mumkin, chunki bunday jadval xar bir muayyan formula uchun kuyilgan savolga javob beradi. Agar berilgan formulaga mos keladigan jadvalning oxirgi ustunida fak,at «chin” bulsa, u xolda bu formula aynan «chin”, agar oxirgi ustunda xech bulmaganda bitta «yolgon” bulsa, u xolda formula aynan chin emas buladi. Tabiiyki, amalda bu usulni xar doim xam kullab bulavermaydi (chunki formulada p ta uzgaruvchi k,atnashsa, bunday jadval 2" ta satrga ega buladi). L yekin xar doi m chekli mitsdordagi amallar bajarib, prinsip jixatdan kuyilgan savolga javob berish mumkin. Keyingi paragraflarda boshk,a bir yechiluvchi protsedurani keltiramiz, u berilgan formulani normal shaklga keltirishga asoslangan. Normal shakllar matematik mantik,ning boshk,a masalalarida ham ishlatiladi. Form ulalarning normal shakllari Teng kuchli almashtirishlar bajarib, muloxazalar algebrasining formulalarini xar xil kurinishlarda yozish mumkin. Masalan, A -+ VS formulani L v i? C yoki {A v B )(A v Q . kurinishlarda yoza olamiz. Mantik algebrasining kontakt va rele-kontaktli sxemalar, diskret texnikadagi tadbiqlarida va matematik mantikning boshk.a masalalarida formulalarning normal shakllari katga axamiyatga ega. Kuyidagi belgilashni kiritamiz: kurinishdagi formula elementar dizʼyunksiya deb ataladi, bu yerda xam a = {st,, st2, ..., стл} ixtiyoriy kiymatlar satri va x(. uzgaruvchilar orasida bir xillari bulishi mumkin. 3 - t a ʼ r i f . Elementar dizʼyunksiyalarning konʼyu nksiyasi formulaning konʼyunktiv normal shakli (KNSH ) va element ar konʼyunksiyalarning dizʼyunksiyasi formulaning dizʼyunktiv normal shakli (DNSH) deb ataladi. KN SH ga (x v u ) l (Zs v z) a (x v u v z) formula va D N SH ga x y v x z v xyz formula misol bula oladi. 1-teorema. Elementar muloxazalarning xar bir R formulasiga teng kuchli konʼyunktiv normal shakldagi Q formula mavj ud. Bu teoremani isbotlashda ushbu teng kuchliliklardan foydalanamiz: Rdagi elementar muloxazalar l va v amallari bilangina birlashtirilgan bulsa xam, lekin d sunggi amalni ifodalamaydi. Bu xolda Av(BaC) = (Av B)a(AvB) istributivlik konunidan foydalanib, sunggi amali d dan iborat teng kuchli formulaga keltiramiz;R formula - , V, d, -u, mantikiy amallar vositasida tuzilgan biror formulani ifodalasin. U xolda R ga (3) teng kuchliliklarni tatbik etib, R bilan teng kuchli va v, l bilan ifodalangan R 1 formulani xosil kilamiz. Agar R1 K N SH kurinishida bulmasa, unga Av (Ba Q = (AvB)a (Av B) distributivlik konunini tatbik etib, chekli adamlardan keyin R bilan teng kuchli Q konʼyunktiv normal shakldagi formulaga kelamiz. Izox- R formulani konʼyunktiv normal shaklga keltirish jarayonida Shunday kilib, P formulaning K N SH bittagina dizʼyunktiv (xvy) xaddan iborat ekan. R formula tavtologiya ekanligini chinlik jadvaliga murojaat kilmay turib xam nikdash mumkinmi degan savolga kuyidagi chinlik alomati deb atalgan eorema ijobiy javob beradi. 2-teorema. R formula doimo chin bulishi uchun uning K N SH dagilar bir elementar dizʼyunktiv %adida kam ida bitta elementar muloxaza bilan birga bu muloxazaning inkori ham mavjud bulishi zarur va yetarli. Isbot: R formulaningR = A1 a A2 A ... a A„ (5) K N SH dagi xar bir A1. xadida kamida bitta elementar muloxaza bilan birga bu muloxazaning inkori xam mavjud bulsin, yaʼni A/ = x v x v u v ...v i shaklida bulsin, u xolda x v x - J va J v A = J larga asosan A,- = J v ( y v . . . v u v V) = J buladi. Demak, R = J a J a ... a J = J buladi, yaʼni aynan chin formula buladi. Endi R tavtologiya bulsin va A, uning K N SH dagi shunday elementar dizʼyunktiv xadi bulsinki, unda birorta elementar muloxaza bilan birga uning inkori katnashmagan bulsin. Masalan, A, = x v u v ... v i shaklida bulsin. Endi, elementar muloxazalarning shunday kiymatlar satrini olaylikki, bu satrda x ning kiymati yo, u ning kiymati ch, Z ning kiymati yo, ..., i ning kiymati yo bulsin. U vakgdaD. = x v u v ... v i = yo v ch v ... v yo = yo v ... v yo = yo. Demak, R = A1 a A2 a ... a A„ n i n g kiymati xam yolgon buladi. Ammo, eoremaning shartiga asosan R ning kiymati aynan chindir. Natijada karama-karshilikka keldik. Demak, elementar dizʼyu nksiyalarning xar bir xadida birorta muloxaza uzi va u:;ining inkori bilan katnashishi shart. Mukammal konʼyuktiv va dizʼyuktiv normal shakllar Mantik, algebrasining bitta formulasi uchun bir nechta D N SH (K N SH ) mg.gjud bulishi mumkin. Masalan, (xvy)(xv^) formulani kuyidagi xvy^, xvxyvxz D N SH larga keltirish mumkin. Bular distributivlik va dempotentlik k;onunlarini kullash natijasida xosil kilingan. Formulalarni bir k,iymatli ravishda normal shakldatasvirlash uchun mukammal dizʼyu nktiv normal shakl va mukammal konʼyunktiv normal shakl (M D N SH va MKNSH) deb ataluvchi kurinishlari ishlatiladi. 1-taʼrif. (1) elementar dizʼyunksiya ((2) elementar konʼyunksiya) ifodasida x,ar bir elementar muloxaza x. bir mart a satnashgan bulsa, u tugri elementar dizʼyunksiya (turri elementar konʼyunksiya) deb ataladi. M asalan, x ,v x 2v x 3 va x, v x4 v x 6 elementar dizʼyu nksiyalar va XjXjXj va x ,x 3x 6 elementar konʼyunksiyalar mos ravish da tugri elem yentar dizʼyu nksiyalar va elem yentar konʼyunksiyalar buladi. 2-taʼrif. (1) elementar dizʼyunksiya ((2) elementar konʼyunksiya)ning ifodasida x,, x 2, ..., xp muloxazalarning xor bittasi bir mart agina satnashgan bulsa, u x,, x 2, ..., xya muloxazalarga nisbatan tulщ elementar dizʼyunksiya (tulits elementar konʼyunksiya) deb ataladi. Masalan, x, v x 2 v x 3 va x, v x 2 v x 3 elementar dizʼyu nksiyalar va x ,x 2x 3, x ,x 2x 3 elementar konʼyunksiyalar x,, x 2, x3 muloxazalarga nisbatan tulik, elementar dizʼyunksiyalar va tulik, elementar konʼyunksiyalar buladi. 3-taʼrif. A gar D N SH (KNSH) if odasida bir xil elementar konʼyunksiyalar (elementar dizʼyunksiyalar) bulmasa va x<*mma elementar konʼyunksiyalar (elementar dizʼyu nksiyalar) myFpu va tulits bulsa, u mukammal dizʼyunktiv normal shakl (mukammal konʼyunktiv normal shakl) M DNSH (MKNSH) deb ataladi. Masalan, xyz v xyz v x yz v xug D N SH x, u, z muloxazalarga nisbatan M DN SH buladi. (x v u )(x v u )(x v u ) KN SH muloxazalarga nisbatan MKNSH buladi. A sosiy m antiliy am allarning M D N SH va MKNSH kurinishlari kuyidagicha buladi: 1-teorema, p ta elementar muloxazaning aynan chin formulasidan farsli xar bir A formulani mukammal konʼyunktiv normal shaklga (MKNSH ) keltirish mumkin. Isbot. Kuyidagi isbot tavtologiyadan farq qiluvchi har qanday A formulani M K N SH ga keltirish algoritmi buladi. Avvalo A formulani konʼyunktiv normal shaklga keltiramiz. Buning uchun A ormulani konʼyunksiya, dizʼyu nksiya va inkor mantikiy amallari orkali if odalaym iz(inkor amali fakatgina uzgaruvchilar ustida bulishi kerak). Sungra distributivlik konunlaridan foydalanib, A f ormulani K N Щ ga keltiramiz va xamma lozim bulgan oddalashtirishlarni bajaramiz.Agar K N SH if odasida bir nechta bir xil elementar dizʼyunksiyalar mavjud bulsa, u xolda x d x = x t e n g kuchlilik formulasidan foydalanib, ulardan bittasini A ifodasida koldiramiz.Kuyidagi ikki usul orkali xamma elementar dizʼyunksiyalarni tugri elementar dizʼyunksiyalarga aylantiramiz:agar biror elementar dizʼyunksiya ifodasida birorta uzgaruvchi uzining inkori bilan katnashgan bulsa, u xolda x v x = ch , 4vx=4, x a x = x teng kuchlilik formulalarga asosan biz bu elementar konʼyunksiyani KNSH ifodasidan olib tashlaymiz;agar biror uzgaruvchi elementar dizʼyu nksiya if odasida bir necha marta ,atnashgan bulsa (yoki xamma xolda inkor ish orasi ostida em as, yoki xamma xolda inkor ish orasi ostida), u xolda x v x formulasiga asosan biz ulardan fakatgina bittasini KN SH ifodasida k,oldiramiz.Natijada, xamma elementar dizʼyunksiyalar tugri el yementar dizʼyunksiyalarga aylanadi. Agar baʼzi elementar dizʼyunksiyalar tulik, elementar dizʼyu nksiyalar bulmasa, aʼni dizʼyu nktiv xadlarda el yementar muloxazalarning baʼzilari (yoki ularning nkorlari) mavjud bulmasa, u xolda bunday elementar dizʼyu nksiyalarni tulik, lementar dizʼyunksiyalar xolatiga keltirish kerak.Masalan, ush bu х, V х2 V ... V х,_, V Хм V ... V Х п elementar dizʼyunksiya ifodasida x. yoki x, yuk, deb faraz k,ilaylik. U xolda uni x, l x, = 0 va D v 0 = D formulalardan foydalanib kuyidagi ikki tulik; elementar izʼyunksiya konʼyunksiyasiga keltira olamiz: Agarda elem yentar dizʼyu nksiya if odasida bir nechta y v u 2, ..., up uzgaruvchilar k,atnashmayotgan bulsa, u xolda uning ifodasiga (u, a u,.) (/ = 1, t) konʼyu nksiyalarni mantik,iy kushib, distributivlik k,onunini kullaymiz. N atijada, bitta tulik, em as elementar dizʼyu nksiya urniga 2t ta tulik, elementar dizʼyu nksiyaga ega bulamiz. Turtinchi kddam bajarilishi natijasida K N SH ifodasida bir xil elementar izʼyunksiyalar paydo buladi. SHuning uchun yana 2 - kddamni ishlatamiz.Demak, 1—5- kddamlar natijasida KNSH ifodasida bir xil elementar dizʼyunksiyalar mavjud bulmaydi va xamma elementar dizʼyunksiyalar tuf i va tulik, buladi. taʼrifga asosan, bunday KN SH mukammal konʼyunktiv normal shakl buladi. Misollar. 1. A = (x -» x) l (u —» u) v (z i) formula kuyidagi M K N SH ga ega buladi: mukammal dizʼyunktiv normal shaklga ega bulamiz. M ukam m al di zʼ yu n k ti v norm al sh aklning xar bir x,1 axJa., .a x ), xadi konʼyunktiv konstituyent deb ataladi. 2-teorema, p ta elementar muloxazalarning aynan yolgon formulasidan farsli xar bir A formulasini mukammal dizʼyunktiv normal shaklga keltirish mumkin. Isbot. Berilgan formulani A bilan belgilab, avvalo A ni mukammal konʼyunktiv normal shaklga keltiramiz: