Muxammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti samarqand filiali

MUXAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI

Kafedra: “TTKT ” FAKULTETI
“AXBOROT XAVFSIZLIGI” KAFEDRASI

“DISKRET TUZILMALAR’’ fanidan

MUSTAQIL ISH 2

Bajardi: Nabiyev G’

Qabul qildi: Saidov O’

Chinlik to‘plami tushunchasining qo‘llanilishi

Formulaning chinlik to‘plami tushunchasi. Ma’lumki, berilgan n ta o‘zgaruvchi elementar mulohazalar uchun barcha bir-biridan farqli mumkin bo‘lgan qiymatlar satrlari kombinatsiyalari n 2 ta . Tarkibida n ta o‘zgaruvchilar ishtirok etgan formula shu n 2 ta qiymatlar satrlarining bir qismida 1, qolgan qismida esa 0 qiymatni qabul qiladi.
1- t a ’ r i f. Berilgan formula tarkibidagi elementar mulohazalarning qiymatlaridan qandaydir tartibda tuzilgan va shu formulaning 1 qiymatiga mos keluvchi barcha kortejlar to‘plami formulaning chinlik to‘plami deb ataladi. Ravshanki, tarkibidagi o‘zgaruvchilarning soni qanday bo‘lishidan qat’iy nazar, aynan yolg‘on formulaning chinlik to‘plami bo‘sh () to‘plamdan iboratdir. n ta elementar mulohazalarning mumkin bo‘lgan barcha n 2 2 ta teng kuchlimas formulalaridan C n n 2 1  2 tasi qiymatlar satridagi n ta qiymatlardan faqat bittasi 1, qolgan ( n 1)tasi esa 0 bo‘lganda 1 qiymat qabul qiladi. Shuning uchun, bunday formulalarning har biri bir elementli chinlik to‘plamiga ega. Xuddi shuningdek, n ta elementar mulohazalarning mumkin bo‘lgan barcha teng kuchlimas formulalaridan C n 2 2 tasi qiymatlar satridagi n ta qiymatlardan faqat ikkitasi 1, qolgan ( n  2 )tasi esa 0 bo‘lganda 1 qiymat qabul qiladi. Shu sababli, bunday formulalarning har biri uchun chinlik to‘plam ikkita kortejdan tashkil topgan bo‘ladi. Shu usulda davom etsak, n 2 2 ta teng kuchlimas formulalardan C n 2 3 tasining har biri uch elementli chinlik to‘plamiga, 4 2 C n tasining har biri to‘rt elementli chinlik to‘plamiga, va hokazo, n n C n 2 2 1 2   tasining har biri ( 2 1 n ) elementli chinlik to‘plamiga, bitta ( 1 2 2  n C n ) formula esa n 2 ta elementli chinlik to‘plamiga egaligiga ishonch hosil qilamiz. Tarkibida n ta elementar mulohazalar ishtirok etgan aynan chin formulaga mos chinlik to‘plamni universal to‘plam (U ) deb olsak, tarkibida shu elementar mulohazalar qatnashgan mumkin bo‘lgan barcha formulalarning har biriga mos chinlik to‘plamlar U to‘plamning qism to‘plamlaridan iborat va bu U universal to‘plam qismlari soni n n n n C n C n C n C n C 2 2 2 2 1 2 2 2 1 2 0 2   ......   2  bo‘ladi. Shunday qilib, tarkibida n ta elementar mulohazalar ishtirok etgan mumkin bo‘lgan barcha formulalar bilan ularning chinlik to‘plamlari orasida o‘zaro bir qiymatli moslik o‘rnatildi. Demak, barcha o‘zaro teng kuchli formulalarga faqat bitta chinlik to‘plami mos keladi. 1- m i s o l . Ikkita ( n  2 ) x va y elementar mulohazalarning x  (x  y)  y formulasi aynan chindir). Shuning uchun berilgan formulaning chinlik to‘plami 2 2 4 2   n elementli {(0,0),(0,1),(1,0),(1,1)} universal to‘plamdan iboratdir. ■ 2- m i s o l . Tarkibida uchta x , y va z elementar mulohazalar qatnashgan xyz formula qiymatlar satrlarining faqat bittasida (aniqrog‘i, 1,0,1 satrda) 1 qiymat, qolgan ettitasida esa 0 qiymat qabul qiladi. Shuning uchun, xyz formulaning chinlik to‘plami {(1,0,1)}, ya’ni bitta (1,0,1) kortejdan tashkil topgan bo‘ladi. ■ 3- m i s o l . Ushbu xyz  xyz  xyz formula tarkibida uchta kortej bo‘lgan {(1,1,1),(0,1,0),(1,0,1)} chinlik to‘plamiga egadir. ■ Agar qandaydir A formula P chinlik to‘plamiga ega bo‘lsa, u holda “ A formula P to‘plamda chin qiymat qabul qiladi” (yoki, qisqacha, “ A formula P to‘plamda chin”) deb ham yuritiladi. Shunga o‘xshash, “ A formula P to‘plamda yolg‘on” deyish mumkin, bu yerda P  U \ P , ya’ni P to‘plamning to‘ldiruvchisi. Agar A formula P to‘plamda chin bo‘lsa, u holda A formula P to‘plamda chin, P to‘plamda esa yolg‘on bo‘ladi. Xuddi shu kabi, aynan chin J formula U universal to‘plamda chin va U   to‘plamda yolg‘on qiymat qabul qiladi. Aynan yolg‘on J formula esa, aksincha,  to‘plamda chin va   U to‘plamda yolg‘ondir. Formulalar bilan chinlik to‘plamlari orasidagi yuqorida ifodalangan bog‘lanish mulohazalar mantiqiga oid masalani to‘plamlar nazariyasi masalasiga va, aksincha, to‘plamlar nazariyasidagi masalani mulohazalar mantiqiga doir masalaga ko‘chirish imkoniyatini beradi. Asosiy mantiqiy amallarning chinlik to‘plamlari. Chinlik to‘plamlari mos ravishda A va B bo‘lgan P va Q formulalar berilgan bo‘lsin. Kon’yunksiyaning chinlik to‘plami. P va Q formulalar P  Q kon’yunksiyasining chinlik to‘plami A B bo‘ladi. Haqiqatdan ham, kon’yunksiya ta’rifiga asosan, P Q formula P va Q formulalarning ikkalasi ham chin bo‘lgandagina chindir. Shuning uchun, P Q formulaning chinlik to‘plami A va B to‘plamlarning umumiy elementlaridan tuzilgan A B kesishmasidan iborat bo‘ladi. Demak, mulohazalar mantiqidagi kon’yunksiya amaliga (  belgiga) to‘plamlar nazariyasidagi kesishma amali. 4- m i s o l . Cxyz va D xyzxyzxyz formulalarning chinlik to‘plamlari, mos ravishda, R {(1,0,1)} va S  {(1,1,1),(0,1,0),(1,0,1)} bo‘lgani uchun (2- va 3- misollarga qarang) C  D kon’yunksiyaning chinlik to‘plami R S {(1,0,1)} bo‘ladi.
■ Diz’yunksiyaning chinlik to‘plami. P va Q formulalar P Q diz’yunksiyasining chinlik to‘plami A B bo‘ladi. Haqiqatdan ham, diz’yunksiya ta’rifiga asosan, P Q formula P va Q formulalarning kamida bittasi chin bo‘lgandagina chindir. Demak, A B to‘plamda P Q formula chindir. Shunday qilib, P Q formulaning chinlik to‘plami A va B to‘plamlarning barcha elementlaridan, ularni takrorlamasdan, tuzilgan A B birlashmasidan iborat bo‘ladi. Demak, mulohazalar mantiqidagi diz’yunksiya ( ) amaliga to‘plamlar nazariyasidagi birlashma (  ) amali mos keladi. 5- m i s o l . 4- misolda aniqlangan C va D formulalar diz’yunksiyasi C  D uchun chinlik to‘plam R S {(1,1,1),(0,1,0),(1,0,1)} bo‘ladi.
■ Implikasiyaning chinlik to‘plami. P va Q formulalar P  Q implikasiyaning chinlik to‘plamini topamiz. P formulaning chinlik to‘plami A va Q formulaning chinlik to‘plami B bo‘lgani uchun, P  Q  P  Q teng kuchlilikka ko‘ra, P  Q formulaning chinlik to‘plami A B bo‘ladi. 1- shaklda tasvirlangan U to‘plamning bo‘yalmagan qismi P  Q implikasiyaning chinlik to‘plamiga mos keladi. 6- m i s o l . 4- misolda aniqlangan C va D formulalar tarkibida uchtadan x , y va z elementar mulohazalar qatnashgani uchun, C  D implikasiyasining chinlik to‘plamini topish maqsadida, dastlab U {(1,1,1),(1,1,0),(1,0,1),(1,0,0),(0,1,1),(0,1,0),(0,0,1),(0,0,0)} 1- shakl U universal to‘plamni tuzamiz. C formulaning chinlik to‘plami R {(1,0,1)} bo‘lgani uchun C formulaning chinlik to‘plami R  U \ R  {(1,1,1),(1,1,0),(1,0,0),(0,1,1),(0,1,0),(0,0,1),(0,0,0)} bo‘ladi. Endi R to‘plam bilan B formulaning S  {(1,1,1),(0,1,0),(1,0,1)} chinlik to‘plami birlashmasini aniqlasak, R  S  U , ya’ni C  D formulaning chinlik to‘plami universal to‘plamdan iborat bo‘ladi. Bu yerdan CD xyz(xyzxyzxyz)  J xulosani hosil qilamiz.
■ Ekvivalensiyaning chinlik to‘plami. P va Q formulalar P  Q ekvivalensiyasining chinlik to‘plamini aniqlash uchun P  Q  (P  Q)  (P  Q ) teng kuchlilikdan foydalanamiz. Yuqorida qilingan xulosalarga ko‘ra P  Q formulaning chinlik to‘plami (A B)(A B) bo‘ladi. 2- shaklda tasvirlangan U to‘plamning bo‘yalmagan qismi P  Q ekvivalensiyaning chinlik to‘plamiga mos keladi. 7- m i s o l . 4- misolda aniqlangan C va D formulalar C  D ekvivalensiyasining chinlik to‘plamini topamiz. 6- misolda R  S  U bo‘lishi aniqlangan edi. R {(1,0,1)} va S {(1,1,0),(1,0,0),(0,1,1),(0,0,1),(0,0,0)} to‘plamlar yordamida R S {(1,1,0),(1,0,1),(1,0,0),(0,1,1),(0,0,1),(0,0,0)} to‘plamni topamiz. Demak, {(1,1,0),(1,0,1),(1,0,0),(0,1,1),(0,0,1),(0,0,0)} to‘plam C  D ekvivalensiyasining chinlik to‘plamidir.
■ Chinlik to‘plami tushunchasining qo‘llanilishi. Chinlik to‘plami tushunchasidan foydalanib mulohazalar algebrasi bilan matematikaning boshqa sohalari, jumladan, to‘plamlar algebrasi orasidagi bog‘lanishlarni ifodalash mumkin. Mulohazalar algebrasidagi  (kon’yunksiya),  (diz’yunksiya) va  (inkor) mantiqiy amallarga, mos ravishda, to‘plamlar algebrasidagi  (kesishma),  (birlashma) va (to‘ldirish) amallari to‘g‘ri keladi. Mulohazalar algebrasidagi 1 va 0 o‘zgarmaslarga (konstantalarga) to‘plamlar algebrasidagi U va  (universal va bo‘sh) to‘plamlar mos keladi. Demak, mulohazalar algebrasidagi biror ifodada (tasdiqda)  belgisini  belgisiga,  ni  ga, inkor belgisini to‘ldiruvchi belgisiga, 1ni U ga, 0ni ga (  ni  ga) almashtirsak, to‘plamlar algebrasidagi ifoda (tasdiq) hosil bo‘ladi va, aksincha almashtirishlar bajarsak, to‘plamlar algebrasidagi ifodadan (tasdiqdan) mulohazalar algebrasidagi ifoda (tasdiq) hosil bo‘ladi. 6- misolda chinlik to‘plami tushunchasidan foydalanib xyz (xyzxyzxyz)  J teng kuchlilik o‘rinli bo‘lishi ko‘rsatilgan edi. Yuqoridagi xulosalar asosida, mulohazalar algebrasining to‘plam algebrasidagiga o‘xshash tasdiqlarini keltirib chiqarish mumkin. Bunday o‘xshashliklarning ayrimlarini keltiramiz. 8- m i s o l . A va B formulalar uchun A A  B  J teng kuchlilikning o‘rinli bo‘lishini ularga mos P va Q chinlik to‘plamlaridan foydalanib isbotlaymiz. A A  B formulaning chinlik to‘plami P P Q  U Q  U . Shu sababli, A A B tavtologiyadir.
1 - t e o r e m a . Agar chinlik to‘plamlari mos ravishda P va Q bo‘lgan A va B formulalar uchun A  B  J teng kuchlilik o‘rinli bo‘lsa, u holda P  Q bo‘ladi. I s b o t i . Ma’lumki, A  B formulaning chinlik to‘plami U universal to‘plamning P  Q qism to‘plamidan iborat. P Q  P \ Q (I bobninig bo‘lgani 2- shakl U uchun A  B  J shartga ko‘ra P \ Q  U bo‘lishi kerak. Bundan P \ Q  U yoki P \ Q   kelib chiqadi. Bu esa P  Q ekanligini bildiradi. Demak, A  B tavtologiya bo‘lishi uchun A formulaning chinlik to‘plami B formula chinlik to‘plamining qism to‘plami bo‘lishi shart. ■
2 - t e o r e m a . A va B formulalar teng kuchli bo‘lishi uchun A  B formula tavtologiya bo‘lishi zarur va yetarli. I s b o t i . A va B formulalarning chinlik to‘plamlari, mos ravishda, P va Q bo‘lsin. a) A va B formulalar teng kuchli, ya’ni A  B bo‘lsin. U holda P  Q va, shu sababli A  B ekvivalensiyaning chinlik to‘plami (P Q)(P  Q)  (P P) (P  P)  U U  U bo‘ladi. Bundan A  B formulalarning tavtologiya ekanligi kelib chiqadi. b) A  B formula tavtologiya bo‘lsin. U holda A  B  (A  B)  (B  A)  J teng kuchlilik o‘rinli bo‘lgani uchun, kon’yunksiya ta’rifiga asosan, A  B  J va B  A  J teng kuchliliklar o‘rinlidir. 1- teoremaga ko‘ra, P  Q va Q  P, ya’ni Q  P bo‘lishi kelib chiqadi. Bu, o‘z navbatida, A va B formulalarning mantiqiy ekvivalentligini tasdiqlaydi. ■
Chinlik to‘plami tushunchasidan foydalanib mulohazalar algebrasi bilan matematilcaning boshqa sohalari, jumladan, to‘plamlar algebrasi orasidagi bog‘lanishlami ifodalash mumkin. Mulohazalar algebrasidagi л (kon’yunksiya), v (diz’yunksiya) va —i (inkor) mantiqiy amallarga, mos ravishda, to‘plamlar algebrasidagi П (kesishma), U (birlashma) va (to‘ldirish) amallari to‘g‘ri keladi. Mulohazalar algebrasidagi 1 va 0 o‘zgarmaslarga (konstantalarga) to‘plamlar algebrasidagi U va 0 (universal va bo‘sh) to‘pi ami ar mos keladi. Demak, mulohazalar algebrasidagi biror ifodada (tasdiqda) belgisini П belgisiga, V ni U ga, inkor belgisini to‘ldiruvchi belgisiga, Ini U ga, Oni 0 g a (= ni = ga) almashtirsak, to‘plamlar algebrasidagi ifoda (tasdiq) hosil bo‘ladi va, aksincha almashtirishlar bajarsak, to‘plamlar algebrasidagi ifodadan (tasdiqdan) mulohazalar algebrasidagi ifoda (tasdiq) hosil bo‘ladi. 6- misolda chinlik to‘plami tushunchasidan foydalanib xyz —>(xyzvxyzVfyz) = J teng kuchlilik o‘rinli bo'lishi ko‘rsatilgan edi. Yuqoridagi xulosalar asosida, mulohazalar algebrasining to‘plam algebrasidagiga o‘xshash tasdiqlarini keltirib chiqarish mumkin. Bunday o‘xshashliklaming ayrimlarini keltiramiz.
8- m i s о 1. A va В formulalar uchun A v A v В = J teng kuchlilikning o'rinli bo'lishini ularga mos P va Q chinlik to‘plamlaridan foydalanib isbotlaymiz. A v A v B _formulaning chinlik to‘plami P { j P [ j Q - U [ j Q — U . Shu sababli, A v A v В tavtologiyadir. ■ 1 - teorema. Agar chinlik to‘plamlari mos ravishda P va Q bo‘lgan A va В formulalar uchun A —^ B = J teng kuchlilik o‘rinli bo‘Isa, u holda P с Q bo‘ladi. Isboti. Ma’Iumki, A В formulaning chinlik to‘plami V universal to‘plamning P {JQ qism to‘plamidan iborat. P [ } Q - P \ Q bo‘lgani uchun A —> В J shartga ko‘ra P \ Q = U bo‘lishi kerak. Bundan P \ Q - U yoki P \ Q = 0 kelib chiqadi. Bu esa P c zQ ekanligini bildiradi. Demak, A - ^ B tavtologiya bo‘lishi uchun A formulaning chinlik to'plami В formula chinlik to‘plamining qism to‘plami bo'lishi shart.
■ 2 - teorema. A va В formulalar teng kuchli bo ‘lishi uchun A B formula tavtologiya bo ‘lishi zarur va yetarli. Isboti. A va В formulalaming chinlik to‘plamlari, mos ravishda, P va Q bo‘lsin. a) A va В formulalar teng kuchli, ya’ni A = В bo‘lsin. U holda P = Q va, shu sababli A В ekvivalensiyaning chinlik to‘plami (P\JQ)V[{PVQ) = (PUP)r\{P\SP) = U № = U bo‘ladi. Bundan A. <-> В formulalaming tavtologiya ekanligi kelib chiqadi. 220 b) A В formula tavtologiya bo‘lsin. U holda A В ) л ( В —> A ) = J teng kuchlilik o‘rinli bo‘lgani uchun, kon’yunksiya ta’rifiga asosan, A —^ B = J va В —> A = J teng kuchliliklar o‘rinlidir. 1- teoremaga ko‘ra, P ^ Q va Q c :P , ya’ni Q P boiishi kelib chiqadi. Bu, o‘z navbatida, A va В formulalaming mantiqiy elcvivalentligini tasdiqlaydi. в