Munosabatlar. Binar munosabatlar. Ekvivalentlik munosabati

Munosabatlar. Binar munosabatlar. Ekvivalentlik munosabati.
Tartiblangan to‘plamlar.
2.1-ta’rif. A to‘plamning B to‘plamga R munosabati deb A B
to‘g‘ri ko‘paytmaning R A B qism to‘plamiga aytiladi. Munosabatlar quyidagicha ifodalanadi:
aRb , agar a,b R A B .
(Bu ta‘ririf binar munosabatlar uchun, ya‘ni ikkita to‘plam
orasidagi munosabat)
2.2-ta’rif. Agar A=B bo‘lsa, u holda R munosabat A to‘plamdagi munosabat deyiladi.
A to‘plamdagi turli munosabatlar orasida quyidagi munosabatlar ahamiyatli:
teskari munosabat: { a, b : b, a R}
2.3-ta’rif.
kompozitsiyasi deb
R1 A B va
R2 B C
munosabatlarning
R R A C { a,c : b B : aR b, bR c} munosabatiga
1 2 1 2
aytiladi.
A to‘plamdagi munosabatlar kompozitsiyasi deb A to‘plamdagi munosabatlarga aytiladi.
2.4-ta’rif. A to‘plamidagi R munosabatlar darajasi uning o‘ziga
bo‘lgan kompositsiyasiga
Rn
R...R
n...marta
Nolinchi va birinchi darajali munosabatlar darajasini kiritish orqali quyidagi ta‘rifga ega bo‘lamiz:
R I , R1 R, R2 R R, ... , Rn
Rn 1R
To‘plamda munosabatlar asosiy xususiyatlarini qarab chiqamiz.
ega;
Agar
a a,b R b,a R
bo‘lsa, R simmetrik xususiyatga
Agar
a,b A ( a,b R b, a R) a b
antisimmetrik
xususiyatiga ega;
Agar
a,b,c A ( a,b R b,c R) a,c R
tranzitivlik
xususiyatiga ega;
Agar
a,b A ( a,b R)
yoki ( b,a R)
bo‘lsa, to‘liq (yoki
chiziqli) bo‘ladi.
A to‘plamda R munosobat R A2 ko‘rinishda bo‘lsin. U holda,
R refleksiv I R
R antirefleksiv R I
R simmetrik
R antisimmetrik
R R1
R R1 I
R tranzitiv R R R
R to‘liq
R I R1 U
bo‘ladi.
Funksiyalar. Funksiya matematikaning asosiy tushunchalaridan biri bo‘lib, A to‘plamni B to‘plamga bir qiymatli akslantiruvchi
munosabatni ifodalab,
f : A B
ko‘rinishda yoziladi.
2.5-ta’rif: f – munosabat A to‘plam bilan B to‘plam o‘rtasidagi
( a,b a f , a,c f ) b c,
ko‘rinishdagi munosabat bo‘lsin, u holda bunday munosabatga funksiya deyiladi va quyidagicha belgilanadi:
f
f : A B yoki A B
Agar
a,b f
bo‘lsa, u holda
b f (a)
bo‘ladi, a funksiya
argumenti deb, b esa funksiya qiymati deb ataladi.
2.6-ta’rif: Agar
chiqsa, u holda
b f (a1) va
b f (a2 )
ekanligidan
a1 a2
kelib
f : A B
funksiya in‘yektiv deyiladi.
2.7-ta’rif: Agar chiqsa, u holda
b B, a A
munosabatlaridan
b f (a)
kelib
f : A B
funksiya syub‘yektiv deyiladi.
2.8-ta’rif: Agar
f : A B
funksiya bir vaqtning o‘zida ham
in‘yektiv, ham syur‘yektiv bo‘lsa, u holda, funksiya biyektiv yoki o‘zaro bir qiymatli deyiladi,
Bir vaqtning o‘zida refliksivlik, simmetriklik va tranzitivlik shartlari bajariladigan munosabatga ekvivalentlik munosabati deyiladi.
Agar R ekvivalentlik munosabatida a, b R bajarilsa, quyidagi belgilash ishlatiladi:
a b .
2.9-ta’rif: R – A to‘plamdagi ekvivalentlik munosabati bo‘lsin. A
to‘plamning a elementi bilan R munosabatda bo‘lgan to‘plamga,
a A
elementning ekvivalentlik sinfi deyiladi:
[a] {b | a b}
Bunda quyidagi munosabatlar bajarilishi lozim:
a A[a] ,
a b [a] [b],
a b [a] [b] .
2.10-ta’rif: Birlashmasi A to‘plamga teng bo‘lgan, A ning o‘zaro kesishmaydigan qism to‘plamlariga, to‘plamni bo‘laklash deyiladi.
{Bi }iI , A to‘plam qism to‘plamlarining biror to‘plami
bo‘lsin. T, A ni bo‘laklash deyiladi, agarda uchun quyidagi xossa o‘rinli bo‘lsa:
Bi Bj
bunda i
j,
iI
Faktor to’plam. A to‘plamning, R ekvivalentlik munosabatiga nisbatan ekvivalentlik munosabatlar to‘plami faktorto‘plam deyiladi va A / R ko‘rinishda belgilanadi.
Faktorto‘plam, A to‘plamning barcha qism to‘plamalari
to‘plamining qism to‘plami hisoblanadi: A:
A / R 2A
2.1-misol. Z butun sonlar to‘plami uchun quyidagi R munosabatni o‘rnatamiz:
aRb, agarda a-b, 5 ga qoldiqsiz bo‘linsa.
Ushbu munosabat ekvivalentlik munosbatidir, chunki, bunda refleksivlik, simmetriklik, va tranzitivlik munosabatlari qoldiqli bo‘lish amalining xossalaridan kelib chiqadi.
Z ning Z/R faktor to‘plami quyidagi 5 ta ekvivalentlik sinfidan iborat bo‘ladi:
Z / R {[0],[1],[2],[3],[4]}
Tartiblash munosabati. Tartiblash munosabati matematika, informatika va kundalik hayotda keng qo‘llaniladi. U yoki bu ob‘ektlalarni tartiblash tez-tez uchrab turadigan hodisa.
Matemtikada, maksimum, minimum, funksiya monotonligi tushunchalarining asosini munosabat belgilaydi.
Informatikada, barcha saralash, qidirish va boshqa algoritmlar tartiblash munosabatiga tayanadi.
2.11-ta’rif: Antisimmetrik tranzitv munosabat tatiblash munosabati deyiladi.
2.12-ta’rif: Refleksiv tartiblash munosabati noqat‘iy tatiblash munosabati
deyiladi.
2.13-ta’rif: Antirefleksiv tartiblash munosabati qat‘iy tatiblash munosabati
deyiladi.
2.14-ta’rif: Agar tartiblash munosabati to‘liq bo‘lsa, u to‘liq yoki chiziqli tartiblash deyiladi, aks holda qisman tartiblash deyiladi.
Agar R – tartiblash munosabati bo‘lsa, u holda aRb quyidagilarni bildiradi:
a b qat‘iy tartib;
a b noqat‘iy tartib;
a b umumiy holda.
2.15-ta’rif: A to‘plamning a elementi tartiblash munosabiga nisbatan minimal element deyiladi, agarda unga nisbatan kichik element mavjud bo‘lmasa:
b A :(b a,b
2.16-ta’rif: A va B tartiblangan to‘plamalar bo‘lsin. Agarda
a1, a2 A
uchun
a1 a2
dan
f (a1)
f (a2 )
kelib chiqsa,
f : A B
funksiya monoton deyiladi.
2.17-ta’rif: Agarda
a1, a2 A
uchun
a1 a2
dan
f (a1)
f ( a2 )
kelib chiqsa,
f : A B
funksiya qat‘iy monoton deyiladi.
2.2-misol: А={1,2,3,4} to‘plamda R={< x; y>: x > y} munosabat
mavjud bo‘lsin. R ning qiymatlari va aniqlanish sohasini toping. R 1 R ;
R ∘ R munosabatlarni matrisalar usulida aniqlang. Munosabatlarning
xossalarini keltiring.
Yechimi: Dastlab А to‘plamning
R: R = {<2, 1>, <3, 1>, <3, 2>, <4, 1>, <4, 2>, <4, 3>} munosabatga
tegishli barcha elementlari tartiblangan juftliklarini hosil qilamiz.
Munosabatning aniqlanish sohasi DR={2,3,4}, qiymatlari sohasi
ER = {1,2,3}.
R 1
={<у; х>: <x; y>
R }={<x; y>: y>x}={<x; y>: x<y}.
R ={<х; у>: <x; y> R }={<x; y>: x y}.
R, R -1; R va R ∘ R munosabatlarning matrisalari quyida keltirilgan:
0 0
1
|| R || 1 0
1
1 1
1 1
0 0
0 0
0
0
;
1 0
1 1
0 1 1
0
|| R 1 || 0 0 1
0 0
0 0 0
0 0 0
1
1
1 ;
0
0
0
|| R || 0 1
0
0 0
1 1
1
1
;
0 1
|| R
∘ R || 0 0 0
1
0 0
1 1 0
0 .
0
0
R munosabat
|| R ∘ R ||
kompoiztsiyasining rij elemuntlarini aniqlashni
bir nechta misolda tushuntiramiz: r11 0 0 0 1 0 1 0 1 0 ; r12 0 0 0 0 01 01 0 ; r13 0 0 0 0 0 0 0 1 0 ;
r14
0 0 0 0 0 0 0 0 0 ;
r21 1 0 0 1 0 1 0 1 0 ;
R munosabat antirefliksiv hisoblanadi, sababi istalgan x R
element uchun x> x shart bajarilmaydi.
R munosabat nosemmitrik, sababi istalgan x, y А elementlar uchun, x> y ekanligidan y> x kelib chiqmaydi.
R antisimmetrik hamda tranzitiv xususiyatga ega sababi istalgan x, y, z А elementlar uchun: agar x> y va y> z bo‘lsa, demak x> z.
|