Mavzu. Mulohazalar algebrasi. Mulohaza ustida amallar. Asosiy chinlik jadvallari. Mulohazalar algebrasi formulalari. Teng kuchli formulalar
Download 229 Kb.
|
1-amaliy mashulot (2) (1)
- Bu sahifa navigatsiya:
- 10-misol.
- 11- misol .
- 13- misol .
|
Mavzuga oid topshiriqlar:
Berilgan mulohazalarning rostlik jadvalini to’ldiring: 1) ( (Х Y) (Х Y)) 2) (Х Y) ( Y Х) 3) (Х (Y Х) Z) 4) X (X Y) Z 5) ((X Y) Y) (Z Y) 6) (X Y) ( Y Z) 7) (XZ)(XYZ) 8) (X Z) (Y Z) 9) (X(YZ))(XY) 10) (XY) (X Z) Fоrmulаning turini аniqlаng : ( (Х U) (Х U)). (Х U) (U Х). (Х (U Х) Z). X (XY) Z. ((X Y) Y) (Z Y). ((X Y) ( Y Z)) (X Y). (X Z) ((Y Z) (X Y Z)). (X Y) ((X Z) (Y Z)). (X (Y Z)) ((X Y) (X Z)). (X Y) ((X Z) ( Y Z)). (X Y) Z X (Y Z). (X Y) Z (X Z) Y. (X Y) X Y. (X Y) Y X. (X Y) (X Z Y Z). (X Y) ( (X Y) (Y X)). (X Y) (Z Z X Z). (X Y) (X Y) (Y X). (X Y) ( Z X) Y Z. ( X Z) Y ) (X Z ) Z . X Z Y X Z . YYXZX . XZYXYX. Bеrilgаn fоrmulаlаr tеngkuchi ekаnligini isbоtlаng: (XY) (XY) X. X(XY Z) (X Y Z) (X Y Z) (X Y Z). X (Y Z) Z Y Z. X Y Y X. X Y X Y X YX Y. X Y X Y. X ( X Y) X Y. X (X Y) X Y. ( X Y) (X Y) XX Y. (X Y) (X Y) X Y. (X Y) (Y Z) (Z X) X Z. (XY(Z Y Y X)(X (X (X X))) YXY. X (X X Y Y) Z) X (Y Z) (Y Z) 1. (X(YZY Z)) (Y X Y) X (Y (X X)) X Y. (X Y) (Y Z) (X Z) 1. (X Z) (X Z) (Y Z) ( X Y Z) X Y Z. (X Y X Y) Y Y. X (Y Z) (X Y) (X Z) . (X (Y Z )) X ( X Y ) ( X Z ) . X Y ( X Y ) ( X Y ) ( X Y ) . (( X Y Z ) X ) Z ( X Y Z ) . ( X ( Y Z )) Z (( X ( Y Z )) Z ) . X Y Z (( X Y ) Z ) ( X Z ) . Formulalarning turini topishga doir misollar yechish 1. А BА C fоrmulаning turini аniqlаng. Yechish. Bеrilgаn fоrmulаdа uchtаА, V, S mulоhаzаlаr qаtnаshgаnligi sаbаbli, ulаrning qiymаtlаr tizimlаri 23 = 8 tа bo’lаdi. Fоrmulаning rоstlik jаdvаligа 8 tа tizimni tаrtib bilаn jоylаshtirаmiz. Mаntiq аmаllаrining bаjаrilish tаrtibigа ko’rа аvvаl АB kоn’yunksiyani, kеyin АC diz’yunksiyani vа nihоyat hоsil qilingаn fоrmulаlаrning implikаsiyasini bаjаrаmiz. Ya’ni аmаllаrning tа’riflаrigа ko’rа mоs ustunlаrni to’ldirаmiz. Nаtijаdа quyidаgi rоstlik jаdvаli hоsil bo’lаdi:
Fоrmulаning rоstlik jаdvаlidаgi охirgi ustun – fоrmulаning rоstlik qiymаtlаr ustuni fаqаt rоst qiymаtlаrdаn ibоrаt bo’lgаnligi uchun bеrilgаn fоrmulа аynаn rоst (tаvtоlоgiya, mаntiq qоnuni) dеgаn хulоsаgа kеlаmiz. Mulohazalar algebrasi formulalarini normal shaklga keltirishga doir misollar yechish. 1-misol. Distributivlik va idempotentlik qonunlariga asoslanib, formulaning kon’yunktiv normal shakllari, masalan, , va formulalar, formula uchun esa diz’yunktiv normal shakllar, masalan, va formulalar bo‘lishiga ishonch hosil qilish qiyin emas. 2-misol. Ushbu formulaning biror KNShini topish talab etilgan bo‘lsin. Berilgan formulani bilan belgilab (1) va (2) formulalardan foydalansak, quyidagilarga ega bo‘lamiz: . Demak, . Berilgan formulaning topilgan KNShida va o‘zgaruvchilarning bittagina elementar diz’yunksiyasi bor, ya’ni berilgan formula uchun KNSh bittagina diz’yunktiv haddan iboratdir. 3-misol. formulani KNShga keltirish maqsadida 2- misoldagidek ish yuritib teng kuchliliklarga ega bo‘lamiz. Shunday qilib, formula berilgan formula uchun KNSh bo‘lib, u ikkita va diz’yunktiv hadlarning kon’yunksiyasidan iboratdir. ■ 4-misol. 2- teoremadan foydalanib va formulalarning tavtologiya bo‘lishi yoki bo‘lmasligini tekshiramiz. Berilgan formulalarni, mos ravishda, va bilan belgilab, (1) va (2) formulalardan foydalansak, quyidagi KNShlarga ega bo‘lamiz: , . Bu formulalarning KNShlarida kamida bittadan elementar mulohaza o‘zining inkori bilan birga qatnashgani uchun berilgan formulalarning har biri tavtologiyadir. ■ 5- misol. Berilgan formulaning doimo yolg‘on formula bo‘lishini ko‘rsatamiz. Haqiqatdan ham, formula DNShda yozilgan bo‘lib, uning tarkibidagi 1- elementar kon’yunksiya ifodasida , 2- ifodasida , 3-sida esa va elementar mulohazalar o‘zlarining inkorlari bilan birgalikda qatnashganlari uchun, yolg‘onlik alomatiga asosan, . ■ 6-misol. Berilgan va elementar diz’yunksiyalar to‘g‘ri elementar diz’yunksiyalar, va elementar kon’yunksiyalar esa to‘g‘ri elementar kon’yunksiyalardir. Lekin, va elementar diz’yunksiyalar ifodasida elementar mulohaza bir martadan ortiq qatnashganligi sababli, ularning hech biri to‘g‘ri elementar diz’yunksiya bo‘la olmaydi. elementar mulohaza va elementar kon’yunksiyalar tarkibida bir martadan ortiq qatnashganligi sababli, bu ifodalarning hech qaysisi to‘g‘ri elementar kon’yunksiya bo‘la olmaydi. ■ 7-misol. Ushbu , va elementar kon’yunksiyalarning hech qaysi biri elementar mulohazalarga nisbatan to‘liq elementar kon’yunksiya emas, lekin ularning birinchisi elementar mulohazalarga nisbatan, oxirgisi esa elementar mulohazalarga nisbatan to‘liq elementar kon’yunksiyadir. Berilgan elementar diz’yunksiya elementar mulohazalarga nisbatan to‘liq elementar diz’yunksiyadir, elementar diz’yunksiya esa elementar mulohazalarga nisbatan to‘liq elementar diz’yunksiya bo‘lsada, u elementar mulohazalarga nisbatan to‘liq elementar diz’yunksiya bo‘la olmaydi. ■ 8-misol. Formulani MKNShga keltirish algoritmidan foydalanib , , va elementar mulohazalarning formulasini MKNShga keltiramiz. Dastlab, algoritmning 1- bandiga ko‘ra, berilgan formulani KNShga keltiramiz. Buning uchun, avvalo, va teng kuchliliklardan foydalanib formulani faqat kon’yunksiya, diz’yunksiya va inkor mantiqiy amallari orqali ifodalaymiz: . Hosil bo‘lgan formulaga teng kuchlilikni qo‘llasak, formula KNShga keladi. KNSh ifodasida barcha elementar diz’yunksiyalar turlicha bo‘lganligi sababli algoritmning 2- bandini bajarishga hojat yo‘q. KNSh ifodasidagi 1- va 2- elementar diz’yunksiyalar to‘g‘ri elementar diz’yunksiyalar bo‘lmaganligi uchun algoritmning 3- banda ifodalangan jarayonlarni bajarishga o‘tamiz. KNSh ifodasidagi hech qaysi elementar diz’yunksiya ifodasida birorta ham o‘zgaruvchi o‘zining inkori bilan birgalikda qatnashmaganligi sababli 3- banddagi a) hol bu yerda ro‘y bermaydi. KNSh ifodasidagi 1- elementar diz’yunksiyada , 2- elementar diz’yunksiyada esa ikki marta qatnashgani uchun b) holda bayon qilingandek ish yuritib, formula uchun barcha elementar diz’yunksiyalari to‘g‘ri elementar diz’yunksiyalardan iborat KNShni hosil qilamiz. Ushbu bobning 5- paragrafidagi 2- teoremaga asosan, formula tavtologiya emas. Algoritmning 4- bandini bajaramiz. Ko‘rinib turibdiki, KNShdagi 1- elementar diz’yunksiyada , va , 2- elementar diz’yunksiyada , va , 3- va 4- elementar diz’yunksiyalarda esa va o‘zgaruvchilar yoki ularning inkorlari yo‘q. Shularni e’tiborga olib, KNSh ifodasidagi to‘rtala elementar diz’yunksiyalarni to‘liq elementar diz’yunksiyalar shakliga keltirish maqsadida 4- bandda ifodalangan jarayonni qo‘llaymiz. Natijada 1- elementar diz’yunksiya () uchun , 2- elementar diz’yunksiya () uchun1 , 3- elementar diz’yunksiya () uchun va 4- elementar diz’yunksiya () uchun teng kuchliliklarga ega bo‘lamiz. Topilgan barcha KNShlar , , va elementar mulohazalarga nisbatan to‘liq KNShlardir. Bu KNShlarni o‘zaro solishtirib, ularning tarkibida bir xil elementar diz’yunksiyalar bor (masalan, 1- va 2- KNShlardagi elementar diz’yunksiya) bo‘lgan vaziyat ro‘y berganligini aniqlaymiz. Shuning uchun, algoritmning 5- bandi boshqarishni uning 2- bandiga o‘tkazadi. Algoritmning 2- bandini bajarib, formula uchun KNSh ifodasiga ega bo‘lamiz. Algoritmning 3- bandi boshqarishni uning 4- bandiga, 4- bandi esa 6- bandiga o‘tkazadi, chunki oxirgi KNSh ifodasidagi barcha elementar diz’yunksiyalar to‘g‘ri va to‘liq elementar diz’yunksiyalardir. Sunday qilib, berilgan formula uchun oxirgi formula MKNShdir. ■ 9-misol. 2- teoremadan foydalanib, 4- misolda MKNShi topilgan formulani MDNShga keltiramiz. Ushbu bobning 5- paragrafidagi 4- teoremaga asoslanib, berilgan formulaning doimo yolg‘on emasligiga ishonch hosil qilish qiyin emas. Avvalo mantiqiy formulani MKNShga keltirish algoritmidan foydalanib formulani MKNShga keltiramiz: . formulaning topilgan MKNShi tarkibida qatnashgan barcha belgilar o‘rniga belgi va, aksincha, o‘rniga hamda , va elementar mulohazalar o‘rinlariga mos ravishda , va , shunga o‘xshash, , va inkorlar o‘rinlariga mos ravishda , , va qo‘yilsa, u holda formulaning MDNShi hosil bo‘ladi. ■ 10-misol. Ushbu formula va elementar mulohazalarga nisbatan MKNShda bo‘lsada, u to‘liq MKNShda emas. va elementar mulohazalarga nisbatan to‘liq MKNShi ifodasi ko‘rinishga ega. MDNShdagi formula , va elementar mulohazalarga nisbatan to‘liq MDNShda emas, lekin formula bu elementar mulohazalarga nisbatan to‘liq MDNShdagi formuladir. ■ 11- misol. Mulohazalar algebrasining asosiy elementar funksiyalariga ikki taraflama bo‘lgan funksiyalarni topamiz (1- jadvalga qarang). Demak, ta’rifga asosan, va funksiyalar o‘z-o‘ziga ikki taraflama funksiya bo‘ladi. ■ 12- misol. funksiyaning o‘z-o‘ziga ikki taraflama funksiya ekanligini isbot qilamiz. Haqiqatdan ham Demak, ekanligi uchun o‘z-o‘ziga ikki taraflama funksiyadir. ■ 13- misol. Ushbu bobning 9- paragrafida keltirilgan (2), (3), (6), (8), (10), (12) teng kuchli formulalarga ushbu prinsipni qo‘llasak, (4), (5), (7), (9), (11), (13) teng kuchli formulalar kelib chiqadi. ■ F={} funksiyalarni o’z-o’ziga qo’shmaligini tekshirish uchun funksiyalarning chinlik jadvalini tuzamiz
Chinlik jadvali yordamida funksiyalarning S-o’z-o’ziga qo’shma funksiyalar sinfiga kirishini tekshiramiz. Buning uchun chinlik jadvalida funksiyalarni qiymatlari satrini chiziq bilan o’rtasidan ajratib, shu chiziqqa nisbatan qiymatlarning simmetrikligini tekshiramiz Jadvaldan ko’rinib turibdiki va funksiyalar o’z-o’ziga qo’shma emas, chunki funksiyalarning chinlik to’plami simmetrik emas. 1 Bu yerda va keyingi elementar diz’yunksiyalar uchun oralik teng kuchliliklarni tushirib qoldirdik. Download 229 Kb. Do'stlaringiz bilan baham: 
|