Kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Diskret tuzilmalar (Ma’ruza)
Fa’ni bo’yicha


MUSTAQIL ISH

Mavzu: Ekvivalentlik munosabati. Faktor to'plami

Bajardi: Reimbayev Sardor


Toshkent–2022 

A to’plamdagi R ikkilik munosabat, agar R refleksiv, simmetrik va o’tishli bo’lsa, ekvivalentlik munosabati deyiladi.

Raqamlar to'plamidagi tenglik munosabati ko'rsatilgan xususiyatlarga ega, shuning uchun u ekvivalentlik munosabati hisoblanadi.
Haqiqiy sonlar to'plamidagi qat'iy bo'lmagan tengsizlik (≤) munosabati ekvivalentlik munosabati bo'lmaydi, chunki u simmetrik emas: 3≤ 5 dan 5≤ 3 ga mos kelmaydi.
Berilgan R ekvivalentlik munosabati uchun a elementi tomonidan yaratilgan ekvivalentlik klassi (qo‘shnilik klassi) R va a o‘rtasidagi munosabatda bo‘lgan x A ning kichik to‘plamidir. Ko'rsatilgan ekvivalentlik klassi [a] R bilan belgilanadi, shuning uchun bizda:
[a] R = (x A: a, x R).
Keling, bir misolni ko'rib chiqaylik. Uchburchaklar to'plamiga o'xshashlik munosabati kiritiladi. Barcha teng tomonli uchburchaklar bitta kosetga tushishi aniq, chunki ularning har biri, masalan, barcha tomonlari uzunligi birlik bo'lgan uchburchakka o'xshashdir.
1.6 teorema. A to'plamda R ekvivalent munosabat bo'lsin va [a] R koset, ya'ni, [a] R = (x A: a, x R), keyin:
1) har qanday A uchun: [a] R ≠, xususan, a [a] R;
2) turli qo'shni sinflar bir-biriga mos kelmaydi;
3) barcha kosetlarning birlashuvi butun A to'plamiga to'g'ri keladi;
4) turli kosetlar toʻplami A toʻplamining bir qismini tashkil qiladi.
Isbot. 1) R refleksli bo'lgani uchun biz har qanday a, A uchun a, R, demak, [a] R va [a] R ≠ ga ega bo'lishini olamiz;
2) Faraz qilaylik, [a] R ∩ [b] R ≠, ya’ni, A va c [a] R ∩ [b] R dan c element mavjud. Keyin (cRa) & (cRb) dan R simmetriyasi tufayli (aRc) & (cRb) ni olamiz va R ning tranzitivligidan aRb ga ega bo'lamiz.
Har qanday x [a] R uchun bizda: (xRa) & (aRb), keyin R ning tranzitivligi tufayli biz hRb ni olamiz, ya'ni. x [b] R, shuning uchun [a] R [b] R. Xuddi shunday, har qanday y, y [b] R uchun bizda quyidagilar mavjud: (yRb) & (aRb) va R simmetriyasi tufayli biz (yRb) & (bR a) ni olamiz, keyin esa, R ning tranzitivligi, biz yR a ni olamiz, ya'ni. y [a] R va
shuning uchun [b] R [a] R. [a] R [b] R va [b] R [a] R dan biz [a] R = [b] R ni olamiz, ya'ni agar kosetlar kesishsa, u holda ular mos tushadi;
3) ixtiyoriy a va A uchun, isbotlanganidek, bizda [a] R ga ega bo‘lsa, barcha kosetlarning birlashuvi A to‘plamga to‘g‘ri kelishi aniq bo‘ladi.
Isbot. A to'plamning B = (B i) bo'limi berilgan bo'lsin. R munosabatini aniqlaymiz: a, b R, agar va faqat B i mavjud bo'lganda, a va b ikkalasi ham shu B i ga tegishli bo'lsin. Shubhasiz, kiritilgan munosabat refleksiv, simmetrik va tranzitivdir, shuning uchun R ekvivalent munosabatdir. Ko'rsatish mumkinki, agar bo'limlar har xil bo'lsa, ular tomonidan yaratilgan ekvivalentlik munosabatlari ham har xil bo'ladi.
Berilgan ekvivalentlik munosabati R bo'yicha A to'plamning barcha kosetlari yig'indisi bo'limlar to'plami deb ataladi va A / R bilan belgilanadi. Faktorlar to'plamining elementlari kosetlardir. Qo'shni sinf [a] R, siz bilganingizdek, R munosabatida o'zaro bog'liq bo'lgan A elementlaridan iborat.
Z = (…, -3, -2, -1, 0, 1, 2, 3,…) butun sonlar toʻplamidagi ekvivalentlik munosabatiga misol keltiring.
Ikki tamsayı a va b, agar m bo'luvchi bo'lsa, taqqoslanadigan (kongruent) modul m deyiladi. a-b raqamlari, ya'ni bizda mavjud bo'lsa:
a = b + km, k =…, -3, -2, -1, 0, 1, 2, 3,….
Bunday holda, a≡ b (mod m) yozing.
1.9 teorema. Har qanday a, b, c va m> 0 raqamlari uchun bizda:
1) a ≡ a (mod m);
2) agar a ≡ b (mod m), u holda b ≡ a (mod m);
3) a ≡ b (mod m) va b ≡ c (mod m) bo'lsa, a ≡ c (mod m).
Isbot. 1) va 2) tasdiqlar aniq. 3 ni isbotlaymiz). a = b + k 1 m, b = c + k 2 m, keyin a = c + (k 1 + k 2) m, ya'ni. a ≡ c (mod m). Teorema isbotlangan.
Shunday qilib, solishtirish moduli m munosabati ekvivalentlik munosabati bo'lib, butun sonlar to'plamini sonlarning ajratilgan sinflariga ajratadi.
Keling, cheksiz ochiladigan spiral quraylik, bu rasmda. 1.13 qat'iy chiziq va cheksiz burilishli spiral, kesilgan chiziq sifatida ko'rsatilgan. m manfiy bo'lmagan butun son berilsin. Biz barcha butun sonlarni (Z to'plamining elementlarini) rasmda ko'rsatilganidek, bu spirallarning m nurlar bilan kesishgan nuqtalariga joylashtiramiz
Taqqoslash moduli m munosabati uchun (xususan, m = 8 uchun) ekvivalentlik sinfi nurda yotgan raqamlardir. Shubhasiz, har bir raqam bitta va faqat bitta sinfga to'g'ri keladi. Buni m = 8 uchun olishingiz mumkin, bizda:

0] ={…, -8, 0, 8, 16, …};
[ 1] ={…, -7, 1, 9, 17, …};
[ 2] ={…, -6, 2, 10, 18, …};
[ 7] ={…, -9, -1, 7, 15, …}.

Taqqoslash moduli m bo'yicha Z to'plamning omillar to'plami Z / m yoki Z m sifatida belgilanadi. Ko'rib chiqilayotgan ish uchun m = 8
Z / 8 = Z8 = (,,,…,) ni olamiz.
1.10 teorema. Har qanday a, b, a *, b *, k va m butun sonlar uchun:
1) agar a ≡ b (mod m), u holda ka ≡ kb (mod m);
2) agar a ≡ b (mod m) va a * ≡ b * (mod m) bo‘lsa, u holda:
a) a + a * ≡ b + b * (mod m); b) aa * ≡ bb * (mod m).
Biz 2b ishi uchun dalil keltiramiz). Ayrim s va t butun sonlar uchun a ≡ b (mod m) va a * ≡ b * (mod m), keyin a = b + sm va a * = b * + tm bo'lsin. Ko'paytirish,
olamiz: aa * = bb * + btm + b * sm + stm2 = bb * + (bt + b * s + stm) m. Demak,
aa * ≡ bb * (mod m).
Shunday qilib, taqqoslash moduli atama bo'yicha qo'shilishi va ko'paytirilishi mumkin, ya'ni. tenglik bilan bir xil tarzda ishlaydi. Masalan,
Agar munosabat R quyidagi xususiyatlarga ega: refleksiv simmetrik tranzitiv, ya'ni. to‘plamdagi ekvivalentlik munosabati (~ yoki ≡ yoki E). M , u holda ekvivalentlik sinflari to'plami to'plamning omillar to'plami deb ataladi M ekvivalentlik haqida R va belgilandi JANOB
To'plam elementlarining kichik to'plami mavjud M ekvivalent x chaqirdi ekvivalentlik klassi.
Ko'rsatkichlar to'plamining ta'rifidan kelib chiqadiki, u mantiqiy to'plamning kichik to'plamidir: .
Funktsiya chaqiriladi aniqlash va quyidagicha aniqlanadi: