Fan: Diskret tuzilmalar Mustaqil ish Topshirdi: Adamboyev Sirojbek Qabul qildi: Urazmetova Shoira

kompozitsiyasi deb,
R1 ∘ R 2 {(x, y): x A, yC ва zB topiladiki (x, z)R 1 va (z, y)R 2} to‘plаmgа аytilаdi.
Teoremа. Ixtiyoriy P, Q, R binаr munosаbаtlаr uchun quyidаgi xossаlаr o‘rinli. 1) (P 1 ) 1  P 2) (P ∘ Q) 1  Q 1 ∘ P 1 3) (P ∘ Q) ∘ R  P ∘ (Q ∘ R) . Munosabatlarning turlarini ularning matritsalari orqali aniqlash qulay. Buning uchun biror A={1,2,3,4} to’plamni olamiz. Bu to’plamning dekart kvadratidan biror
R munosabatni olamiz.
R={(1,1),(1,2),(2,1),(2,2),(3,4),(3,3),(4,3),(4,4)}. Bu munosabatni tekislikda belgilab olamiz.
Buning uchun x o`qqa va y o`qqa to`plam elementlarini joylashtirib chiqamiz.
Munosabat bor o`rinni • bilan, munosabat yo`q o`rinni x bilan belgilaymiz: A A Munosabat tekislikdagi ifodasiga asosan munosabat matritsasini tuzamiz.
Buning uchun x o`qdagi elementlarni satr, y o`qdagi elementlarni ustun nomerlari sifatida olamiz. lar o`rniga 1 lar, x lar o`rniga 0 lar qo`yib, quyidagi matritsani, bu matritsani transponirlab unga teskari matritsani hosil qilamiz
[R] = 1 1 0 0
0 0 1 1
1 1 0 0
1 1 0 0

[R-1 ] = 0 0 1 1

0 0 1 1
0 0 1 1
10001

1. Munosabat refleksivlik bo`lishi uchun [E] [R] shart bajarilishi kerak: 0Bu shart bajariladi, demak, berilgan munosabat refleksivlik shartini qanoatlantiradi. 2. Simmetriklik sharti quyidagicha: [R]=[R-1 ]. Berilgan munosabat va unga teskari munosabatning matritsalari teng. Demak, berilgan munosabat simmetriklik shartini qanoatlantiradi.

1. 
   Tranzitivlik sharti quyidagicha tekshiriladi: [R] [R] [R] . [R] matritsani o`zoziga matritsalarni ko’paytirish qoidasiga ko’ra ko’paytirib, kamida bitta 1 kelgan o`rinda 1 yozamiz:
   

R= 1 0 0 1

1 0 0 1
1 0 1 1
1 0 1 1
[R]= 1 1 0 0
1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1
Tranzitivlik sharti bajariladi, chunki hosil bo`lgan matritsa berilgan matritsa bilan bir xildir.
Har qanday matritsa o’z -o’ziga qism matritsa bo’ladi. 2. Antisimmetriklik shartini tekshiramiz.
[R] [R-1 ] [E] [E] = 0 1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 1
Bunda matritsalarning mos o’rinliklaridagi elementlar ko’paytiriladi:
[R] [R-1 ] = 1 1 1 1
0 0 0 0 1
1 0 0 1 1

1. 
   0 1 1
   

chunki a1,2 , a2,1, a3,4,a4,3 o’rinlarda 1 lar bor, shuning uchun matritsalarning kesishmasi birlik matritsaga qism emas. Bundan kelib chiqadiki, munosabat antisimmetrik emas.
5. Antirefleksivlik shartini tekshiramiz: [R] = Bu shart bajarilmaydi . Chunki bu ikkita matritsaning kesishmalaridan bo’ladi. yana [E] birlik matritsa hosil
6. To’lalik sharti. Munosabat to’la bo’lishi uchun [R] -1 ]= U shart bajarilishi kerak.
Tenglikning chap tomonidagi birlashmalar natijasida barcha elementlari 1 lardan iborat matritsa kelib chiqishi kerak.
Tekshirib ko`rganimizda bunday matritsa hosil bo’lmasligini ko`ramiz. Shuning uchun berilgan munosabat to’la emas.
Munosabatlarning ichida eng ko’p uchraydigan ekvivalent munosabatlardir.
Quyidagi 3 ta shartni qanoatlantiradigan munosabat ekvivalent munosabatdir:
1. Refleksivlik. Agar A to’plamdagi ixtiyoriy x element to’g’risida u o’z-o’zi bilan R munosabatda deyish mumkin bo’lsa, A to’plamdagi munosabat refleksiv munosabat deyiladi va x R x ko’rinishda belgilanadi. Yoki boshqacha ko`rinishda yozadigan bo`lsak, (x,x) .
2. Simmetriklik.
Agar A to’plamdagi x elementning y element bilan R munosabat bo’lishidan y elementning ham x element bilan R munosabatda bo’lishi kelib chiqsa, A to’plamdagi R munosabat simmetrik munosabat deyiladi va x R y y R x ko’rinishda belgilanadi. Yoki boshqacha ko`rinishda yozadigan bo`lsak, (x,y) ═> (y,x)
Tranzitivlik. Agar A to’plamdagi x elementning y element bilan R munosabatda bo’lishi va y elementning z element bilan R munosabatda bo’lishidan x elementning z element bilan R munosabatda bo’lishi kelib chiqsa , A to’plamdagi R munosabat tranzitiv munosabat deyiladi va x R y, y R z x R z ko’rinishida belgilanadi.
Yoki boshqacha ko`rinishda yozadigan bo`lsak, , (y,z) (x,z) 1) Birdan farqli natural sonlarning birdan farqli umumiy bo’luvchiga ega bo’lishi munosabati ekvivalent munosabat emas, chunki bu munosabat uchun refleksivlik va simmetriklik shartlari bajariladi, tranzitivlik sharti esa har doim ham bajarilmaydi.