Mavzu: Chekli to`plamlar yig`indisining Quvvati aniqlash usullari. Ikkita, uchta, to`rtta to`plam yig`indilari uchun Reja
Yüklə 66,59 Kb.
|
|
Quvvat to`plami
Quvvat to'plami barcha kichik to'plamlarni, shu jumladan bo'sh to'plamni va asl to'plamni o'z ichiga olgan to'plamdir. U odatda P bilan belgilanadi. Quvvat to'plami to'plamlarning bir turi bo'lib , ularning asosiyligi ma'lum to'plam uchun tuzilgan kichik to'plamlar soniga bog'liq. Agar A = {x, y, z} toʻplam toʻplam boʻlsa, uning barcha kichik toʻplamlari {x}, {y}, {z}, {x, y}, {y, z}, {x, z}, { x, y, z} va {} quvvat to'plamining elementlari, masalan: A, P(A) = { {x}, {y}, {z}, {x, y}, {y, z}, {x, z}, {x, y, z}, ning quvvatlar toʻplami. Bu yerda P (A) quvvat to'plamini bildiradi. Keling, misollar va xususiyatlar yordamida kontseptsiyani tushunaylik. To'plam nazariyasida A to'plamining quvvat to'plami (yoki quvvat to'plami) A to'plamining barcha kichik to'plamlari to'plami, shu jumladan to'plamning o'zi va nol yoki bo'sh to'plam sifatida aniqlanadi. U P(A) bilan belgilanadi. Asosan, bu to'plam barcha kichik to'plamlarning, shu jumladan berilgan to'plamning nol to'plamining birikmasidir. Agar berilgan to‘plam n ta elementga ega bo‘lsa, uning quvvat to‘plami 2ta elementdan iborat bo‘ladi. Shuningdek, u quvvat to'plamining kardinalligini ifodalaydi. Agar M to`plam bilan natural sonlar to`plami o`rtasida biyek- tiv moslik o`rnatish mumkin bo`lsa, M ga sanoqli to`plam deyiladi. Boshqacha ta'riflasak, agar M to`plam elementlarini natural sonlar vositasida a1, a2, . . . , an, . . . cheksiz ketma-ketlik ko`rinishida nomerlab chiqish mumkin bo`lsa, M ga sanoqli to`plam deyiladi. Quvvat to`plamiga misol Aytaylik, to'plam A = { a, b, c} Elementlar soni: 3 Shunday qilib, to'plamning kichik to'plamlari: { }bu nol yoki bo'sh to'plamdir { a }
{ b }
{ c }
{ a, b }
{ b, c } { c, a } {a, b, c} Quvvat to‘plami P(A) = { { } , { a }, { b }, { c }, { a, b }, { b, c }, { c, a }, { a, b, c }} Endi Quvvat to'plamida 2 3 = 8 element mavjud. To‘plamni tashkil etuvchi ob’yektlar – bu to‘plamning elementlari deb ataladi. Masalan, yuqoridagi misollardagi natural sonlar, o‘quvchilar, talabalar, nuqtalar mos to‘plamlarining elementlari hisoblanadi. To‘plamlar odatda, lotin alfavitining bosh harflari bilan, ularning elementlari esa alfavitning kichik harflari bilan belgilanadi. A to‘plam a, b, c, d, e, f elementlaridan tuzilganligi A={a, b, c, d, e, f} ko‘rinishda yoziladi. To‘plam bir qancha elementlardan iborat bo‘lishi mumkin, quyidagi yozuv: aA, a elementning A to‘plamga tegishliligini bildiradi. Agar aA bo‘lsa, u holda «a element A to‘plamga tegishli», «a element A to‘plamning elementi», «a element A to‘plamda mavjud» yoki «a element A to‘plamga kiradi» deb o‘qiladi. aAyoki aA yozuv esa a elementni A to‘plamga tegishli emasligini bildiradi. Masalan, A – juft natural sonlar to‘plami bo‘lsin, u holda 2A, 5A, 628A va 729A bo‘ladi. 2-ta’rif. To‘plamning elementlari soniga to‘plam quvvati deyiladi va n(A) kabi belgilanadi. Masalan, A={a,b,c,d,e,f,g} to‘plamning quvvati n(A)=7ga, B={a}to‘plamning quvvati n(B) = 1 ga, C={b,d,f} to‘plamning quvvati n(C)=3 ga, D={a,g} to‘plamningquvvati n(D)=2 ga teng. 3-ta’rif. Quvvatlari teng bo‘lgan to‘plamlar teng quvvatli to‘plamlar deyiladi. Masalan, A={a,b,c} va C={b,d,f} to‘plamlar teng quvvatli. n(A) = n(C) = 3. To‘plamlarning berilish usullari. Agar har bir elementning ma’lum bir to‘plamga tegishli yoki tegishli emasligi bir qiymatli aniqlangan bo‘lsa, to‘plam berildi deyiladi. Sonli to‘plamlar uchun xarakteristik xossani formula bilan berish qulay. Bu holda, odatda, kata qavslarichiga to‘plam elementi belgisi, vertical chiziq va undan keyin to‘plam elementiga tegishli xossa yoziladi. Masalan: «M ‒ 6 sonidan kichik bo‘lgan natural sonlar»to‘plami bo‘lsin. Bu to‘plam xarakteristik xossasi orqali M={n |nNva n < 6} ko‘rinishda ifodalanadi. Shunga o‘xshash: C={c|c} Quvvat to`pamining kardinalligi Kardinallik to'plamda mavjud bo'lgan elementlarning umumiy sonini ifodalaydi. Quvvat to'plamida asosiylik to'plamning kichik to'plamlari sonining ro'yxati bo'ladi. Quvvat to'plamining elementlari soni |P (A)| shaklida yoziladi, bu yerda A har qanday to'plamdir. Agar A "n" elementga ega bo'lsa, unda quvvatlar to'plamidagi to'plamning kichik to'plamlari sonini toppish formulasi quyidagicha ifodalanadi: |P(A)| = 2 n Masalan, A = {1, 2, 3} o'rnating. n = A ningelementlarisoni = 3 Shunday qilib, A quvvat to'plamidagi kichik to'plamlar soni quyidagicha bo'ladi:
P|A| = 2 3 = 8 Demak, P(A) {{}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3,}}
Bu asl to'plamdan ancha katta. A quvvat to'plamidagi elementlar soni 2 n ,bu yerda n - A to'plamidagi elementlar soni Hisoblanadigan chekli to'plamning quvvat to'plami sanab o'tiladi. Natural sonlar to'plami uchun biz P(S) to'plamini haqiqiy sonlar bilan birma-bir xaritalashimiz mumkin. S to‘plamning P(S) to‘plamlar birlashmasi, to‘plamlar kesishmasi va to‘plamlarning to‘ldiruvchisi bilan bajarilsa, Mantiqiy algebra misolini bildiradi. Bo'sh to'plam nol elementga ega. Demak, bo'sh to'plamning quvvat to'plami{ }, quyidagicha qayd etilishi mumkin; Nol to'plamni o'zichiga olgan to'plam. U nol yoki nol elementlarni o'z ichiga oladi. Bo'shto'plam yagona kichik to'plamdir. Har qanday chekli S to‘plamning P(S) quvvat to‘plamini hosil qilish uchun rekursiv algoritm qo‘llaniladi. F (e, T) operatsiyasi quyidagicha aniqlanadi: F (e, T) = { X∪ {e} | X ∈ T } Bu x elementga ega bo'lgan T dagi X to'plamining har birini qaytaradi.
P(S) = P(T) ∪ F ( e, P(T)) Xulosa qilish uchun, agar S to'plami bo'sh bo'lsa, u holda quvvat to'plamidagi yagona element nol to'plam bo'ladi. Aks holda, quvvat to'plami ma'lum elementni o'z ichiga olgan barcha kichik to'plamlar va muayyan elementni o'z ichiga olmaydi.
Bitta elementli kichik to'plamlar soni (singl to'plamlar) = 3 Ikki elementli kichik to'plam larsoni (singl to'plamlarning to'ldiruvchilari)=3 Uch elementli kichik to'plamlarsoni (haqiqiy to'plam) = 1 Yuqoridagi munosabatdan |2 s | ni hisoblashimiz mumkin quyidagicha: |2s|=∑k=0|s|(k|s|) Agar |S| = n keyin, |2s|=2n=∑k=0n(kn) Bu quvvat to'plami va binomial teorema o'rtasidagi bog'liqlikdir.
Quvvat to'plamidagi elementlarning umumiy soni = 2 n Bu erda n = 3 (Z to'plamdagi elementlar soni)
Shuning uchun, P(Z) = {{}, {2}, {7}, {9}, {2, 7}, {7, 9}, {2, 9}, {2, 7, 9}}
3-misol: A = {1, 2, 3, 4} to'plamning quvvat to'plami qanday? Yechish: berilgan bo‘lsa, A = {1, 2, 3, 4} ni o‘rnating. Quvvat to'plamining formulasi bo'yicha biz bilamizki, bu yerda hosil qilishimiz mumkin bo'lgan to'plamlar soni quyidagicha ifodalanadi: |P (A)| = 2 n Bu erda n - A to'plam elementlari soni Demak,
A to'plamining 16 ta kichik to'plami bo'ladi. A = {}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, pastki toʻplamlari 4}, {3, 4},{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1,2,3,4} Shunday qilib, A to'plamining quvvat to'plami quyidagicha ifodalanadi: P(A) = { {}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, { 2, 4}, {3, 4},{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1,2,3, 4} }. Natural sonlar tushunchasi har qanday toʻplam tushunchasida noldinmantiqanoʻrinolgankontekstlarda S toʻplaminichekli deb belgilashmumkin, agar S shaklningbaʼzi natural sonlartoʻplamigaikkilanishniqabulqilsa.{\displaystyle \{x\,|\,x Agar in'ektiv, sur'ektivbo'lmaganfunksiyamavjudbo'lsa, S to'plam Dedekind chiksiz deb ataladi{\ Displaystyle f: S \ o'ng ko'rsatkich S} . Bundayfunktsiya S va S ningtegishlikichikto'plami ,ya'ni f ningtasvirio'rtasidagiikkilanishniko'rsatadi. Dedekind cheksiz S toʻplami, f funksiyasiva f tasviridaboʻlmagan x elementiberilganboʻlsa, biz S ningalohidaelementlariningcheksizketma-ketliginihosilqilishimizmumkin , yaʼni .{\displaystyle x,f(x),f(f(x)),...} Aksincha, S dagialohidaelementlardaniboratketma-ketlikberilgan,{\displaystyle x_{1},x_{2},x_{3},...} f funksiyani shundaybelgilashimizmumkinki, ketma-ketlikdagielementlarda{\displaystyle f(x_{i})=x_{i+1}} va f aksholdaidentifikatsiyafunktsiyasikabi harakat qiladi. Shundayqilib, Dedekind cheksizto'plamlari natural sonlargabijektivravishdamoskeladigankichikto'plamlarnio'zichigaoladi. Dedekind cheklitabiiyravishdaharbirin'ektivo'z-o'zinixaritasi ham sur'ektivekanliginianglatadi. Kuratovskiychekliligiquyidagichaaniqlanadi. Har qanday S to'plamiberilgan bo'lsa, birlashmaningikkilikishlashi P quvvat to'plamiga( S ) yarimpanjara tuzilishiniberadi . Bo'shto'plamvasinglto'plamlartomonidanhosilqilingankichikyarimto'plamuchun K ( S ) niyozib , S to'plaminiKuratovski chekli deb ataymiz, agar Sning o'zi K ( S ) ga tegishlibo'lsa. Intuitivjihatdan K ( S ) S ningcheklikichiktoʻplamlaridaniborat. Muhimjihatishundaki, hosil boʻlganinianiqlashuchuninduksiya, rekursiyayoki natural sonlarningtaʼrifishartemas, chunki boʻshtoʻplamvasingltonlarnioʻzichigaolganbarchakichikyarimtoʻplamlarningkesishishini olishorqali K ( S ) niolishmumkin. Yarimpanjaralarvamavhumalgebraningboshqatushunchalaribilantanishbo'lmagano'quvchilarbutunlayelementarformulaniafzalko'rishlarimumkin. Kuratovskiycheklidegani S ning K ( S ) to'plamidayotadi , quyidagichatuzilgan. P ( S ) ningbarcha X kichikto‘plamlarito‘plamiuchun M nishundayyozing : X bo'shto'plamnio'zichigaoladi; P ( S ) dagi harbir T to'plamiuchun , agar X T nio'z ichigaolsa, X ham Tning harqandaysinglbilanbirlashishinio'zichigaoladi. Keyin K ( S ) M ningkesishishisifatidaaniqlanishimumkin . ZFdaKuratovskichekli Dedekind cheklininazardatutadi, lekinaksinchaemas. Ommaboppedagogikiborabilanaytganda, tanlovaksiomasimuvaffaqiyatsizlikkauchraganida, cheksizko'pjuftlikdanbittapaypoqnitanlashimkonibo'lmagancheksizpaypoqoilasigaegabo'lishimumkin. Dedekind bundaypaypoqlarto'plaminichekliqiladi: paypoqlarningcheksizketma-ketligibo'lishimumkinemas, chunkibundayketma-ketlikketma-ketlikdagibirinchipaypoqnitanlab, cheksizko'pjuftliklaruchunbittapaypoqnitanlashimkoniniberadi. Biroq, Kuratovskiningcheksizligibirxilpaypoqlarto'plamiuchunmuvaffaqiyatsizbo'ladi. A va B to'plamlarva f funktsiya A dan B gachabo'lsin B. ( f:A→B ). Tegishlimiqdorko'rsatkichlariyordamidaquyidagilardanharbirinidiqqatbilanto'ldiring f funksiyasi finyeksiyabo'lib, agar... f funktsiyasi fin'ektsiyaemas, agar ... f funksiyasi fsuryeksiyabo'lib, agar... f funktsiyasi fsuryeksiyaemas, agar... f funksiyasi fbijeksiyabo'lib, agar... Element to`plamlarvabirma-biryozishmalar A va B to'plamlar bo'lsin . A to'plam B to'plamga ekvivalentA bo'ladi , agar A to'plamdan B to'plamgaikkilanishmavjudbo'lsa . Buholdabiz A \thickapprox B yozamiz .BABA≈B A \thickapprox B bo'lganda , A to'plami B to'plambilan birma-birmos kelishiniva A to'plami B to'plambilan bir xil kardinallikkaA≈B egaekanligini ham aytamiz .ABAB Eslatma: Agar A BA ga ekvivalentbo'lmasa , biz A \not\thickprox B niyozamiz .BA≉B Har birto'plamuchun , .AA≈A va to'plamlariuchun , agar , keyin .ABA≈BB≈A Barcha , va to'plamlariuchun va bo'lsa, .ABCA≈BB≈CA≈C Preview Activity da biz ekvivalentto'plamlartushunchasinikiritdik. Ushbuta'rifningmotiviikkitato'plamda "birxilmiqdordagielementlargaega" yokiyo'qliginianiqlashningrasmiyusuligaegabo'lishedi. Bu g'oyabirto'plamdanikkinchito'plamgayakkama-yakkayozishmalar (bijection) nuqtainazaridantasvirlangan. Bu g'oyacheklanganto'plamlaruchunoddiybo'libtuyulishimumkin, lekin biz ko'ribturganimizdek, cheksizto'plamlarbilanshug'ullanganimizdabug'oyahayratlanarlioqibatlargaolibkeladi. Oldindanko‘rishfaoliyati 9.1 teoremasida biz isbotlaganuchtaxususiyatrefleksiv, simmetrikvao‘tishmunosabatlaritushunchalarigajudao‘xshash. to'plamdagiekvivalentlikmunosabati deb hisoblamaymiz, chunkiekvivalentlikmunosabatiasosli (universal) to'plamini talab qiladi . Bundayholda, bizningelementlarimiz , va to'plamlaribo'ladivaularkeyinchalikqandaydir universal W to'plaminingkichikto'plamlaribo'lishikerak (W quvvatto'plaminingelementlari . , va to'plamlarini talab qilmaymiz9.1.2UUABCVABCbir xil universal to'plamningkichikto'plamlaribo'lsin. Shuninguchun biz to'plamlarningekvivalentligiganisbatanmunosabatatamasidanfoydalanmaymiz. Biroq, agar va to'plamlarva bo'lsa, biz ko'pincha va ekvivalentto'plamlar deb aytamiz.ABA≈BAB
A to'plami A yoki k sonimavjudbo'lganda cheklanganto'plamdir .AA=∅kA≈Nk To'plamcheksizto'plamdir , agar u cheklito'plambo'lmasa. Agar bo'lsa , to'plamningasosiyligi (yoki asosiyraqam ) deb aytamiz ) deb yozamiz .A≈NkAkkA=k Bundantashqari, biz bo'shto'plamning kardinalligi 0 (yoki asosiyraqam0 )ekanliginiaytamizva biz yozamiz .karta(∅)=0 E'tiborbering, buta'rifgako'ra, bo'shto'plamcheklito'plamdir. Bundantashqari, harbir dagiidentifikatsiyafunksiyasibijeksiya hisoblanadivashuninguchunta'rifgako'ra kardinallikkaegacheklito'plamdir .k∈NNkNkk to'plamigaekvivalentbo'lganharqandayto'plamcheklito'plam bilanbirxilkardinallikkaega .AA teoremada “aniq” natijaniisbotlashuchun biz ko'pishqilgandektuyulishimumkin. Bu bo'limdagiqolgannatijalarga ham xuddishundaybo'lishimumkin, ularcheklito'plamlarhaqidaqo'shimchanatijalarberadi. Maqsadlardanbiri - cheklanganto'plamuchunkardinalliktushunchasito'plamdagielementlarsonihaqidagibizningintuitivtushunchamizgamoskelishigaishonchhosilqilishdir. Yana birmuhimmaqsad - cheksizto'plamlarga biz ilgariduchkelganimizdanko'raqat'iyroqvamatematikishlovberishuchunzaminyaratishdir. Yo'ldavomida biz cheklivacheksizto'plamlaro'rtasidagimatematikfarqniko'ramiz. Cheklito'plamningharbirkichikto'plamichekliekanliginibildiruvchiteoremaniisbotlashuchunquyidagiikkitalemmadanfoydalaniladi. Agar cheklito'plambo'lsava bo'lsa, u holda cheklito'plamva .Ax∉AA∪{x}karta(A∪{x})=karta(A)+1 Har bir natural son uchun , agar boʻlsa, u holda cheklitoʻplamva .mA⊆NmAkarta(A)≤m Agar cheklito'plambo'lsava ningkichikto'plamibo'lsa , u holda cheklito'plamva .SASAkarta(A)≤karta(S) Cheklito'plamgabitta element qo'shishuningkardinalligini 1 ga oshirishininazardatutadi. Cheklanganbo'shbo'lmaganto'plamdanbittaelementniolibtashlashkardinallikni 1 ga kamaytirishi ham haqiqatdir. Agar cheklito'plambo'lsava , u holda cheklito'plamvaAx∈AA−{x}karta(A−{x})=karta(A)−1 Keyingixulosakeyingibo'limdacheklivacheksizto'plamlaro'rtasidagimatematikfarqnita'minlashuchunishlatiladi. Cheklanganto'plamuningto'g'rito'plamlariningbirortasiga ham ekvivalentemas. Ushbubo'limda biz ko'ribchiqadigancheklito'plamlarningoxirgixususiyatiko'pincha " Kabutarlaruyasiprintsipi " deb ataladi . Bu xususiyatning “kabutarteshigi” versiyasidashundaydeyilgan: “Agar kabutar teshigigava ga kirsa ,kamidabittakaptardabirnechtakaptarbor”.mrm>r Bundayvaziyatda biz kaptarlarto‘plamini m kardinallikkaegabo‘lgan P to‘plamga, r to‘plamiesa r ga tengbo‘lgan H to‘plamiga ekvivalent mumkin . funktsiyasinianiqlashimizmumkin, u harbirkaptarnio'zteshigigamoslashtiradi. Pigeonhole Principle bufunktsiyain'ektsiyaemasliginibildiradi. (Bu birma-biremas, chunkibittakaptarteshigigakamidaikkita "xaritaqilingan" kaptarbor.)PHrf:P→H Foydalanilganadabiyotlar internetsaytlari 1.turaev x.matematikmantiqvadiskritmatematika<>nashriyoti, t., 2003.
Internet saytlari 1.http://www.uni-dubna.ru/~mazny/kurses/odm/lekcii/ 2. http://www.lvf2004.com/dop_t2r1part2.html 3. https://www.fayllar.org http://fayllar.org Yüklə 66,59 Kb. Dostları ilə paylaş:
|