Иккинчи боб

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNALOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI


MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNALOGIYALARI UNIVERSITETI
Algoritmlash va matematik modellashtirish kafedrasi “Diskret tuzilmalar” fani
Mustaqil ish


Mavzu : Nyuton binomi. Binomial koeffietsientlarning xossalari

Fan: Diskret tuzilmalar

Guruh: 061-20 sirtqi
Bajardi: Muhammedova Dilnoza
Tekshirdi: Begimov Oybek


T oshkent 2021


NYUTON BINOMI.
BINOMIAL KOEFFITSIYENTLARNING XOSSALARI.
BINAR MUNOSABATLAR VA ALGEBRAIK AMALLARBINAR MUNOSABATLAR.
EKVIVALENTLIK MUNOSABATI.

Ixtiyoriy A to`plam berilgan bo`lsin.

A² to`plamning ixtiyoriy R qism to`plami A to`plamda binar munosabat deyiladi. Agar (x, u) R bo`lsa, u xolda x element u element bilan R binar munosabatda deyiladi va xRu kabi yoziladi.
Matematikadagi muxim binar munosabatlar uchun ay-rim belgilar kiritilgan.
Misollar.
1) R xaqiqiy sonlar to`plamida x va u sonlarning tenglik munosabati. Uning belgisi Bu munosabat R<sup>2</sup> tekislikkdagi to`g`ri chiziq nuqtalari bilan beriladi.

2. 
   R xaqiqiy sonlar to`plamida x va u sonlarning tengmaslik munosabati. Uning belgisi . Bu munosabat R<sup>2</sup> tekislikda to`g`ri chiziqqa kirmagan barcha nuqtalardan iborat bo`lgan to`plam bilan beriladi.
   
3. 
   R da u sonning x sondan katta ekanligi munosabati:
   belgisi u>x yoki xBu munosabat R² da to`g`ri
   chiziqqan yuqorida yotuvchi nuqtalar to`plami bilan beriladi;
   
4. 
   to`plamlarning tenglik munosabati;
   
5. 
   to`plamlarning tengmaslik munosabati;
   
6. 
   yoki - qism to`plam munosabati;
   
7. 
   yoki - xos qism to`plam munosabati;
   
8. 
   to`g`ri chiziqlarning parallellik munosabati;
   
9. 
   to`g`ri chiziklarning tiklik munosabati;
   

10) bir tenglamalar tizimi ikkinchisining natijasi ekanligi;
11) ikkita tenglamalar tizimining teng kuchlilik munosabati.
Agar A to`plamda berilgan biror R munosabat shunday bo`lsaki, xar qanday uchun aRa o`rinli bo`lsa, u refleksiv munosabat deyiladi. Agar aRb munosabatdan munosabat kelib chiqsa, (ya`ni aRa munosabat xech qanday element uchun bajarilmasa), bunday munosabat antirefleksiv deyiladi.
Agar aR` munosabatning bajarilishidan bRa munosabatning xam bajarilishi kelib chiqsa, bunday munosabat A da simmetriklik munosabati deyiladi.
Agar aRb va bRs munosabatlarning bajarilishidan aRs bajarilishi kelib chiqsa, bunday munosabat tranzitivlik deyiladi.
T a ` r i f . Agar A to`plamdagi R munosabat refleksiv, simmetrik va tranzitiv bo`lsa, uni A da ekvivalentlik munosabati deyiladi va uning uchun aRb belgi o`rniga ko`pincha (yoki ) belgi ishlatiladi.
Ekvivalentlikka misollar:
1) xaqiqiy sonlarning tenglik munosabati;

2. 
   to`plamlarning tenglik munosabati;
   

2. 
   tenglamalar tizimlarining teng kuchlilik munosabati;
   
3. 
   funkqiyalarning tenglik munosabati.
   
4. 
   Muxim misol. A to`plamda N o`zgartirishlar guruxi berilgan bo`lsin.
   

Bu N o`zgartirishlar guruxi yordamida A da ekvivalentlik tushunchasini kiritamiz.
Agar A to`plamning a va b elementlari uchun shunday biektsiya mavjud bo`lsaki, bo`lsa, bu elementlar N -ekvivalent deyiladi va ko`rinishda yoziladi.
Agar ixtiyoriy ni olib, sifatida ni olsak ( -birlik aks ettirish o`zgartirishlar guruxining ta`rifidagi ) shartga ko`ra N ga tegishli, ya`ni xar qanday uchun (refleksivlik).
Endi bo`lsin. U xodda shunday mavjudki, . O`zgartirishlar guruxining ta`rifidagi d₃) shartga ko`ra. . U xodda tenglikka tatbiq qilsak, . Bundan ya`ni (simmetriklik).
Agar va bo`lsa, shunday va biekqiyalar mavjudki, . Bulardan , ya`ni . O`zgartirishlar guruxining ) shartiga ko`ra Bundan va tenglikdan munosabatni olamiz (tranzitivlik).
Demak, (N - ekvivalentlik) xaqiqatan xam ekvivalentlik munosabati ekan.
Kelajakda bu ekvivalentlikni N o`zgartirishlar guruxi xosil qilgan ekvivalentlik (N-ekvivalentlik) deb ataymiz.
A to`plam biror usul bilan sinflarga bo`lingan bo`lsin: . Bu bo`linma yordamida A go`plamga ekvivalentlik munosabatani kiritamiz.
Agar x,u A elementlar V bo`linmadagi bir sinfga tegishli bo`lsa, ularni V bo`linmaga nisbatan ekvivalent deymiz va x-u shaklida yozamiz,
Bu ekvivalentlik refleksivlik, simmetriklik va tranzitivlik xossalariga ega.
Ixtiyoriy A to`plamda xar qanday ekvivalentyaik munosabati shunday xosil qilinishi mumkinligini ko`rsatamiz.
A to`plamda biror "~" ekvivalentlik munosabati berilgan bo`lsin. Ixtiyoriy x A uchun x orqali x ga ekvivalent bo`lgan barcha u A elementlar to`plamini belgilaymiz va { , x A) to`plamlar tizimi A ni sinflarga bo`lishini ko`rsatamiz.
Refleksivlik xossasiga asosan xar bir x A uchun x , ya`ni . endi xar bir element yagona sknfga tegishli ekanligini ko`rsatamiz. Faraz qilaylik, va . bo`lsin, ya`ni z-x. Buvdan simmetriklik xossasiga asosan x-z,. Ixtiyoriy elementni olamiz. U xolda z-y, Yuqoridagi x-z va z-y munosabatlardan tranzitivlik xossasiga asosan x-u ni olamiz, ya`ni . Ushbu element ixtiyoriy bo`lgani uchun . Yuqoridagiga o`xshash muloxazalar bilan munosabat xam ko`rsatiladi, ya`ni . Bu bilan to`plamlar tizimi A to`plamni sinflarga bo`lishi ko`rsatildi.
Shunday qilib, A to`plamdagi ekvivalentlik munosabati bilan A ni sinflarga bo`lish orasida o`zaro bir qiymatli bog`lanish ko`rsatildi.
A to`plamda biror R ekvivalentlik munosabati berilgan va S- biror to`plam bo`lsin.
Agar aks ettirish, ya`ni A to`plam elementlarining biror f xossasi uchun munosabatdan tenglik kelib chiqsa, bunday aks ettirish R-invariavgg (R- ekvivalentliqda saqlanuvchi, o`zgarmas) deyiladi.
Xususan, agar A to`plamdagi ekvivalentlik munosabati A to`plamdagi biror N o`zgarishlar guruxi xosil qilgan N-ekvivalentlik munosabati bo`lsin. Bu xolda N – invariant aks ettirish ta`rifi quyvdagicha berilishi mumkin.
Agar xar qanday va uchun tenglik o`rinli bo`lsa, bunday aks etshirish N -invariant (N o`zgarishlar guruxi ta`sirida saqlanuvchi) deyiladi. N - invariant aks ettirishlar matematikada va fanning turli soxalardda ko`p uchraydi. Masalan, yopiq fizik tizimning energiyasi yopiq fizik tizimning barcha fizik o`zgarishlariga nisbatan saqlanadigan kattalikdir (energiyaning saqlanish qonuni). Mexanik tizimning massasi mexanik xarakatlarda saqlanadi.
R-invariant aks ettirishlar quyidagi xossalari tufayli muxim axamiyatga ega: agar elementlar shunday bo`lsaki, bo`lsa, bunday elementlar R- ekvivalent bo`lmaydi. SHunday qilib, R- invariantlar R-ekvivalent sinflarni farq qilish vositasi sifatvda axamiyatga ega.
Ta`rif. R-invariantlar tizimi quyidagi shartni qanoatlantirsa, u to`la deyiladi: xar qanday ikkita R-ekvivalent bo`lmagan elementlar uchun shunday R-invariynt mavjudki, .
Keyingi boblarda R- invariant funkqiyalarni ko`p uchratamiz.