Formulalar. Asosiy teng kuchli formulalar. Mulohazalar algebrasining funktsiyalari
Download 387.15 Kb.
|
1м
|
FORMULALAR. ASOSIY TENG KUCHLI FORMULALAR. MULOHAZALAR ALGEBRASINING FUNKTSIYALARI. I.1.1 – ta’rif. Rost yoki yolg‘onligini bir qiymatli aniqlash mumkin bo‘lgan darak gap mulohaza deyiladi. « +ayin – daraxt », « Negrlar – oq tanli odamlar », « 5 > 2 », « Bugun – 5 – may » kabi gaplar mulohazalarga misol bO‘la oladilar. Lekin har qanday gap ham mulohaza bo‘la olmaydi, masalan, « YAshasin O‘zbekiston yoshlari! », « Sen nechanchi kursda o‘qiysan? » kabi gaplar mulohazalar emas, chunki ular darak gaplar emas. Demak, biror bir gap mulohaza bO‘lishi uchun, u albatta darak gap bO‘lishi va rost yoki yolg‘onligi bir qiymatli aniqlanishi shart. O‘zbek tilidagi barcha mulohazalar tO‘plamini ℳ orqali belgilaylik. ℳ tO‘plamning elementlarini lotin alifbosining bosmacha, indeksli yoki indekssiz bosh harflari bilan belgilashga kelishib olamiz. YA’ni A , V , S , . . . , A 1, A 2 , . . . , A n - mulohazalardir. A mulohaza rost bO‘lsa, unga 1 ni, yolg‘on bO‘lsa, 0 ni mos qO‘yamiz. I.1.2 – ta’rif. A va V mulohazalarning kon’yunksiyasi deb, A va V mulohazalar rost bO‘lgandagina rost, qolgan hollarda yolg‘on bO‘ladigan A Ù V mulohazaga aytiladi. Mulohazalar kon’yunksiyasi mantiqiy kO‘paytirish deb ham ataladi va A · V yoki A & V kabi belgilanishi mumkin. I.1.3 - ta’rif. A va V mulohazalar diz’yunksiyasi deb, A va V mulohazalarning ikkalasi ham yolg‘on bO‘lgandagina yolg‘on, qolgan hollarda rost bO‘ladigan A V mulohazaga aytiladi. Mulohazalar diz’yunksiyasi mantiqiy qO‘shish deb ham yuritiladi va A V kabi belgilanishi ham mumkin. I.1.4 - ta’rif. A mulohaza rost bO‘lganda yolg‘on, yolg‘on bO‘lganda rost bO‘ladigan A mulohaza A mulohazaning inkori deyiladi. A mulohazaning inkori A orqali belgilanishi ham mumkin. Mulohazalar ustida bajariladigan amallar rostlik jadvali deb ataladigan jadvallar yordamida ham berilishi mumkin. YUqorida ta’riflangan amallar rostlik jadvali quyidagi kO‘rinishda bO‘ladi :
Bundan tashqari yana bir qancha amallar, ya’ni : - implikatsiya yoki mantiqiy hulosa, yoki - ekvivalensiya yoki mantiqiy teng kuchlilik, - SHefer shtrixi, - Pirs strelkasi, - qat’iy diz’yunksiya, ya’ni 2 modul bO‘yicha qO‘shish amallari quyidagi jadval orqali beriladi:
Takrorlash uchun savollar : +anday gaplar mulohaza bo‘ladi ? Mulohazalar kon’yunksiyasi, diz’yunksiyasi, implikatsiyasi, ekvivalensiyasi hamda inkori ta’riflarini ayting. Rostlik jadvali nima ? Biri ikkinchisining inkori bo‘lgan mantiq amallarini keltiring. Mashqlar : +uyidagi gaplar ichidan mulohazalarni ajrating va ularning rost yoki yolg‘on ekanligini aniqlang : 1). Sirdaryo Orol dengiziga quyiladi. 2). Siz qaysi oliygohda o‘qiysiz ? 3). O‘zbekiston Mustaqilligining 10 yilligi muborak bo‘lsin! 4). Har qanday son musbat. 5). 0 har qanday haqiqiy songa bo‘linadi. 6). 2, 3, 5 sonlari tub sonlar. 7). Barcha insonlar yoshi 20 da. 8). Galaktikamizda shunday sayyora bor-ki, unda hayot mavjud. 9). 5 soni 25 va 70 sonlarining eng katta umumiy bo‘luvchisi. 10). 3x3 – 5u 9. +uyidagi juftliklarining qaysisida mulohazalar bir – birining inkori ? 2 0, 2 0. 6 9, 6 9 . « AVS to‘g‘riburchakli uchburchak», « AVS o‘tmas burchakli uchburchak». « f- funksiya – toq » , « f – funksiya – juft ». «Barcha tub sonlar toq» , «SHunday tub son mavjud-ki, u juft». «Irratsional sonlar mavjud», «Barcha sonlar ratsional». +uyidagi mulohazalarning rostlik qiymatini aniqlang: 1). Agar 12 6 ga bo‘linsa, u holda 12 3 ga bo‘linadi. 2). Agar 11 6 ga bo‘linsa, u holda 11 3 ga bo‘linadi. 3). Agar 15 6 ga bo‘linsa, u holda 15 3 ga bo‘linadi. 4). Agar 15 3 ga bo‘linsa, u holda 15 6 ga bo‘linadi. 5). 12 6 ga bo‘linadi, faqat va faqat shu holda-ki, agar 12 3 ga bo‘linsa. 6). 15 6 ga bo‘linadi, faqat va faqat shu holda-ki, agar 15 3 ga bo‘linsa. Agar A orqali « 9 3 ga bo‘linadi», V orqali « 8 3 ga bo‘linadi» degan mulohazalar belgilangan bo‘lsa, u holda quyidagi mulohazalarni so‘zlar orqali ifodalang va rostlik qiymatini aniqlang : A V , V A , A V , V A , A V , V A , A V , V A , A V , A V , A V , A V . I.2.1 - ta’rif. < M , , , , , > - universal algebra mulohazalar algebrasi deyiladi. Mulohazalar algebrasini qisqacha MA deb belgilaymiz. MA ning alfaviti quyidagilardan iborat : A , V , S , . . . – mulohazalarni belgilash uchun ishlatiladigan xarflar; , , , , - mantiq amallarini belgilash uchun ishlatiladigan belgilar; ( , ) - chap va O‘ng qavslar . Mulohazalar algebrasining asosiy tushunchalaridan biri formula tushunchasidir. Unga induktiv ta’rif beramiz. I.2.2 - ta’rif. 1). Xar bir mulohaza formuladir. 2). Agar va lar formulalar bO‘lsa, u holda ( ) , ( ) , ( ) , ( ) , ( ) lar ham formulalardir. 3). 1) va 2) lar yordamida hosil qilingan ifodalargina formulalardir. Masalan, A , V , S lar 1) ga asosan formulalar; ( V ), ( A ( V )), ( ( ( A ( V )) A ) S ) lar 2) ga asosan formulalardir. Formulalarning tarkibidagi qavslarni kamaytirish maqsadida mantiq amallarining bajarilish tartibini , , , , deb belgilab olamiz. Demak, qavslar bO‘lmaganda avval , keyin va h.k. amallar bajariladi. Bundan tashqari tashqi qavslarni ham ehtiyoj bO‘lmaganda tashlab yuboramiz. Bunday O‘zgartirishlardan keyin ( ( A V ) ( ( A ) S ) ) formulani A V ( A S ) kO‘rinishda ¸zishimiz mumkin bO‘ladi. I.2.3 - ta’rif. Formulada qatnashgan mantiq amallari soni formulaning rangi deyiladi. YUqorida keltirilgan formulaning rangi 4 ga teng. I.2.4 - ta’rif. 1. formula - mulohaza bO‘lsa , uning formulaosti faqat uning O‘zidan iborat. Agar formulaning kO‘rinishi dan iborat bO‘lsa, u holda uning formulaostilari , , , hamda va larning barcha formulaostilaridan iborat bO‘ladi. Bu erda - , , , amallaridan biri. Agar formulaning kO‘rinishi bO‘lsa, uning formulaostilari formula, formulaning barcha formulaostilari va ning O‘zidan iborat. Boshqa formulaostilari yO‘q. I.2.5 - misol. ( A V ) A formulaning formulaostilari ta’rifga kO‘ra quyidagilardan iborat : A , V , A , A V , ( A V ) A . Agar formula tarkibiga faqat A 1, A 2, . . . , A n –mulohazalar kirgan bO‘lsa, bu mulohazalarni propozitsional O‘zgaruvchilar deb ataymiz va formulani ehtiyoj bO‘lganda ( A 1, A 2, . . . , A n ) kO‘rinishda yozamiz. Koordinatalari 0 yoki 1 lardan iborat ( i 1, i 2, . . . , i n) vektor, bu erda i k lar 0 yoki 1 lardan iborat, propozitsional O‘zgaruvchilarning qiymatlari tizimi deyiladi. A 1, A 2, . . . , A n propozitsional O‘zgaruvchilarning barcha qiymatlari tizimi 2n ta ekanligini kO‘rish qiyin emas. Demak, agar mulohazalar algebrasining biror formulasi tarkibiga n ta mulohaza kirgan bo‘lsa, bu formulaning rostlik jadvali 2n ta qiymatlar tizimidan tashkil topgan bo‘ladi. I.2.6 - misol . A V A S formulaning rostlik jadvalini tuzing.
Takrorlash uchun savollar : Mulohazalar algebrasi deb nimaga aytiladi ? Mulohazalar algebrasining alfavitini keltiring. Mulohazalar algebrasining formulasi deb nimaga aytiladi ? Mantiq amallarining bajarilish tartibini ayting. Formulaning rangi nima? Formulaosti nima? Formula uchun rostlik jadvali qanday tuziladi ? M a sh q l a r : +uyidagi ifodalardan qaysilari formula ekanligini aniqlang : A V A S V ; A V S A ; A V S ; ( A V ) ( A V S ) ( V ) ; (( A V ) S ) A ; (( A V ) ( S A ) . A V A S formuladan qavslar yordamida hosil qilish mumkin bo‘lgan barcha formulalarni toping. +uyidagi formulalarning barcha formula ostilarini aniqlang : A V S A ; ((A V ) S ) ((( A V ) A ) V ) ; ( A V ) (( A V ) ( A V )) ; A V S A S . YUqoridagi misollarda keltirilgan formulalar ranglarini aniqlang. YUqoridagi misollarda keltirilgan formulalar uchun rostlik jadvallari tuzing. I.3.1 - ta’rif. MA ning va formulalari berilgan bO‘lib, bu formulalar tarkibiga kirgan barcha mulohazalar A1 ,. . ., Am - lardan iborat bO‘lsin. Agar A1 , . . . , A m mulohazalarning barcha qiymatlar tizimlari ( i1, . . . , im ) lar uchun va formulalar bir hil qiymatlar qabul qilsalar, u holda, bu formulalar teng kuchli formulalar deyiladi. va formulalarning teng kuchliligi kO‘rinishda ifodalanadi. I.3.2 - ta’rif. Mulohazalar algebrasining ( A1,. . . , An) formulasi A1 ,. . . , An mulohazalarning barcha qiymatlari tizimi ( i1, . . . , in) uchun 1 qiymat qabul qilsa, aynan rost formula yoki tavtologiya yoki mantiq qonuni deyiladi. Aynan rost formulani qisqacha AR deb belgilaymiz. I.3.3 - ta’rif. MA ning ( A 1, . . . , A n ) formulasi A1 ,. . . , An mulohazalarning barcha qiymatlari tizimi ( i1 , . . . , in ) lar uchun 0 qiymat qabul qilsa, aynan yolg‘on yoki ziddiyat deyiladi I.3.4 - ta’rif. Agar mulohazalar algebrasining (A1 , . . . , An) formulasi A1 , . . . , An larning kamida bitta ( i1 , . . . , in ) qiymatlari tizimida 1 ga teng qiymat qabul qilsa, u holda bu formula bajariluvchi formula deyiladi. I.3.5 - teorema. Mulohazalar algebrasining va formulalari teng kuchli formulalar bO‘lishi uchun, formula aynan rost formula bO‘lishi zarur va etarli. Isbot. bO‘lsin. U holda va formulalarga kirgan barcha propozitsional O‘zgaruvchilarning barcha qiymatlari tizimlarida va formulalar bir xil qiymatlar qabul qiladilar. YA’ni, bO‘ladi. Aksincha, bO‘lsa, bO‘lganda va bO‘lganda bO‘ladi. A A A (kon’yunksiyaning idempotentlik qonuni). A A A (diz’yunksiyaning idempotentlik qonuni). A 1 A . A 1 1. A 0 0 . A 0 A . A A 1 – uchinchisini inkor qilish qonuni. A A 0 - ziddiyatga keltirish qonuni. ( A ) A - qO‘sh inkor qonuni. A ( V A ) A . A ( V A ) A . A V ( A V ) ( V A ). A V A V . ( A V ) A V . ( A V ) A V . A V ( A V ). A V ( A V ). A V V A – kon’yunksiyaning kommutativlik qonuni. A V V A – diz’yunksiyaning kommutativlik qonuni. A ( V S ) ( A V ) ( A S ) - ning ga nisbatan distributivlik qonuni. A ( V S ) ( A V ) ( A S ) - ning ga nisbatan distributivlik qonuni. A ( V S ) ( A V ) S – kon’yunksiyaning assotsiativlik qonuni. A ( V S ) ( A V ) S – diz’yunksiyaning assotsiativlik qonuni. Bu tengkuchliliklar rostlik jadvallari yordamida isbotlanishi mumkin. Masalan, 20 - tengkuchlilikning isboti uchun rostlik jadvali tuzamiz :
Rostlik jadvalidagi oxirgi ikki ustunlar mos qatorlaridagi qiymatlar tengligidan kO‘rinadiki : A ( V S ) ( A V ) ( A S ). Takrorlash uchun savollar : Mulohazalar algebrasining teng kuchli formulalariga ta’rif bering. Mantiq qonuni deb nimaga aytiladi ? Mulohazalar algebrasida ziddiyat deb nimaga aytiladi? Bajariluvchi formula ta’rifini ayting. Mulohazalar algebrasining formulalari teng kuchli bo‘lishining zarur va etarli shartlarini keltiring. Uchinchisini inkor qilish, yutilish, qo‘sh inkor va ziddiyatga keltirish qonunlarini ifodalang. M a sh q l a r : +uyidagi formulalarning aynan rost ekanligini isbotlang : ( A V ) ( A V ) ; ( A V ) (( A ( V S )) ( A S )) ; ( A V ) (( V A ) ( A V )) ; ( A S ) (( A V ) ( S V )) . 2. +uyidagi formulalarning aynan yolg‘on ekanligini isbotlang : A ( V ( A V )) ; ( ( A V ) ( A V )) ; ( A ( V A )) ; ( A S ) (( V S ) ( A V S )) ; 5) ( A V ) (( A S ) ( V A )) . 3. +uyidagi formulalarning qaysilari bajariluvchi ekanligini aniqlang : ( A A ) ; ( A V ) ( V A ) ; ( V ( A S )) (( A S ) V ) ; (( A V ) S ) V ; ( A V ) (( S V ) ( V V )) . 4. .3.6 da keltirilgan tengkuchliliklarni rostlik jadvallari yordamida isbotlang. I.4 - §. Formulalarni teng kuchli almashtirish. Agar bO‘lib, va formulalar tarkibiga kirgan C qism formulani C ga teng kuchli bO‘lgan D formula bilan almashtirsak, yana teng kuchli formulalar hosil bO‘lishi ravshan. Buni qisqacha ( C ) ( C ) , C D ( D ) ( D ) kO‘rinishda ¸zishni kelishib olamiz. I.4.1 – misol. A V A V A V tengkuchlilikni isbotlang. I.3.6 da keltirilgan tengkuchliliklardan foydalanib quyidagi teng kuchli formulalar ketma – ketligini hosil qilamiz : A V ( A V ) ( V A ) ( A V ) ( V A ) ( ( A V ) V ) ( A V ) A ) ( A V ) ( V V ) ( A A ) ( V A ) ( A V ) 0 0 ( V A ) ( A V ) ( V A ). Takrorlash uchun savollar : Mulohazalar algebrasining formulasi, qism formulasi deb nimaga aytiladi ? Teng kuchli formulalar deb qanday formulalarga aytiladi ? Idempotentlik, kommutativlik, assotsiativlik, distributivlik qonunlarini ifodalang. 4. Formulalarni teng kuchli almashtirish deganda nimani tushunasiz ? M a sh q l a r : Teng kuchli almashtirishlar yordamida quyidagi formulalarni soddalashtiring : ( A V ) (( A V ) A ) ; ( A V ) (( A V ) A ) ; ( A V ) ( V A ) ( A V ) ; ( A V ) ( V A ) ( S A ) ; ( A S ) ( A S ) ( V S ) ( A V S ) . 2. Teng kuchli almashtirishlar yordamida quyidagi formulalarni shunday almashtiring-ki, natijada hosil bo‘lgan formulalarda faqat va amallari qatnashsin : ( A V ) ( A S ) ; ( A V ) ( A V ) ; (( A V S ) A ) S ; (( A V ) S ) A ; ( A ( V S )) A . 3. Teng kuchli almashtirishlar yordamida quyidagi formulalarni shunday almashtiring – ki, natijada hosil bo‘lgan formulalarda faqat va amallari qatnashsin : 1) ( A V ) ( V S ) ; 2) ( A V ) ( A V ) ; (( A V ) S ) ( S V ) ; (( A ( V S )) ( V A )) V ; (( A V ) ( V S )) ( A S ) . 4. +uyidagi formulalarning inkorini toping : 1) ( A ( B C )) ( A B ) ; 2) (( A B C ) D ) Q R P ; 3) ((( A ( B C )) D ) Q ) ( R ( P F )) ; 4) (( A ( B ( C D ))) Q ) R . 5. Teng kuchli almashtirishlar yordamida quyidagi formulalarning ziddiyat ekanligini isbotlang : ( A V ) ( V A ) (( A V ) ( A V )) ; (( A V ) ( A ( A V ))) (( V ( A V )) ( A V )) ; (( A V ) ( V S )) ( A S ) ; ( A V ) ( A V ) A ; ( A V ) ( A S )) (( A V ) ( A S )) . I.5.1 -ta’rif . BO‘sh bO‘lmagan M tO‘plam va unda aniqlangan " + " - qO‘shish , " · " – kO‘paytirish, " ¯ " – inkor amallariga nisbatan quyidagi shartlar bajarilgan bO‘lsin : x + u q u + x - qO‘shishga nisbatan kommutativlik qonuni x · u q u · x - kO‘paytirishga nisbatan kommutativlik qonuni. ( x + u ) + z q x + ( y + z ) -qO‘shishga nisbatan assotsiativlik qonuni.. ( x · u ) · z q x · ( y · z ) – kO‘paytirishga nisbatan assotsiativlik qonuni. x + x q x qO‘shishga nisbatan idempotentlik qonuni. x · x q x – kO‘paytirishga nisbatan idempotentlik qonuni. х̿ q x - qO‘sh inkor qonuni. x + u q х̅ · у̅ x · u q х̅ + у̅ - de – Morgan qonunlari. x + ( u · x ) q x x · ( u + x ) q x - yutilish qonunlari. ( x + u ) · z q ( x · z ) + ( y · z ) -qO‘shishning kO‘paytirishga nisbatan distributivlik qonuni. ( x · y ) + z q ( x + z ) · ( y + z ) –kO‘paytirishning qO‘shishga nisbatan distributivlik qonuni u holda < M ; + , · , ¯ > - algebra Bul algebrasi deyiladi. I.5.2 - Misollar. 1. I.3.6 dagi tengkuchliliklardan kO‘rinadiki, mulohazalar algebrasida kon’yunksiyani " · ", diz’yunksiyani " + " ga mos qO‘ysak, mulohazalar algebrasi Bul algebrasiga misol bO‘la oladi. 2. TO‘plamlar algebrasi, unda aniqlangan "ìü " - tO‘plamlar kesishmasi, "îþ" – tO‘plamlar birlashmasi , " ' " – tO‘plam tO‘ldiruvchisi amallari I.5.1 dagi xossalarga ega ekanligidan uning Bul algebrasini tashkil etishini kO‘rish mumkin. I.5.3 - ta’rif. X q { 0 , 1 } –ikki elementli tO‘plam berilgan bO‘lsin. U holda f : Xn X ( n 0, 1, 2, . . . ) - funksiya n – O‘zgaruvchili Bul funksiyasi yoki 2 - qiymatli funksiya deyiladi. n0, bO‘lganda, X tO‘plamning ajratilgan elementlarini, ya’ni 0 yoki 1 ni hosil qilamiz. Mulohazalar algebrasining ihtiyoriy formulasi ikki qiymatli funksiyaga misol bO‘la oladi. Masalan, A V –formulani qaraylik.
Demak , f ( x,u ) q x u – Bul funksiyasi ekan. Umuman, ( A 1 , . . . , A n ) – formula n – O‘zgaruvchili Bul funksiyasidir. Endi teskari masalani kO‘raylik. Ixtiyoriy F ( X1, . . . , Xn ) – Bul funksiyasi berilgan bO‘lsin. Bu funksiyani mulohazalar algebrasining formulasi orqali ifodalash mumkinligini kO‘ramiz : F ( 1, 1, . . . , 1 ) X1 X2 . . . Xn F ( 1, . . . , 1,0 ) X1 . . . Xn-1 Xn . . . F ( 0 , 0 , . . . ,0 ) X1 . . . Xn (1) – formula mulohazalar algebrasining F ( X1, . . . , Xn) – Bul funksiyasiga teng bO‘lgan formuladir. Bu tasdiqni ( X1, . . . , X n) – propozitsional O‘zgaruvchilar tizimiga (1 , . . . , 1), ( 1, . . . , 1, 0 ) , . . . , ( 0, . . . , 0 ) qiymatlar tizimini qO‘yib tekshirib chiqish mumkin. ( 1, . . . , 1, 0 ) - qiymatlar tizimi uchun tenglikni tekshiraylik. I.3.6 dagi tengkuchliliklarga asosan : F ( 1, 1, . . . , 1 ) 1 . . . 0 F ( 1, . . . ,1, 0 ) 1 1 . . . 0 . . . F ( 0, . . . , 0 ) 1 1 . . . 0 F ( 1, . . . , 1 ) 0 F ( 1, . . . ,1, 0 ) 1 1 . . . 1 . . . F ( 0, . . . , 0 ) 0 0 F ( 1, . . . , 1, 0 ) . . . 0 F ( 1, 1, . . . , 0 ) . Agar (1) formulada 0 ga teng bO‘lgan qO‘shiluvchilarni, ya’ni birinchi O‘paytuvchisi 0 ga teng kon’yunksiyalarni va birinchi kO‘paytuvchisi 1 ga teng kon’yunksiyalarda 1 A A tengkuchlilikdan foydalanib 1 ni tashlab yozsak, (1) formulaning kO‘rinishi ancha soddalashadi. SHunday qilib, (1) ni faqat propozitsional O‘zgaruvchilardan tuzilgan va quyidagi shartlarni qanoatlantiradigan formula shaklida yozish mumkin : Formuladagi har bir qO‘shiluvchida F ( X1, . . . , Xn ) funksiyaga kirgan barcha X1, . . . , Xn O‘zgaruvchilar qatnashadi. Formulada bir hil qO‘shiluvchilar yO‘q. 3. Har bir qO‘shiluvchida X1, . . . , Xn O‘zgaruvchilar faqat bir martagina qatnashadi. Agar F ( X1, . . . , Xn ) funksiyaning rostlik jadvali berilgan bO‘lsa, uni mulohazalar algebrasining formulasi orqali ifoda qilish uchun X1, . . . , Xn o‘zgaruvchilarning F ( X1, . . . , Xn ) funksiya 1 ga teng qiymat qabul qiladigan qiymatlari tizimlarinigina ajratib olamiz. Bunday qiymatlar tizimi uchun Xk O‘zgaruvchi 1 ga teng qiymat qabul qilsa, Xk ni O‘zini, aks holda Xk ning inkorini olib X1, . . . , Xk O‘zgaruvchilardan kon’yunksiyalar tuzib olamiz. Hosil bO‘lgan barcha kon’yunksiyalarning yig‘indisi F ( X1, . . . , Xn ) formulaning ifodasi bO‘ladi. I.5.4 – misol. F ( X1, X2, X3 ) – ikki qiymatli fuksiya faqatgina ( 1, 1, 0 ) va ( 0, 1, 1 ) qiymatlar tizimlaridagina 1 ga teng qiymat qabul qilsin. F ( X1, . . . , Xn ) ni mulohazalar algebrasining formulasi orqali ifodalaylik. Echim. X1, X2, X3 – O‘zgaruvchilarning ( 1, 1, 0 ) qiymatlari tizimiga X1 X2 X3 – kon’yunksiya, ( 0, 1, 1 ) ga esa X1 X2 X3 - kon’yunksiya mos keladi. U holda, F ( X1, X2, X3 ) q X1 X2 X3 X1 X2 X3 . I.5.5 - natija . F ( X1, . . . ,Xn )– ikki qiymatli funksiya berilgan bO‘lsin. U holda, F ( X1, . . . , Xn ) ( F ( 1, . . . , 1 ) X1 , . . . , Xn ) F ( 1, . . . , 1, 0 ) X1 , , . . . , Xn-1 Xn ) . . . ( F ( 0, 0, . . . , 0 ) X1 . . . Xn ). Isbot. Haqiqatdan ham, yuqorida F ( X1, . . . , Xn ) funksiya uchun hosil qilingan ifodaga asosan : F ( X1, . . . , Xn ) ( F ( 1, . . . , 1 ) X1 . . . Xn ) ( F ( 1, . . . , 1, 0 ) X1 . . . Xn-1 Xn ) . . . ( F ( 0, . . . , 0 ) X1 . . . Xn ). +O‘sh inkor va de-Morgan qonunlariga kO‘ra F ( X1, . . . , Xn ) ( F ( X1, . . . ,Xn)) ( F ( 1, . . . ,1 ) X1 . . . Xn) ( F ( 1, . . . , 1, 0 ) X1 . . . Xn-1 Xn ) . . . ( F ( 0, . . . , 0 ) X1 . . . Xn ) ( F ( 1, . . . , 1 ) X1 . . . Xn ) ( F ( 1, . . . ,1, 0 ) X1 . . . Xn-1 Xn ) . . . (F ( 0, . . . , 0 ) X1 . . . Xn ). Takrorlash uchun savollar : Algebra deb nimaga aytiladi ? Bul algebrasi ta’rifini keltiring va unga misollar keltiring. 2 qiymatli funksiya nima ? 2 qiymatli funksiya orqali mulohazalar algebrasining formulasini ifodalash mumkin – mi ? M a sh q l a r : Faqatgina quyidagi tizimlarda 1 qiymat qabul qiladigan F ( X1, . . . , Xn ) ni mulohazalar algebrasining formulasi orqali ifodalang : ( 0 , 0 ) ; ( 0 , 1 ) ; ( 1 , 1 ) ; ( 0 , 1 , 1 ) ; ( 1 , 0 , 0 ) ; ( 1 , 0 , 1 , 1 ) ; ( 0 , 1 , 1 , 1 ) . Berilgan shartlarni qanoatlantiruvchi formulalarni aniqlang : F ( 0, 0 ) F ( 1, 1 ) 1 ; F ( 0, 1, 0 ) F ( 1, 0, 1 ) F ( 1, 1, 1 ) 1 ; F ( 0, 1, 1 ) F ( 1, 0, 0 ) 1 ; F ( 0, 1, 0, 1 ) F ( 1, 0, 1, 0 ) F ( 1, 0, 0, 0 ) F ( 1, 1, 1, 0 ) F ( 1, 1, 1, 1 ) 1. Faqatgina quyidagi tizimlarda 0 qiymat qabul qiladigan F ( X1, . . . , Xn ) ni mulohazalar algebrasining formulasi orqali ifodalang : ( 0, 0 ) ; ( 1, 0 ) ; ( 1, 1 ) ; ( 0, 1, 1 ) ; ( 1, 0, 1 ) ; ( 0, 0, 1 ) ; ( 1, 0, 0, 1) ; ( 0, 1, 0, 0 ) . 4. Berilgan shartlarni qanoatlantiruvchi formulalarni aniqlang : 1) F ( 0, 1 ) F ( 1, 1 ) 0 ; 2) F ( 1, 0, 0 ) F ( 1, 0, 1 ) 0 ; 3) F ( 1, 1, 1 ) F ( 0, 0, 1 ) F ( 1, 1, 0 ) F ( 1, 0, 0 ) 0; 4) F ( 1, 1, 0, 1 ) F ( 0, 0, 1, 0 ) F ( 1, 0, 1, 0 ) F ( 0, 0, 1, 1 ) 0 . I.6.1 - ta’rif. Mulohazalar algebrasining formulasida faqat , , mantiq amallari qatnashib, faqat propozitsional O‘zgaruvchilarga tegishli bO‘lsa, u holda keltirilgan formula ( forma ) deyiladi. I.6.2 – lemma . Agar mulohazalar algebrasining formulasi keltirilgan formula bO‘lsa, u holda mulohazalar algebrasining formulaga teng kuchli keltirilgan formulasi mavjud. Isbot. Formula rangi bO‘yicha matematik induksiya metodini qO‘llaymiz. Formula rangi 0 ga teng bO‘lsa, formula propozitsional O‘zgaruvchidan iborat bO‘lib, isbot ravshan. Rangi k ( k 1 ) dan kichik formulalar uchun teorema tasdig‘i tO‘g‘ri bO‘lsin deb faraz qilamiz. - rangi k ga teng formula bO‘lsin. Formula ta’rifiga kO‘ra -keltirilgan formula yoki kO‘rinishda bO‘ladi. U holda, formula yoki formulalardan biriga teng kuchli bO‘ladi. va formulalarning rangi k dan kichik bO‘lganligi uchun, va larga mos ravishda teng kuchli bO‘lgan keltirilgan va formulalar mavjud. Demak, formula yoki keltirilgan formalardan biriga teng kuchli buladi. Download 387.15 Kb. Do'stlaringiz bilan baham: 
|