U aynan yolgon formuladir


Download 488.36 Kb.
bet1/3
Sana08.05.2023
Hajmi488.36 Kb.
#1442697
  1   2   3
Bog'liq
Chinlik jadvali yordamida formulalarni mukammal diz’yunktiv normal formaga va mukammal kon’yunktiv normal formaga keltirish


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 .

  1. 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 (AV) 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 V ,)) formula xam ch kiymat kabul kiladi. Dem ak, ((AV)-+ —>(/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.




Download 488.36 Kb.

Do'stlaringiz bilan baham:
  1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling