Diskret riyaziyyatın əsasları.

Çoxluq anlayışı. Çoxluqlar arasında əlaqə.

Dəst müəyyən bir xüsusiyyətə malik olan, vahid bütövlükdə birləşən obyektlərin məcmusudur.

Çoxluğu təşkil edən obyektlər adlanır elementləri dəstləri. Müəyyən bir obyekt toplusunun çoxluq adlandırılması üçün aşağıdakı şərtlər yerinə yetirilməlidir:

· Elementin verilmiş kolleksiyaya aid olub-olmadığını müəyyən etmək üçün mono olan bir qayda olmalıdır.

· Elementləri bir-birindən ayırmaq üçün bir qayda olmalıdır.

Çoxluqlar böyük hərflərlə, elementləri isə kiçik hərflərlə işarələnir. Dəstləri təyin etməyin yolları:

· Set elementlərinin sadalanması. - sonlu çoxluqlar üçün.

Xarakterik xüsusiyyətin təyin edilməsi .

boş dəst- tərkibində heç bir element (Ø) olmayan çoxluq deyilir.

İki çoxluq eyni elementlərdən ibarətdirsə, ona bərabər deyilir. , A=B

Bir dəstə Bçoxluğun alt çoxluğu adlanır VƏ( , yalnız və yalnız çoxluğun bütün elementləri olduqda B dəstinə aiddir A.

Misal üçün: , B =>

Əmlak:

Qeyd: adətən adlanan eyni çoxluğun alt çoxluğunu nəzərdən keçirin universal(u). Universal dəst bütün elementləri ehtiva edir.

Dəstlər üzərində əməliyyatlar.

A

B

1. Assosiasiya 2 A və B çoxluğu A və ya B çoxluğunun elementlərinin aid olduğu çoxluq adlanır (çoxluqlardan ən azı birinin elementləri).

2.keçid 2 dəst eyni zamanda həm birinci, həm də ikinci çoxluğa aid olan elementlərdən ibarət yeni çoxluqdur.

Nr: , ,

Əmlak: birləşmə və kəsişmə əməliyyatları.

· Kommutativlik.

assosiativlik. ;

· Distribyutor. ;

U

4.Əlavə. Əgər VƏ universal çoxluğun alt çoxluğudur U, sonra çoxluğun tamamlayıcısı VƏÇoxlu U(qeyd olunur) çoxluğun həmin elementlərindən ibarət çoxluqdur U dəstinə aid olmayan VƏ.

Binar münasibətlər və onların xassələri.

Qoy olsun VƏ və AT bunlar törəmə təbiət dəstləridir, sıralı bir cüt elementi nəzərdən keçirin (a, c) a ϵ A, c ϵ B sifarişli “enks” hesab edilə bilər.

(a 1, a 2, a 3,...a n), harada a 1 ϵ A 1; a 2 ϵ A 2; …; a n ϵ A n ;

Dəstələrin kartezian (birbaşa) hasili A 1, A 2, ..., A n, formasının sıralı n k-dan ibarət çoxluq adlanır.

Nr: M= {1,2,3}

M× M= M 2= {(1,1);(1,2);(1,3); (2,1);(2,2);(2,3); (3,1);(3,2);(3,3)}.

Dekart məhsulunun alt çoxluqları dərəcə nisbəti adlanır n ya da enary əlaqə. Əgər n=2, sonra düşünün ikili münasibət. Buna nə deyirlər a 1, a 2 binar əlaqədədirlər R, nə vaxt a 1 R a 2.

Çoxluqda ikili əlaqə Mçoxluğun birbaşa hasilinin alt çoxluğu adlanır nöz üzərində.

M× M= M 2= {(a, b)| a, b ϵ M) əvvəlki misalda nisbət çoxluqda daha kiçikdir M aşağıdakı çoxluğu yaradır: ((1,2);(1,3); (2,3))

İkili münasibətlər müxtəlif xüsusiyyətlərə malikdir, o cümlədən:

Refleksivlik: .

· Anti-refleksivlik (refleksivlik): .

· Simmetriya: .

· Antisimmetriya: .

· Keçidlilik: .

· Asimmetriya: .

Münasibətlərin növləri.

Ekvivalentlik əlaqəsi;

· Sifariş əlaqəsi.

v Refleksiv keçid əlaqəsi kvazi nizamlı əlaqə adlanır.

v Refleksiv simmetrik keçid əlaqəsi ekvivalentlik münasibəti adlanır.

v Refleksiv antisimmetrik keçid əlaqəsi (qismən) sıra əlaqəsi adlanır.

v Antirefleksiv antisimmetrik keçid əlaqəsi ciddi nizam əlaqəsi adlanır.

Tərif. İkili əlaqə R cütlərin alt çoxluğu adlanır (a,b)∈R Dekart məhsulu A×B, yəni R⊆A×B. Eyni zamanda çoxlu A R münasibətinin təyini oblastı, B çoxluğuna qiymətlər oblastı deyilir.

Qeyd: aRb (yəni a və b R-ə münasibətdədir). /

Şərh: əgər A = B , onda R-ə A çoxluğuna münasibət deyilir.

Binar əlaqələrin təyin edilməsi yolları

1. Bu əlaqənin təmin olunduğu siyahı (cütlərin sadalanması).

2. Matris. İkili münasibət R ∈ A × A , burada A = (a 1 , a 2 ,..., a n), i-nin kəsişməsində olan c ij elementinin n düzənli kvadrat matrisinə uyğundur. -ci sətir və j-ci sütun, a i və j arasında R əlaqəsi varsa 1-ə, yaxud yoxdursa 0-a bərabərdir:

Münasibət xassələri

A, R ∈ A×A çoxluğuna R münasibəti olsun. Sonra R əlaqəsi:

refleksiv olaraq Ɐ a ∈ A olarsa: a R a (refleksiv əlaqənin matrisasının əsas diaqonalı yalnız birini ehtiva edir);

Ɐ a ∈ A olduqda antireflekslidir: a R a (refleksiv münasibət matrisinin əsas diaqonalında yalnız sıfırlar var);

simmetrik əgər Ɐ a , b ∈ A: a R b ⇒ b R a (belə əlaqənin matrisi əsas diaqonala, yəni c ij c ji ilə bağlı simmetrikdir);

antisimmetrik əgər Ɐ a, b ∈ A: a R b & b R a ⇒ a = b (belə əlaqənin matrisində baş diaqonala görə simmetrik olanlar yoxdur);

keçidli olaraq Ɐ a, b, c ∈ A: a R b & b R c ⇒ a R c cərgəsi, yəni c ij = 1 olarsa, j-ci cərgədə olanların hamısı (bu vahidlər k e koordinatlarına uyğun gəlsin ki, c jk = 1) eyni k koordinatlarında i-ci cərgədə olanlara uyğun olmalıdır, yəni c ik = 1 (və bəlkə də digər koordinatlarda).

Tapşırıq 3.1. Natural ədədlər çoxluğunda verilmiş R - “bölən olmaq” münasibətinin xassələrini müəyyən edin.

Qərar.

nisbət R = ((a,b):a bölən b):

refleksiv, antirefleksiv deyil, çünki istənilən ədəd özünü qalıqsız bölür: a/a = 1 bütün a∈N ;

simmetrik deyil, antisimmetrik, məsələn, 2 4-ün bölənidir, lakin 4-ü 2-nin bölməsi deyil;

keçidlə, çünki b/a ∈ N və c/b ∈ N olarsa, onda c/a = b/a ⋅ c/b ∈ N olarsa, məsələn, 6/3 = 2∈N və 18/6 = 3∈N olarsa , onda 18/3 = 18/6⋅6/3 = 6∈N.

Tapşırıq 3.2.İnsanlar toplusunda verilmiş R - “qardaş olmaq” münasibətinin xassələrini müəyyənləşdirin.
Qərar.

Nisbət R = ((a,b):a - b-nin qardaşı):

hamı üçün aRa-nın aşkar olmaması səbəbindən refleksiv olmayan, anti-refleksiv;

simmetrik deyil, çünki ümumiyyətlə qardaş a və bacı b arasında aRb var, lakin bRa deyil;

antisimmetrik deyil, çünki a və b qardaşdırsa, aRb və bRa, lakin a≠b;

keçid olaraq, qardaşları ümumi valideynləri (ata və anası) olan insanlar adlandırsaq.

Tapşırıq 3.3. Quruluş elementləri toplusunda göstərilən R - "boss olmaq" əlaqəsinin xüsusiyyətlərini müəyyənləşdirin

Qərar.

Nisbət R = ((a,b) : a - patron b):

• qeyri-refleksiv, anti-refleksiv, əgər müəyyən bir şərhdə mənası yoxdursa;
• simmetrik deyil, antisimmetrik, çünki bütün a≠b aRb və bRa eyni vaxtda təmin edilmir;
• keçidli, çünki a b-nin, b isə c-nin başıdırsa, a da c-nin başıdır.

M i çoxluğunda matrislə müəyyən edilmiş R i münasibətinin xassələrini müəyyən edin, əgər:

1. R 1 "5-ə bölündükdə eyni qalığa malikdir"; M 1 natural ədədlər çoxluğudur.
2. R 2 "bərabər olmaq"; M 2 natural ədədlər çoxluğudur.
3. R 3 "eyni şəhərdə yaşayır"; M 3 insanlar toplusu.
4. R 4 "tanış olmaq"; M 4 çox adam.
5. R 5 ((a,b):(a-b) - cüt; M 5 ədədlər toplusu (1,2,3,4,5,6,7,8,9).
6. R 6 ((a,b):(a+b) - cüt; M 6 ədədlər toplusu (1,2,3,4,5,6,7,8,9).
7. R 7 ((a,b):(a+1) - bölən (a+b)) ; M 7 - dəst (1,2,3,4,5,6,7,8,9).
8. R 8 ((a,b):a - bölən (a+b),a≠1); M 8 natural ədədlər çoxluğudur.
9. R 9 "bacı olmaq"; M 9 - bir çox insan.
10. R 10 "qızı olmaq"; M 10 - bir çox insan.

Binar əlaqələr üzərində əməliyyatlar

R 1 , R 1 A çoxluğunda müəyyən edilmiş əlaqələr olsun.

birlik R 1 ∪ R 2: R 1 ∪ R 2 = ((a,b) : (a,b) ∈ R 1 və ya (a,b) ∈ R 2 ) ;

kəsişmə R 1 ∩ R 2: R 1 ∩ R 2 = ((a,b) : (a,b) ∈ R 1 və (a,b) ∈ R 2 ) ;

fərq R 1 \ R 2: R 1 \ R 2 = ((a,b) : (a,b) ∈ R 1 və (a,b) ∉ R 2 ) ;

universal münasibət U: = ((a;b)/a ∈ A & b ∈ A). ;

əlavə R 1 U \ R 1, burada U = A × A;

şəxsiyyət əlaqəsi I: = ((a;a) / a ∈ A);

əks əlaqə R-1 1 :R-1 1 = ((a,b) : (b,a) ∈ R 1 );

tərkibi R 1 º R 2: R 1 º R 2: = ((a,b) / a ∈ A&b ∈ B& ∃ c ∈ C: aR 1 c & c R 2 b), burada R 1 ⊂ A × C və R 2 ⊂ C×B;

Tərif. Əlaqə dərəcəsi A çoxluğundakı R onun özü ilə tərkibidir.

Təyinat:

Tərif. Əgər R ⊂ A × B olarsa, onda R º R -1 deyilir əlaqənin nüvəsi R .

Teorem 3.1. R ⊂ A × A A çoxluğunda müəyyən edilmiş əlaqə olsun.

1. R yalnız və yalnız o halda (bundan sonra ⇔ işarəsi istifadə olunur) I ⊂ R olduqda refleksdir.
2. R simmetrikdir ⇔ R = R -1 .
3. R keçidlidir ⇔ R º R ⊂ R
4. R antisimmetrikdir ⇔ R ⌒ R -1 ⊂ I .
5. R antirefleksdir ⇔ R ⌒ I = ∅ .

Tapşırıq 3.4 . Cütlüklərin sadalanması ilə verilən (1,2,3) və (1,2,3,4) çoxluqlar arasında R əlaqəsi olsun: R = ((1,1), (2,3), (2, 4), (3.1), (3.4)). Bundan əlavə, S çoxluqlar arasındakı əlaqədir S = ((1,1), (1,2), (2,1), (3,1), (4,2)). R -1 , S -1 və S º R hesablayın. (S º R) -1 = R -1 , S -1 olduğunu yoxlayın.

Qərar.
R -1 = ((1.1), (1.3), (3.2), (4.2), (4.3));
S -1 = ((1.1), (1.2), (1.3), (2.1), (2.4));
S º R = ((1,1), (1,2), (2,1), (2,2), (3,1), (3,2));
(S º R) -1 = ((1,1), (1,2), (1,3), (2,1), (2,2), (2,3));
R -1 º S -1 = ((1.1), (1.2), (1.3), (2 .1), (2.2), (2.3)) = (S º R ) -bir .

Tapşırıq 3.5 . Bütün insanların çoxluğunda R "...valideyn..." və S "...qardaş..." münasibəti olsun. Münasibətin qısa şifahi təsvirini verin:

R -1 , S -1 , R º S, S -1 º R -1 və R º R.

Qərar.

R -1 - münasibət "... uşaq ...";

S -1 - münasibət "... qardaş və ya bacı ...";

R º S - əlaqə "... valideyn ...";

S -1 º R -1 - əlaqə "... uşaq ..."

R º R - münasibət "...nənə və ya baba..."

Müstəqil həll üçün tapşırıqlar

1) Bütün insanların çoxluğunda R "...ata...", S isə "...bacı..." münasibəti olsun. Münasibətin şifahi təsvirini verin:

R -1 , S -1 , R º S, S -1 º R -1 , R º R.

2) Bütün insanların çoxluğunda R "...qardaş...", S isə "...ana..." münasibəti olsun. Münasibətin şifahi təsvirini verin:

R -1 , S -1 , S º R, R -1 º S -1 , S º S.

3) Bütün insanların çoxluğunda R “...baba...”, S isə “...oğul...” münasibəti olsun. Münasibətin şifahi təsvirini verin:

4) Bütün insanların çoxluğunda R “...qızı...”, S isə “...nənə...” münasibəti olsun. Münasibətin şifahi təsvirini verin:

5) Bütün insanların çoxluğunda R "...qardaşı...", S isə "...ata..." münasibəti olsun. Münasibətin şifahi təsvirini verin:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

6) Bütün insanların çoxluğunda R “bacı...” münasibəti, S isə “ana...” münasibəti olsun. Münasibətin şifahi təsvirini verin:

R -1 , S -1 , R º S, S -1 º R -1 , S º S.

7) Bütün insanların çoxluğunda R “...ana...”, S isə “...bacı...” münasibəti olsun. Münasibətin şifahi təsvirini verin:

R -1 , S1, R º S, S1 º R1, S º S.

8) Bütün insanların çoxluğunda R “...oğul...”, S isə “...baba...” münasibəti olsun. Münasibətin şifahi təsvirini verin:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

9) Bütün insanların çoxluğunda R “...bacı...”, S isə “...ata...” münasibəti olsun. Münasibətin şifahi təsvirini verin:

R -1 , S -1 , R º S, S -1 º R -1 , S º S.

10) Bütün insanların çoxluğunda R “...ana...”, S isə “...qardaş...” münasibəti olsun. Münasibətin şifahi təsvirini verin:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

Təriflər

• 1. A və B çoxluqlarının elementləri arasındakı ikili əlaqə RAB, RAA dekart məhsulunun istənilən alt çoxluğudur.
• 2. Əgər A=B olarsa, onda R A üzərində ikili münasibətdir.
• 3. Qeyd: (x, y)R xRy.
• 4. R ikili münasibətin təyin oblastı R = çoxluğudur (x: elə y var ki, (x, y)R).
• 5. R ikili münasibətin diapazonu R = çoxluğudur (y: elə x var ki, (x, y)R).
• 6. A və B elementləri arasında R ikili əlaqənin tamamlayıcısı R = (AB) R çoxluğudur.
• 7. R ikili münasibəti üçün tərs münasibət R1 = ((y, x) : (x, y)R çoxluğudur.
• 8. R1AB və R2BC münasibətlərinin hasili R1 R2 = ((x, y) münasibətidir: elə zB mövcuddur ki, (x, z)R1 və (z, y)R2).
• 9. Əgər iki şərt yerinə yetirilərsə, f münasibəti A-dan B-yə funksiya adlanır:
  • a) f \u003d A, f B
  • b) bütün x, y1, y2 üçün (x, y1)f və (x, y2)f-nin y1=y2 mənasını verməsi faktı.
• 10. Birinci abzasda f = A, f = B olarsa, f münasibəti A-dan B-yə funksiya adlanır.
• 11. Qeyd: (x, y)f y = f(x).
• 12. iA: AA eyniləşdirmə funksiyası aşağıdakı kimi müəyyən edilir: iA(x) = x.
• 13. Əgər hər hansı x1, x2, y üçün y = f(x1) və y = f(x2) faktının x1=x2 mənasını verməsi f funksiyası 1-1-funksiya adlanır.
• 14. f funksiyası: AB, əgər f = A, f = B və f 1-1 funksiyası olarsa, A və B arasında təkbətək uyğunluğu yerinə yetirir.
• 15. A çoxluğunda R ikili münasibətinin xassələri:
  • - refleksivlik: (x, x)R bütün xA üçün.
  • - əks olunmazlıq: (x, x)R bütün xA üçün.
  • - simmetriya: (x, y)R (y, x)R.
  • - antisimmetriya: (x, y)R və (y, x)R x=y.
  • - keçid qabiliyyəti: (x, y)R və (y, z)R (x, z)R.
  • - dixotomiya: bütün xA və yA üçün ya (x, y)R və ya (y, x)R.
• 16. P(A)-dan A1, A2, ..., Ar çoxluqları A çoxluğunun bir hissəsini təşkil edir, əgər
• - Аi , i = 1, ..., r,
• - A = A1A2...Ar,
• - AiAj = , i j.

Ai , i = 1, ..., r alt çoxluqları bölmə blokları adlanır.

• 17. A çoxluğundakı ekvivalentlik A üzərində refleksiv, keçidli və simmetrik əlaqədir.
• 18. R ekvivalentliyinə görə x elementinin ekvivalentlik sinfi [x]R=(y: (x, y)R) çoxluğudur.
• 19. A ilə R amil çoxluğu A çoxluğunun elementlərinin ekvivalentlik siniflərinin çoxluğudur. Təyinat: A/R.
• 20. Ekvivalentlik sinifləri (A/R faktorlar çoxluğunun elementləri) A çoxluğunun bölməsini təşkil edir. Əksinə. A çoxluğunun istənilən bölməsi ekvivalentlik sinifləri müəyyən edilmiş bölmənin blokları ilə üst-üstə düşən R ekvivalentlik münasibətinə uyğundur. Fərqli. A dəstinin hər bir elementi A/R-dən bəzi ekvivalentlik sinfinə düşür. Ekvivalentlik sinifləri ya kəsişmir, ya da üst-üstə düşür.
• 21. A çoxluğundakı qabaqcadan sifariş A üzərində refleksiv və keçid əlaqəsidir.
• 22. A çoxluğunda qismən nizam A üzərində refleksiv, keçid və antisimmetrik münasibətdir.
• 23. Xətti nizam A çoxluğunda dixotomiya xassəsini təmin edən A üzərində refleksiv, keçid və antisimmetrik münasibətdir.

A=(1, 2, 3), B=(a, b) olsun. Dekart hasilini yazaq: AB = ( (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) ). Bu Kartezian hasilinin hər hansı alt çoxluğunu götürün: R = ( (1, a), (1, b), (2, b) ). Onda R A və B çoxluqlarında ikili münasibətdir.

Bu əlaqə funksiya olacaqmı? İki şərtin yerinə yetirilməsini yoxlayaq 9a) və 9b). R münasibətinin oblastı R = (1, 2) (1, 2, 3) çoxluğudur, yəni birinci şərt təmin olunmur, ona görə də R-ə cütlərdən birini əlavə etmək lazımdır: (3, a) və ya (3, b). Hər iki cüt əlavə olunarsa, ikinci şərt təmin edilməyəcək, çünki ab. Eyni səbəbdən (1, a) və ya (1, b) cütlərindən biri R-dən atılmalıdır. Beləliklə, R = ( (1, a), (2, b), (3, b) ) əlaqəsi funksiyadır. Qeyd edək ki, R 1-1 funksiyası deyil.

Verilmiş A və B çoxluqlarında aşağıdakı əlaqələr də funksiyalar olacaq: ( (1, a), (2, a), (3, a) ), ( (1, a), (2, a), ( 3, b ) ), ( (1, b), (2, b), (3, b) ) və s.

A=(1, 2, 3) olsun. A çoxluğundakı əlaqəyə misal olaraq R = ( (1, 1), (2, 1), (2, 3) ). A çoxluğundakı funksiyaya misal olaraq f = ( (1, 1), (2, 1), (3, 3) ).

Problemin həlli nümunələri

1. R = ((x, y) | x, y D və x+y0) üçün R, R, R1, RR, RR1, R1R tapın.

Əgər (x, y)R, onda x və y bütün həqiqi ədədlərdən keçir. Buna görə də R = R = D.

Əgər (x, y)R, onda x+y0, deməli, y+x0 və (y, x)R. Buna görə də R1=R.

İstənilən xD, yD üçün z=-|max(x, y)|-1, sonra x+z0 və z+y0 götürürük, yəni. (x, z)R və (z, y)R. Buna görə də RR = RR1 = R1R = D2.

2. Hansı ikili münasibətlər üçün R R1= R doğrudur?

Qoy RAB. İki hal mümkündür:

• (1) AB. Gəlin xAB-ı götürək. Sonra (x, x)R (x, x)R1 (x, x)R (x, x)(AB) R (x, x)R. Ziddiyyət.
• (2) AB=. R1BA və RAB olduğundan, onda R1= R= . R1 =-dən belə çıxır ki, R =. R =-dən belə çıxır ki, R=AB. Ziddiyyət.

Deməli, əgər A və B, onda belə R münasibətləri mövcud deyildir.

3. Həqiqi ədədlərin D çoxluğunda R münasibətini aşağıdakı kimi təyin edirik: (x, y)R (x-y) rasional ədəddir. R-nin ekvivalent olduğunu sübut edin.

Refleksivlik:

İstənilən xD üçün x-x=0 rasional ədəddir. Çünki (x, x)R.

Simmetriya:

Əgər (x, y)R, onda x-y =. Onda y-x=-(x-y)=- rasional ədəddir. Buna görə də (y, x)R.

Keçidlilik:

Əgər (x, y)R, (y, z)R, onda x-y = və y-z = olar. Bu iki tənliyi əlavə edərək, əldə edirik ki, x-z = + rasional ədəddir. Buna görə də (x, z)R.

Beləliklə, R ekvivalentdir.

4. D2 müstəvisinin bölməsi a) şəkildə göstərilən bloklardan ibarətdir. Bu bölməyə uyğun olan R ekvivalentlik əlaqəsini və ekvivalentlik siniflərini yazın.

b) və c) üçün oxşar problem.

a) iki nöqtə y=2x+b şəklində düz xətt üzərində yerləşirsə ekvivalentdir, burada b istənilən həqiqi ədəddir.

b) iki nöqtə (x1,y1) və (x2,y2) ekvivalentdir, əgər (x1-in tam hissəsi x2-nin tam hissəsinə bərabərdir) və (y1-in tam hissəsi y2-nin tam hissəsinə bərabərdir).

c) Özünüz qərar verin.

Müstəqil həll üçün tapşırıqlar

• 1. Sübut edin ki, f A-dan B-yə, g isə B-dən C-yə funksiyadırsa, fg A-dan C-yə funksiyadır.
• 2. A və B müvafiq olaraq m və n elementdən ibarət sonlu çoxluqlar olsun.

A və B çoxluqlarının elementləri arasında neçə binar əlaqə mövcuddur?

A-dan B-yə qədər neçə funksiya var?

A-dan B-yə qədər neçə 1-1 funksiya var?

Hansı m və n üçün A və B arasında bir-bir uyğunluq var?

3. Sübut edin ki, f hər hansı A və B üçün f(AB)=f(A)f(B) şərtini ödəyir və yalnız f 1-1 funksiyası olduqda.

Çoxluqda müəyyən edilmiş əlaqə bir sıra xüsusiyyətlərə malik ola bilər, yəni:

2. Refleksivlik

Tərif. Münasibət R setdə X hər bir elementə refleksiv deyilir X dəstləri X münasibətdədir RÖzümlə.

Simvollardan istifadə edərək bu əlaqəni aşağıdakı kimi yazmaq olar:

Rəks etdirən şəkildə X Û(" XÎ X) x R x

Misal. Seqmentlər çoxluğunda bərabərlik əlaqəsi refleksivdir, çünki hər seqment özünə bərabərdir.

Refleksiv əlaqə qrafiki bütün təpələrdə döngələrə malikdir.

2. Antirefleks

Tərif. Münasibət R setdə X element yoxdursa antirefleksiv adlanır X dəstləri X münasibətdə deyil RÖzümlə.

R antirefleksiv olaraq X Û(" XÎ X)

Misal.Əlaqə "birbaşa X xəttinə perpendikulyar saat» müstəvidə xətlər dəsti antirefleksivdir, çünki təyyarənin heç bir düz xətti özünə perpendikulyar deyil.

Antirefleksiv əlaqənin qrafikində heç bir döngə yoxdur.

Qeyd edək ki, nə refleksiv, nə də antirefleksiv münasibətlər var. Məsələn, "nöqtə" əlaqəsini nəzərdən keçirin X bir nöqtəyə simmetrikdir saat» təyyarənin nöqtələr çoxluğunda.

Nöqtə X bir nöqtəyə simmetrikdir X- doğru; nöqtə saat bir nöqtəyə simmetrikdir saat- yalandır, ona görə də biz müstəvinin bütün nöqtələrinin özlərinə simmetrik olduğunu iddia edə bilmərik və müstəvinin heç bir nöqtəsinin özünə simmetrik olmadığını iddia edə bilmərik.

3. Simmetriya

Tərif. Münasibət R setdə X elementin olması faktından, əgər simmetrik adlanır X münasibətdədir R elementi ilə saat, ondan belə çıxır ki, element saat münasibətdədir R elementi ilə X.

R simmetrik X Û(" X, saatÎ X) x R y Þ y R x

Misal.Əlaqə "birbaşa X xətti keçir saat təyyarənin düz xətləri çoxluğunda” simmetrikdir, çünki düz olsa X xətti keçir saat, sonra düz xətt saat xətti keçməlidir X.

Bir nöqtədən hər bir ox ilə birlikdə simmetrik əlaqə qrafiki X tam olaraq saat eyni nöqtələri birləşdirən ox olmalıdır, lakin əks istiqamətdə.

4. Asimmetriya

Tərif. Münasibət R setdə X elementləri yoxdursa, asimmetrik adlanır X, saatçoxlarından X elementi ola bilməz X münasibətdədir R elementi ilə saat və element saat münasibətdədir R elementi ilə X.

R asimmetrik X Û(" X, saatÎ X) x R y Þ

Misal. münasibət" X < saat» asimmetrik olaraq, çünki hər hansı bir cüt element üçün X, saat eyni zamanda olduğunu söyləmək olmaz X < saat və saat<X.

Asimmetrik əlaqənin qrafikində döngələr yoxdur və qrafikin iki təpəsi oxla birləşdirilirsə, bu ox yalnız birdir.

5. Antisimmetriya

Tərif. Münasibət R setdə X ki, əgər antisimmetrik adlanır X ilə münasibətdədir saat, a saat ilə münasibətdədir X bunu izləyir X = y.

R antisimmetrik X Û(" X, saatÎ X) x R y Ù y R xÞ x = y

Misal. münasibət" X£ saat» antisimmetrikdir, çünki şərtlər X£ saat və saat£ X yalnız zaman eyni vaxtda icra edilir X = y.

Antisimmetrik əlaqənin qrafiki döngələrə malikdir və qrafikin iki təpəsi oxla birləşdirilirsə, bu ox yalnız birdir.

6. Keçidlilik

Tərif. Münasibət R setdə X hər hansı element üçün əgər keçid adlanır X, saat, zçoxlarından X nədən X ilə münasibətdədir saat, a saat ilə münasibətdədir z bunu izləyir X ilə münasibətdədir z.

R keçidli X Û(" X, saat, zÎ X) x R y Ù at RzÞ x Rz

Misal. münasibət" Xçoxsaylı saat» keçidlidir, çünki birinci ədəd ikincinin, ikincisi isə üçüncünün qatıdırsa, birinci ədəd üçüncünün qatıdır.

Hər bir ox cütü ilə keçid əlaqəsinin qrafiki Xüçün saat və dən saatüçün z gedən ox ehtiva edir Xüçün z.

7. Bağlantı

Tərif. Münasibət R setdə X hər hansı element üçün əgər bağlı deyilir X, saatçoxlarından x x ilə münasibətdədir saat və ya saat ilə münasibətdədir X və ya x = y.

Rəlaqədar X Û(" X, saat, zÎ X) x R y Ú at RzÚ X= saat

Başqa sözlə: münasibət R setdə X hər hansı fərqli elementlər üçün əgər bağlı adlanır X, saatçoxlarından x x ilə münasibətdədir saat və ya saat ilə münasibətdədir X və ya x = y.

Misal. münasibət" X< saat» bağlıdır, çünki hansı real ədədləri götürsək də, onlardan birinin digərindən böyük olacağı və ya bərabər olacağı əmindir.

Münasibətlər qrafikində bütün təpələr oxlarla birləşdirilir.

Misal. Hansı xüsusiyyətləri yoxlayın

münasibət" X - bölücü saat» setdə müəyyən edilmişdir

X= {2; 3; 4; 6; 8}.

1) bu münasibət refleksivdir, çünki verilmiş çoxluqdan hər bir ədəd özünə böləndir;

2) bu münasibət antireflekslik xüsusiyyətinə malik deyildir;

3) simmetriya xassəsi ödənilmir, çünki məsələn, 2 4-ün bölənidir, lakin 4 2-nin bölməsi deyil;

4) bu münasibət antisimmetrikdir: iki ədəd eyni vaxtda bir-birinin bölənləri ola bilər, yalnız bu ədədlər bərabər olduqda;

5) münasibət keçidlidir, çünki əgər bir ədəd ikincinin, ikincisi isə üçüncünün bölənidirsə, onda birinci ədəd mütləq üçüncünün bölməsi olacaqdır;

6) münasibətin əlaqə xassəsi yoxdur, çünki məsələn, qrafikdəki 2 və 3 rəqəmləri oxla birləşdirilmir, çünki iki fərqli ədəd 2 və 3 bir-birinin bölənləri deyil.

Beləliklə, bu əlaqə refleksivlik, asimmetriya və keçid xüsusiyyətlərinə malikdir.

§ 3. Ekvivalentlik əlaqəsi.
Ekvivalentlik münasibətinin çoxluğun siniflərə bölünməsi ilə əlaqəsi

Tərif. Münasibət R setdə X refleksiv, simmetrik və keçidli olarsa, ekvivalentlik əlaqəsi adlanır.

Misal. Münasibətlərə fikir verin" X sinif yoldaşı saat» pedaqoji fakültənin tələbələri toplusu üzrə. Onun xüsusiyyətləri var:

1) refleksivlik, çünki hər bir şagird özü üçün sinif yoldaşıdır;

2) simmetriya, çünki tələbə olsa X saat, sonra tələbə saat tələbənin sinif yoldaşıdır X;

3) keçid qabiliyyəti, çünki tələbə olsa X- sinif yoldaşı saat, və tələbə saat- sinif yoldaşı z, sonra tələbə X tələbənin sinif yoldaşı olmaq z.

Beləliklə, bu əlaqə reflekslik, simmetriya və keçid xüsusiyyətlərinə malikdir və buna görə də ekvivalentlik əlaqəsidir. Eyni zamanda, pedaqoji fakültənin tələbələr toplusunu eyni kursa daxil olan tələbələrdən ibarət alt qruplara bölmək olar. 5 alt çoxluq alırıq.

Ekvivalentlik münasibəti də, məsələn, paralel xətlərin münasibəti, fiqurların bərabərliyi münasibətidir. Hər bir belə münasibət çoxluğun siniflərə bölünməsi ilə bağlıdır.

Teorem. Setdə olarsa X ekvivalentlik əlaqəsi verildikdə, o, bu çoxluğu qoşa ayrı-ayrı alt çoxluqlara (ekvivalentlik siniflərinə) ayırır.

Əks müddəa da doğrudur: əgər çoxluqda hər hansı əlaqə müəyyən edilibsə X, bu çoxluğun siniflərə bölməsini yaradır, onda ekvivalentlik əlaqəsidir.

Misal. Setdə X= (1; 2; 3; 4; 5; 6; 7; 8) "3-ə bölündükdə eyni qalığa sahib olmaq" münasibəti verilir. Ekvivalent münasibətdirmi?

Bu əlaqənin qrafikini quraq:

Bu əlaqə reflekslik, simmetriya və keçid xüsusiyyətlərinə malikdir, buna görə də ekvivalentlik əlaqəsidir və çoxluğu parçalayır. X ekvivalentlik siniflərinə. Hər bir ekvivalentlik sinfi 3-ə bölündükdə eyni qalığı verən ədədlərə sahib olacaq: X 1 = {3; 6}, X 2 = {1; 4; 7}, X 3 = {2; 5; 8}.

Hesab olunur ki, ekvivalentlik sinfi onun hər hansı bir nümayəndəsi tərəfindən müəyyən edilir, yəni. bu sinfin ixtiyari elementi. Beləliklə, bərabər kəsrlər sinfi bu sinfə aid olan hər hansı bir kəsri təyin etməklə müəyyən edilə bilər.

Riyaziyyatın ilkin kursunda ekvivalentlik münasibətləri də baş verir, məsələn, “ifadələr X və saat eyni ədədi qiymətlərə malikdir", "rəqəm X rəqəmə bərabərdir saat».

Bəzi boş olmayan A çoxluğu verilsin və R A çoxluğunun Kartezian kvadratının bəzi alt çoxluğu olsun: R  A  A.

münasibət R setdə VƏçoxluğun alt çoxluğu adlanır VƏ VƏ(və ya VƏ 2 ). Beləliklə münasibət gəliş sahəsinin gediş sahəsi ilə eyni olduğu xüsusi uyğunlaşma halı var. Uyğunluq kimi, əlaqə də hər iki elementin eyni çoxluğa aid olduğu sıralı cütdür.

R  A  A = ((a, b) | aA, bA, (a, b)R).

Bu faktdır ki ( a, b)R aşağıdakı kimi yazıla bilər: a R b. Oxuyur: " a R ilə münasibətdədir b"və ya "arasında a və b R əlaqəsi var. Əks halda yazın: a, b)R və ya aR b.

Rəqəmlər çoxluğundakı münasibətlərə misal olaraq aşağıdakıları göstərmək olar: "=", "", "", ">" və s. İstənilən şirkətin işçiləri toplusunda “rəis olmaq” və ya “tabe olmaq”, qohumlar qrupunda “əcdad olmaq”, “qardaş olmaq”, “ata olmaq” münasibəti. ” və s.

Nəzərdən keçirilən əlaqələr binar (iki yerli) homojen əlaqələr adlanır və riyaziyyatda ən mühümdür. Onlarla yanaşı, onlar da hesab edirlər P-yerli və ya P-ar münasibətləri:

R  A  A … A = A n = ((a 1 , a 2 ,…a n) | a 1 , a 2 ,…a n  A).

Münasibət yazışmaların xüsusi bir halı olduğundan, onları təyin etmək üçün əvvəllər təsvir edilmiş bütün üsullardan istifadə edilə bilər.

Aydındır ki, nisbəti matris üsulu ilə təyin etməklə kvadrat matris əldə edirik.

Əlaqənin həndəsi (qrafik) təsviri ilə aşağıdakıları ehtiva edən bir diaqram alırıq:

çoxluğun elementlərinə uyğun gələn nöqtələr və ya dairələrlə işarələnmiş təpələr;

və binar münasibətlərə daxil olan elementlərin cütlərinə uyğun gələn qövslər (xətlər) elementə uyğun gələn təpədən yönəldilmiş oxları olan xətlərlə işarələnir. a elementə uyğun gələn yuxarıya b , əgər a Rb .

Belə fiqur ikili əlaqənin yönəldilmiş qrafiki (və ya diqrafı) adlanır.

Tapşırıq 4.9.1 . Nisbət "M = (1, 2, 3, 4) çoxluğunda bölən olmaq" verilə bilər. matris:

sadalama: R = ((1.1), (1.2), (1.3), (1.4), (2.2), (2.4), (3.3), ((4.4 ));

həndəsi (qrafik):

1. A = (1, 2, 3, 4, 5, 6, 7) çoxluğuna aşağıdakı ikili münasibətlərə aid sıralı cütləri yazın:

R1 = ((x, y)| x, yA; x + y = 9);

R2 = ((x, y)| x, yA; x< y}.

2. X = (a, b, c, d) çoxluğunda R əlaqəsi matrislə verilir.

,

sətirlərin və sütunların sırası yazılan elementlərin sırasına uyğundur. Verilmiş münasibətə aid olan sıralı cütləri sadalayın. Qrafikdən istifadə edərək əlaqəni göstərin.

3. A = (1, 2, 3, 4) çoxluğundakı əlaqə qrafiklə göstərilmişdir. Zəruri:

R-ə aid olan sıralı cütləri sadalayın;

müvafiq matrisi yazın;

predikatlardan istifadə edərək bu əlaqəni təyin edin.

(cavab: a-b= 1).

4.10. Binar əlaqələrin əsas növləri (xassələri).

Qoy ikili əlaqə R setdə VƏ 2 : R  A  A = (( a, b) | aA, bA, ( a, b)R)

ikili əlaqə R setdə VƏ çağırdı əks etdirən, əgər varsa aA həyata keçirdi aRa, yəni ( a,a)R. Refleksiv əlaqə matrisinin əsas diaqonalı birlərdən ibarətdir. Refleksiv əlaqə qrafiki mütləq hər təpəsində döngələrə malikdir.

Nümunələr refleksiv münasibətlər: , =,  həqiqi ədədlər çoxluğunda, işçilərin çoxluğunda “rəis olmamaq”.

ikili əlaqə Rçoxluqda A adlanır antirefleksiv (refleksiv), əgər varsa aA əlaqəni saxlamır aRa, yəni ( a,a)R. Reflekssiz əlaqə matrisinin əsas diaqonalı sıfırlardan ibarətdir. Reflekssiz əlaqənin qrafikində döngələr yoxdur.

Nümunələr antirefleks əlaqələri:<, >həqiqi ədədlər çoxluğunda, xətlər çoxluğunda xətlərin perpendikulyarlığı.

ikili əlaqə R setdə A çağırdı simmetrik, əgər varsa a, bVƏ-dan aRb etməlidir bRa, yəni əgər ( a, b)R, sonra və ( b, a)R. Simmetrik nisbət matrisi əsas diaqonalına görə simmetrikdir ( σ ij = σ ji). Simmetrik əlaqənin qrafiki istiqamətləndirilməyib (kənarları oxsuz göstərilib). Buradakı hər bir təpə cütü yönləndirilməmiş kənar ilə bağlanır.

Nümunələr simmetrik münasibətlər:  həqiqi ədədlər çoxluğunda, insanlar çoxluğunda “qohum olmaq”.

ikili əlaqə R setdə A çağırdı:

antisimmetrik, əgər varsa a, bVƏ-dan aRb və bRa bunu izləyir a=b. Yəni, əgər ( a, b)R və( b, a)R, sonra bunun ardınca gəlir a=b. Əsas diaqonal boyunca antisimmetrik nisbət matrisinin hamısı 1-ə malikdir və əsas diaqonala nisbətən simmetrik yerlərdə yerləşən 1 cütü yoxdur. Başqa sözlə, hər şey σ ii=1 və əgər σ ij=1, onda mütləq σ ji=0. Antisimmetrik əlaqə qrafikinin hər təpəsində döngələr var və təpələr yalnız bir istiqamətləndirilmiş qövslə bağlanır.

Nümunələr antisimmetrik münasibətlər: , ,  həqiqi ədədlər çoxluğunda; ,  dəstlərdə;

asimmetrik, əgər varsa a, bVƏ-dan aRb uğursuzluq izlədi bRa, yəni əgər ( a, b)R, sonra ( b, a) R. Əsas diaqonal boyunca əyilmə nisbəti matrisi sıfırlara malikdir ( σ ij=0) hamısı və simmetrik bir cütləri yoxdur (əgər σ ij=1, onda mütləq σ ji=0). Asimmetrik əlaqənin qrafikində döngələr yoxdur və təpələr tək istiqamətləndirilmiş qövslə bağlanır.

Asimmetrik əlaqələrin nümunələri:<, >həqiqi ədədlər toplusunda, insanların çoxluğunda "ata olmaq".

ikili əlaqə R setdə A çağırdı keçidlinym, əgər varsa a, b, iləVƏ-dan aRb və bRa bundan irəli gəlir və aRilə. Yəni, əgər ( a, b)R və( b, ilə)R ondan belə çıxır ( a, ilə)R. Keçid əlaqə matrisi onunla xarakterizə olunur ki, əgər σ ij=1 və σ jm=1, onda mütləq σ im=1. Keçid əlaqə qrafiki elədir ki, məsələn, birinci-ikinci və ikinci-üçüncü təpələri qövslərlə birləşdirərsə, birincidən üçüncü təpəyə doğru mütləq qövslər vardır.

Nümunələr keçid əlaqələri:<, , =, >,  həqiqi ədədlər çoxluğunda; bir sıra işçilərdə "boss olmaq".

ikili əlaqə R setdə A çağırdı antitransitivnym, əgər varsa a, b, iləVƏ-dan aRb və bRa yerinə yetirilmədiyi ortaya çıxır aRilə. Yəni, əgər ( a, b)R və( b, ilə)R ondan belə çıxır ( a, ilə) R. Antikeçidli əlaqə matrisi onunla xarakterizə olunur ki, əgər σ ij=1 və σ jm=1, onda mütləq σ im=0. Antikeçid münasibətinin qrafiki belədir ki, məsələn, birinci-ikinci və ikinci-üçüncü təpələr qövslərlə birləşdirilirsə, onda birincidən üçüncü təpəyə mütləq qövs yoxdur.

Anti-keçidli münasibətlərin nümunələri: tam ədədlər çoxluğunda "paritet uyğunsuzluğu"; bir sıra işçilər üzrə "birbaşa nəzarətçi olmaq".

Münasibətin hansısa xassəsi yoxdursa, çatışmayan cütləri əlavə etməklə siz bu xassə ilə yeni münasibət əldə edə bilərsiniz. Belə itkin cütlərin dəsti deyilir bağlanması bu əmlaka münasibət. kimi təyin edin R* . Bu yolla refleksiv, simmetrik və keçidli qapanma əldə edə bilərsiniz.

Məsələ 4.10.1. A = (1, 2, 3, 4) çoxluğunda R=(( a,b)| a,bA, a+b cüt ədəd). Bu əlaqənin növünü müəyyənləşdirin.

Qərar. Bu əlaqənin matrisi:

. Aydındır ki, münasibət əks etdirən, çünki əsas diaqonal boyunca vahidlər var. O simmetrik olaraq: σ 13 = σ 31, σ 24 = σ 42. keçidlə: (1,3)R, (3,1)R və (1,1)R; (2,4)R, (4,2)R və (2,2)R və s.

Məsələ 4.10.2. A çoxluğunda hansı xüsusiyyətlər = ( a, b, c, d) ikili münasibətə malikdir R = (( a,b), (b,d), (a,d), (b,a), (b,c)}?

Qərar . Bu əlaqənin matrisini və onun qrafikini quraq:

Münasibət reflekssiz olaraq, çünki bütün σ ii= 0. Bu yox simmetrik olaraq, çünki σ 23 =1, və σ 32 =0, lakin, σ 12 =σ 21 =1. Münasibət yox keçidlə, çünki σ 12 =1, σ 23 =1 və σ 13 =0; σ 12 =1, σ 21 =1 və σ 11 =0; lakin eyni zamanda σ 12 =1, σ 24 =1 və σ 14 =1.

Tapşırıq 4.10.3. A = (1,2,3,4,5) çoxluğunda R = ((1,2), (2,3), (2,4), (4,5)) əlaqəsi verilir. Əlaqənin növünü təyin edin və R üçün aşağıdakı qapanmaları tapın:

əks etdirən;

simmetrik;

keçidli.

Qərar. Formanın heç bir elementi olmadığı üçün əlaqə əks olunmur ( a,a). Asimmetrik, çünki forma cütlərini ehtiva etmir ( a,b) və ( b,a) və bütün diaqonal elementlər 0-dır. Çünki (1,2)R, (2,3)R, lakin (1,3)R. Eynilə (2.4)R, (4.5)R və (2.5)R və s.

verilmiş münasibətin refleksiv bağlanması R * =((1,1), (2,2), (3,3), (4,4), (5,5));

simmetrik qapanma: R*=((2,1), (3,2), (4,2), (5,4));

keçid bağlanması: R*=((1,3), (1,4), (2,5)). İlkin əlaqənin və nəticədə keçidin qrafikini nəzərdən keçirin.

Müstəqil həll üçün tapşırıqlar.

1. R = ((1,1), (1,2), (1,3), (3,1), (2,3)) münasibəti verilmişdir. Onun növünü müəyyənləşdirin və refleksivlik, simmetriya və keçidlə bağlı qapaqları tapın.

2. Rus dilinin söz çoxluğu üzrə münasibət aşağıdakı kimi müəyyən edilir: a R bən azı bir ümumi hərf olduqda. A = çoxluğunda əlaqənin növünü müəyyən edin (inək, vaqon, sap, balta).

3. A = (1, 2) və B = (1, 2, 3) çoxluğunda ikili münasibətlərin nümunələrini göstərin, hansılar olacaq:

refleksiv deyil, simmetrik deyil, keçidli deyil;

refleksiv, simmetrik deyil, keçid deyil;

simmetrik, lakin refleksiv və keçid deyil;

keçid, lakin refleksiv və simmetrik deyil;

refleksiv, simmetrik, lakin keçidli deyil;

refleksiv, keçidli, lakin simmetrik deyil;

refleksiv olmayan, simmetrik, keçidli;

refleksiv, simmetrik, keçidli.