Osnove diskretne matematike.

Koncept seta. Odnos između skupova.

Skup je skup objekata koji imaju određeno svojstvo, ujedinjenih u jednu cjelinu.

Pozivaju se objekti koji čine skup elementi setovi. Da bi se određeni skup objekata mogao nazvati skupom, moraju biti ispunjeni sljedeći uslovi:

· Trebalo bi postojati pravilo po kojem je mono odrediti da li element pripada datoj kolekciji.

· Mora postojati pravilo po kojem se elementi mogu razlikovati jedan od drugog.

Skupovi se označavaju velikim slovima, a njegovi elementi malim slovima. Načini za određivanje skupova:

· Nabrajanje elemenata skupa. - za konačne skupove.

Određivanje karakterističnog svojstva .

prazan set- naziva se skup koji ne sadrži nijedan element (Ø).

Za dva skupa se kaže da su jednaka ako se sastoje od istih elemenata. , A=B

Gomila B naziva se podskup skupa I( , ako i samo ako su svi elementi skupa B pripadaju skupu A.

Na primjer: , B =>

Nekretnina:

Napomena: obično razmotrite podskup istog skupa, koji se zove univerzalni(u). Univerzalni set sadrži sve elemente.

Operacije na skupovima.

A

B

1. Udruženje 2 skupovima A i B naziva se takav skup kojem pripadaju elementi skupa A ili skupa B (elementi barem jednog od skupova).

2.prelaz 2 skupa je novi skup koji se sastoji od elemenata koji istovremeno pripadaju i prvom i drugom skupu.

br: , ,

Imovina: radnje sindikata i raskrsnica.

· Komutativnost.

Asocijativnost. ;

· Distributivni. ;

U

4.Dodatak. Ako I je podskup univerzalnog skupa U, zatim dopuna skupa I mnogo U(označeno) je skup koji se sastoji od tih elemenata skupa U, koji ne pripadaju skupu I.

Binarne relacije i njihova svojstva.

Neka bude I i AT ovo su skupovi izvedene prirode, razmotrite uređeni par elemenata (a, c) a ϵ A, c ϵ B naručeni "enkovi" mogu se uzeti u obzir.

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

Dekartov (direktan) proizvod skupova A 1, A 2, ..., A n, naziva se skup, koji se sastoji od uređenog n k oblika .

br: 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)}.

Podskupovi kartezijanskog proizvoda naziva stepenom omjera n ili enarni odnos. Ako n=2, onda razmotrite binarni odnos. Šta oni to kažu a 1, a 2 su u binarnom odnosu R, kada a 1 R a 2.

Binarna relacija na skupu M naziva se podskup direktnog proizvoda skupa n na sebi.

M× M= M 2= {(a, b)| a, b ϵ M) u prethodnom primjeru, omjer je manji na skupu M generira sljedeći skup: ((1,2);(1,3); (2,3))

Binarni odnosi imaju različita svojstva uključujući:

Refleksivnost: .

· Antirefleksivnost (nerefleksivnost): .

· Simetrija: .

· Antisimetrija: .

· Tranzitivnost: .

· Asimetrija: .

Vrste odnosa.

Relacija ekvivalencije;

· Odnos naloga.

v Refleksivna tranzitivna relacija naziva se relacija kvazi-reda.

v Refleksivna simetrična tranzitivna relacija naziva se relacija ekvivalencije.

v Refleksivna antisimetrična tranzitivna relacija naziva se (djelomična) relacija reda.

v Antirefleksivna antisimetrična tranzitivna relacija naziva se relacija strogog reda.

Definicija. Binarna relacija R naziva se podskup parova (a,b)∈R kartezijanski proizvod A×B, tj. R⊆A×B . Istovremeno, mnogi A naziva se domenom definicije relacije R, skup B naziva se domenom vrijednosti.

Oznaka: aRb (tj. a i b su u odnosu na R). /

Komentar: ako je A = B, onda se kaže da je R relacija na skupu A.

Načini specificiranja binarnih odnosa

1. Lista (nabrajanje parova) za koje je ovaj odnos zadovoljen.

2. Matrica. Binarna relacija R ∈ A × A , gdje je A = (a 1 , a 2 ,..., a n), odgovara kvadratnoj matrici reda n, u kojoj je element c ij, koji se nalazi na presjeku i -ti red i j-ti stupac, jednaka je 1 ako postoji relacija R između a i i a j, ili 0 ako je odsutna:

Relationship Properties

Neka je R relacija na skupu A, R ∈ A×A. Tada je relacija R:

refleksivno ako je Ɐ a ∈ A: a R a (glavna dijagonala matrice refleksivne relacije sadrži samo jedinice);

je antirefleksivan ako Ɐ a ∈ A: a R a (glavna dijagonala refleksivne relacijske matrice sadrži samo nule);

simetrična ako je Ɐ a , b ∈ A: a R b ⇒ b R a (matrica takve relacije je simetrična u odnosu na glavnu dijagonalu, tj. c ij c ji);

antisimetrično ako Ɐ a, b ∈ A: a R b & b R a ⇒ a = b (u matrici takve relacije nema simetričnih u odnosu na glavnu dijagonalu);

tranzitivno ako je Ɐ a, b, c ∈ A: a R b & b R c ⇒ a R c red, tj. c ij = 1, tada sve jedinice u j-tom redu (neka ove jedinice odgovaraju k e koordinatama tako da, c jk = 1) mora odgovarati jedinicama u i-tom redu u istim k koordinatama, tj. c ik = 1 (a možda i u drugim koordinatama).

Zadatak 3.1. Odrediti svojstva relacije R - "da bude djelitelj", date na skupu prirodnih brojeva.

Odluka.

omjer R = ((a,b):a djelitelj b):

refleksivan, a ne antirefleksivan, pošto se bilo koji broj dijeli bez ostatka: a/a = 1 za sve a∈N ;

nije simetričan, antisimetričan, na primjer, 2 je djelitelj 4, ali 4 nije djelitelj 2;

tranzitivno, jer ako je b/a ∈ N i c/b ∈ N, onda je c/a = b/a ⋅ c/b ∈ N, na primjer, ako je 6/3 = 2∈N i 18/6 = 3∈N , tada je 18/3 = 18/6⋅6/3 = 6∈N.

Zadatak 3.2. Odrediti svojstva relacije R - "biti brat", data na skupu ljudi.
Odluka.

Omjer R = ((a,b):a - brat od b):

nerefleksivan, antirefleksivan zbog očiglednog odsustva aRa za sve a;

nije simetrično, jer općenito postoji aRb između brata a i sestre b, ali ne i bRa;

nije antisimetrično, jer ako su a i b braća, onda su aRb i bRa, već a≠b;

prelazno, ako braćom nazivamo ljude koji imaju zajedničke roditelje (oca i majku).

Zadatak 3.3. Odrediti svojstva relacije R - "biti šef" specificirane na skupu elemenata strukture

Odluka.

Omjer R = ((a,b) : a - šef b):

• nerefleksivan, antirefleksivan, ako nema smisla u određenoj interpretaciji;
• nije simetrično, antisimetrično, jer za sve a≠b aRb i bRa nisu zadovoljeni istovremeno;
• tranzitivno, pošto ako je a glava b i b glava c, onda je a glava c.

Odredi svojstva relacije R i , definirane na skupu M i matricom, ako:

1. R 1 "imaju isti ostatak kada se podijele sa 5"; M 1 je skup prirodnih brojeva.
2. R 2 "biti jednak"; M 2 je skup prirodnih brojeva.
3. R 3 "živi u istom gradu"; M 3 skup ljudi.
4. R 4 "biti upoznat"; M 4 mnogo ljudi.
5. R 5 ((a,b):(a-b) - paran; M 5 skup brojeva (1,2,3,4,5,6,7,8,9).
6. R 6 ((a,b):(a+b) - paran; M 6 skup brojeva (1,2,3,4,5,6,7,8,9).
7. R 7 ((a,b):(a+1) - djelitelj (a+b)) ; M 7 - set (1,2,3,4,5,6,7,8,9).
8. R 8 ((a,b):a - djelitelj (a+b),a≠1); M 8 je skup prirodnih brojeva.
9. R 9 "biti sestra"; M 9 - puno ljudi.
10. R 10 "biti ćerka"; M 10 - puno ljudi.

Operacije nad binarnim odnosima

Neka su R 1 , R 1 relacije definirane na skupu A .

udruženje R 1 ∪ R 2: R 1 ∪ R 2 = ((a,b) : (a,b) ∈ R1 ili (a,b) ∈ R2) ;

raskrsnica R 1 ∩ R 2: R 1 ∩ R 2 = ((a,b) : (a,b) ∈ R1 i (a,b) ∈ R2) ;

razlika R 1 \ R 2: R 1 \ R 2 = ((a,b) : (a,b) ∈ R 1 i (a,b) ∉ R 2 ) ;

univerzalni odnos U: = ((a;b)/a ∈ A & b ∈ A). ;

dodatak R 1 U \ R 1 , gdje je U = A × A;

identitetski odnos I: = ((a;a) / a ∈ A);

obrnuti odnos R-1 1 :R-1 1 = ((a,b) : (b,a) ∈ R 1 );

kompozicija R 1 º R 2: R 1 º R 2: = ((a,b) / a ∈ A&b ∈ B& ∃ c ∈ C: aR 1 c & c R 2 b), gdje je R 1 ⊂ A × C i R 2 ⊂ C×B;

Definicija. Stepen odnosa R na skupu A je njegova kompozicija sa samim sobom.

Oznaka:

Definicija. Ako je R ⊂ A × B, tada se zove R º R -1 jezgro relacije R .

Teorema 3.1. Neka je R ⊂ A × A relacija definirana na skupu A.

1. R je refleksivan ako i samo ako (u daljem tekstu se koristi znak ⇔) kada je I ⊂ R.
2. R je simetričan ⇔ R = R -1 .
3. R je tranzitivan ⇔ R º R ⊂ R
4. R je antisimetričan ⇔ R ⌒ R -1 ⊂ I .
5. R je antirefleksivan ⇔ R ⌒ I = ∅ .

Zadatak 3.4 . Neka je R relacija između skupova (1,2,3) i (1,2,3,4) datih nabrajanjem parova: R = ((1,1), (2,3), (2, 4), (3.1), (3.4)). Osim toga, S je relacija između skupova S = ((1,1), (1,2), (2,1), (3,1), (4,2)). Izračunajte R -1 , S -1 i S º R. Provjerite da li je (S º R) -1 = R -1 , S -1 .

Odluka.
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 ) -jedan .

Zadatak 3.5 . Neka je R relacija "...roditelj...", a S relacija "...brat..." na skupu svih ljudi. Dajte kratak verbalni opis odnosa:

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

Odluka.

R -1 - relacija "...dijete ...";

S -1 - odnos "...brat ili sestra...";

R º S - relacija "... roditelj ...";

S -1 º R -1 - relacija "... dijete ..."

R º R - odnos "...baka ili djed..."

Zadaci za samostalno rješavanje

1) Neka je R relacija "...otac...", a S relacija "...sestra..." na skupu svih ljudi. Dajte verbalni opis odnosa:

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

2) Neka je R relacija "...brat...", a S relacija "...majka..." na skupu svih ljudi. Dajte verbalni opis odnosa:

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

3) Neka je R relacija "...djed...", a S relacija "...sin..." na skupu svih ljudi. Dajte verbalni opis odnosa:

4) Neka je R relacija “...ćerka...”, a S relacija “...baka...” na skupu svih ljudi. Dajte verbalni opis odnosa:

5) Neka je R relacija "...nećakinja...", a S relacija "...otac..." na skupu svih ljudi. Dajte verbalni opis odnosa:

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

6) Neka je R relacija "sestra..." i S relacija "majka..." na skupu svih ljudi. Dajte verbalni opis odnosa:

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

7) Neka je R relacija “...majka...”, a S relacija “...sestra...” na skupu svih ljudi. Dajte verbalni opis odnosa:

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

8) Neka je R relacija “...sin...”, a S relacija “...djed...” na skupu svih ljudi. Dajte verbalni opis odnosa:

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

9) Neka je R relacija “...sestra...”, a S relacija “...otac...” na skupu svih ljudi. Dajte verbalni opis odnosa:

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

10) Neka je R relacija “...majka...”, a S relacija “...brat...” na skupu svih ljudi. Dajte verbalni opis odnosa:

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

Definicije

• 1. Binarna relacija između elemenata skupova A i B je bilo koji podskup kartezijanskog proizvoda RAB, RAA.
• 2. Ako je A=B, onda je R binarna relacija na A.
• 3. Oznaka: (x, y)R xRy.
• 4. Domen binarne relacije R je skup R = (x: postoji y takvo da (x, y)R).
• 5. Opseg binarne relacije R je skup R = (y: postoji x takav da (x, y)R).
• 6. Komplement binarne relacije R između elemenata A i B je skup R = (AB) R.
• 7. Inverzna relacija za binarnu relaciju R je skup R1 = ((y, x) : (x, y)R).
• 8. Proizvod relacija R1AB i R2BC je relacija R1 R2 = ((x, y) : postoji zB takav da (x, z)R1 i (z, y)R2).
• 9. Relacija f se naziva funkcijom od A do B ako su ispunjena dva uslova:
  • a) f \u003d A, f B
  • b) za sve x, y1, y2, činjenica da (x, y1)f i (x, y2)f implicira y1=y2.
• 10. Relacija f naziva se funkcija od A do B ako je u prvom paragrafu f = A, f = B.
• 11. Oznaka: (x, y)f y = f(x).
• 12. Funkcija identiteta iA: AA je definirana na sljedeći način: iA(x) = x.
• 13. Funkcija f se naziva 1-1-funkcija ako za bilo koje x1, x2, y činjenica da je y = f(x1) i y = f(x2) implicira x1=x2.
• 14. Funkcija f: AB obavlja korespondenciju jedan-na-jedan između A i B ako je f = A, f = B i f je funkcija 1-1.
• 15. Svojstva binarne relacije R na skupu A:
  • - refleksivnost: (x, x)R za sve xA.
  • - nerefleksivnost: (x, x)R za sve xA.
  • - simetrija: (x, y)R (y, x)R.
  • - antisimetrija: (x, y)R i (y, x)R x=y.
  • - tranzitivnost: (x, y)R i (y, z)R (x, z)R.
  • - dihotomija: ili (x, y)R ili (y, x)R za sve xA i yA.
• 16. Skupovi A1, A2, ..., Ar iz P(A) čine particiju skupa A ako
• - Ai , i = 1, ..., r,
• - A = A1A2...Ar,
• - AiAj = , i j.

Podskupovi Ai , i = 1, ..., r, nazivaju se particijski blokovi.

• 17. Ekvivalencija na skupu A je refleksivna, tranzitivna i simetrična relacija na A.
• 18. Klasa ekvivalencije elementa x po ekvivalentnosti R je skup [x]R=(y: (x, y)R).
• 19. Faktorski skup A po R je skup klasa ekvivalencije elemenata skupa A. Oznaka: A/R.
• 20. Klase ekvivalencije (elementi faktorskog skupa A/R) čine particiju skupa A. Obrnuto. Bilo koja particija skupa A odgovara relaciji ekvivalencije R čije se klase ekvivalencije poklapaju sa blokovima navedene particije. Drugačije. Svaki element skupa A spada u neku klasu ekvivalencije iz A/R. Klase ekvivalencije ili se ne sijeku ili se poklapaju.
• 21. Prednaredba na skupu A je refleksivna i tranzitivna relacija na A.
• 22. Parcijalni poredak na skupu A je refleksivna, tranzitivna i antisimetrična relacija na A.
• 23. Linearni poredak na skupu A je refleksivna, tranzitivna i antisimetrična relacija na A koja zadovoljava svojstvo dihotomije.

Neka je A=(1, 2, 3), B=(a, b). Napišimo kartezijanski proizvod: AB = ( (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) ). Uzmite bilo koji podskup ovog kartezijanskog proizvoda: R = ( (1, a), (1, b), (2, b) ). Tada je R binarna relacija na skupovima A i B.

Hoće li ova relacija biti funkcija? Provjerimo ispunjenost dva uslova 9a) i 9b). Domen relacije R je skup R = (1, 2) (1, 2, 3), odnosno prvi uslov nije zadovoljen, pa se jedan od parova mora dodati R: (3, a) ili (3, b). Ako se dodaju oba para, onda drugi uslov neće biti zadovoljen, jer ab. Iz istog razloga, jedan od parova (1, a) ili (1, b) mora biti ispušten iz R. Dakle, relacija R = ( (1, a), (2, b), (3, b) ) je funkcija. Imajte na umu da R nije funkcija 1-1.

Na datim skupovima A i B sljedeće relacije će također biti funkcije: ( (1, a), (2, a), (3, a) ), ( (1, a), (2, a), ( 3, b ), ( (1, b), (2, b), (3, b) ) itd.

Neka je A=(1, 2, 3). Primjer relacije na skupu A je R = ( (1, 1), (2, 1), (2, 3) ). Primjer funkcije na skupu A je f = ( (1, 1), (2, 1), (3, 3) ).

Primjeri rješavanja problema

1. Pronađite R, R, R1, RR, RR1, R1R za R = ((x, y) | x, y D i x+y0).

Ako (x, y)R, tada x i y prolaze kroz sve realne brojeve. Stoga je R = R = D.

Ako je (x, y)R, onda je x+y0, dakle y+x0 i (y, x)R. Stoga R1=R.

Za bilo koje xD, yD uzimamo z=-|max(x, y)|-1, zatim x+z0 i z+y0, tj. (x, z)R i (z, y)R. Stoga RR = RR1 = R1R = D2.

2. Za koje je binarne relacije R R1= R tačno?

Neka RAB. Moguća su dva slučaja:

• (1) AB. Uzmimo xAB. Tada (x, x)R (x, x)R1 (x, x)R (x, x)(AB) R (x, x)R. Kontradikcija.
• (2) AB=. Pošto su R1BA i RAB, onda je R1= R= . Iz R1 = slijedi da je R = . Iz R = slijedi da je R=AB. Kontradikcija.

Dakle, ako su A i B, onda takvi odnosi R ne postoje.

3. Na skupu D realnih brojeva definišemo relaciju R na sljedeći način: (x, y)R (x-y) je racionalan broj. Dokažite da je R ekvivalent.

Refleksivnost:

Za bilo koji xD x-x=0 je racionalan broj. Jer (x, x)R.

simetrija:

Ako je (x, y)R, onda je x-y = . Tada je y-x=-(x-y)=- racionalan broj. Stoga (y, x)R.

tranzitivnost:

Ako je (x, y)R, (y, z)R, onda je x-y = i y-z =. Sabiranjem ove dvije jednačine dobijamo da je x-z = + racionalan broj. Prema tome (x, z)R.

Stoga je R ekvivalent.

4. Pregrada ravni D2 sastoji se od blokova prikazanih na slici a). Zapišite relaciju ekvivalencije R koja odgovara ovoj particiji i klasama ekvivalencije.

Sličan problem za b) i c).

a) dvije tačke su ekvivalentne ako leže na pravoj liniji oblika y=2x+b, gdje je b bilo koji realan broj.

b) dvije tačke (x1,y1) i (x2,y2) su ekvivalentne ako je (cijeli dio x1 jednak cijelom dijelu x2) i (cijeli dio y1 jednak je cijelom broju y2).

c) Odlučite sami.

Zadaci za samostalno rješavanje

• 1. Dokažite da ako je f funkcija od A do B i g funkcija od B do C, onda je fg funkcija od A do C.
• 2. Neka su A i B konačni skupovi koji se sastoje od m odnosno n elemenata.

Koliko binarnih relacija postoji između elemenata skupova A i B?

Koliko funkcija ima od A do B?

Koliko 1-1 funkcija ima od A do B?

Za koje m i n postoji korespondencija jedan prema jedan između A i B?

3. Dokažite da f zadovoljava uslov f(AB)=f(A)f(B) za bilo koje A i B ako i samo ako je f funkcija 1-1.

Relacija definirana na skupu može imati niz svojstava, i to:

2. Refleksivnost

Definicija. Stav R na setu X naziva se refleksivnim ako svaki element X setovi X je u vezi R Sa sobom.

Koristeći simbole, ovaj odnos se može napisati na sljedeći način:

R refleksivno na X Û(" XÎ X) x R x

Primjer. Odnos jednakosti na skupu segmenata je refleksivan, jer svaki segment je jednak sam sebi.

Reflektivni graf relacija ima petlje na svim vrhovima.

2. Antirefleksivnost

Definicija. Stav R na setu X naziva se antirefleksivnim ako nema elementa X setovi X ne u odnosu R Sa sobom.

R antirefleksno uključeno X Û(" XÎ X)

Primjer. Odnos „direktan X okomito na liniju at» na skupu linija u ravni je antirefleksivan, jer nijedna ravna linija nije okomita na samu sebe.

Graf antirefleksne relacije ne sadrži petlje.

Imajte na umu da postoje odnosi koji nisu ni refleksivni ni antirefleksivni. Na primjer, razmotrite relaciju "tačka X simetrično do tačke at» na skupu tačaka ravni.

Dot X simetrično do tačke X- istinito; dot at simetrično do tačke at- je lažno, dakle, ne možemo tvrditi da su sve tačke ravni simetrične same sebi, niti možemo tvrditi da nijedna tačka ravni nije simetrična sama sebi.

3. Simetrija

Definicija. Stav R na setu X naziva se simetričnim ako, iz činjenice da je element X je u vezi R sa elementom at, slijedi da je element at je u vezi R sa elementom X.

R simetrično X Û(" X, atÎ X) x R y Þ y R x

Primjer. Odnos „direktan X prelazi liniju at na skupu pravih ravni” je simetrična, jer ako je ravno X prelazi liniju at, zatim prava linija at mora preći liniju X.

Graf simetričnih odnosa zajedno sa svakom strelicom iz tačke X upravo at treba da sadrži strelicu koja povezuje iste tačke, ali u suprotnom smjeru.

4. Asimetrija

Definicija. Stav R na setu X naziva se asimetričnim ako nema elemenata X, at od mnogih X ne može se desiti da element X je u vezi R sa elementom at i element at je u vezi R sa elementom X.

R asimetrično X Û(" X, atÎ X) x R y Þ

Primjer. stav " X < at» asimetrično, jer za bilo koji par elemenata X, at ne može se reći da je u isto vrijeme X < at i at<X.

Graf asimetrične relacije nema petlje, a ako su dva vrha grafa povezana strelicom, onda je ova strelica samo jedna.

5. Antisimetrija

Definicija. Stav R na setu X se naziva antisimetričnim ako, iz činjenice da X je u vezi sa at, a at je u vezi sa X sledi to X = y.

R antisimetrično X Û(" X, atÎ X) x R y Ù y R xÞ x = y

Primjer. stav " X£ at» je antisimetrično, jer uslovima X£ at i at£ X se izvršavaju u isto vrijeme samo kada X = y.

Graf antisimetrične relacije ima petlje, a ako su dva vrha grafa povezana strelicom, onda je ova strelica samo jedna.

6. Tranzitivnost

Definicija. Stav R na setu X naziva se tranzitivnim ako za bilo koji element X, at, z od mnogih X iz onoga što X je u vezi sa at, a at je u vezi sa z sledi to X je u vezi sa z.

R tranzitivan X Û(" X, at, zÎ X) x R y Ù u RzÞ x Rz

Primjer. stav " X višestruko at» je tranzitivan, jer ako je prvi broj višekratnik drugog, a drugi višekratnik trećeg, tada je prvi broj višekratnik trećeg.

Graf tranzitivne relacije sa svakim parom strelica iz X to at i od at to z sadrži strelicu koja ide od X to z.

7. Povezivanje

Definicija. Stav R na setu X naziva se povezano ako za bilo koji element X, at od mnogih x x je u vezi sa at ili at je u vezi sa X ili x = y.

R povezan X Û(" X, at, zÎ X) x R y Ú u RzÚ X= at

Drugim riječima: odnos R na setu X se naziva povezanim ako za bilo koje različite elemente X, at od mnogih x x je u vezi sa at ili at je u vezi sa X ili x = y.

Primjer. stav " X< at» je povezan, jer bez obzira koje realne brojeve uzmemo, jedan od njih je sigurno veći od drugog ili su jednaki.

Na grafu relacija svi vrhovi su povezani strelicama.

Primjer. Provjerite koja svojstva

stav " X - razdjelnik at» definisano na setu

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

1) ovaj odnos je refleksivan, jer svaki broj iz datog skupa je sam po sebi djelitelj;

2) ovaj odnos nema svojstvo antirefleksivnosti;

3) svojstvo simetrije nije zadovoljeno, jer na primjer, 2 je djelitelj od 4, ali 4 nije djelitelj od 2;

4) ova relacija je antisimetrična: dva broja mogu istovremeno biti djelitelji jedan drugog samo ako su ti brojevi jednaki;

5) relacija je tranzitivna, pošto ako je jedan broj djelitelj drugog, a drugi je djelitelj trećeg, tada će prvi broj nužno biti djelitelj trećeg;

6) relacija nema svojstvo povezanosti, jer na primjer, brojevi 2 i 3 na grafu nisu povezani strelicom, jer dva različita broja 2 i 3 nisu djelitelji jedan drugog.

Dakle, ova relacija ima svojstva refleksivnosti, asimetrije i tranzitivnosti.

§ 3. Relacija ekvivalencije.
Povezanost relacije ekvivalencije sa podjelom skupa na klase

Definicija. Stav R na setu X se naziva relacija ekvivalencije ako je refleksivna, simetrična i tranzitivna.

Primjer. Razmotrite odnos" X drug iz razreda at» na skupu studenata pedagoškog fakulteta. Ima svojstva:

1) refleksivnost, pošto svaki učenik je sam sebi drug iz razreda;

2) simetrija, jer ako student X at, zatim student at je student iz razreda X;

3) tranzitivnost, jer ako student X- drugarica iz razreda at, i student at- drugarica iz razreda z, zatim student X biti učenik iz razreda z.

Dakle, ova relacija ima svojstva refleksivnosti, simetrije i tranzitivnosti, te je stoga relacija ekvivalencije. Istovremeno, skup studenata pedagoškog fakulteta može se podijeliti na podskupove koje čine studenti upisani na isti predmet. Dobijamo 5 podskupova.

Relacija ekvivalencije je također, na primjer, odnos paralelnih pravih, odnos jednakosti figura. Svaka takva relacija povezana je sa podjelom skupa na klase.

Teorema. Ako je na setu X ako je data relacija ekvivalencije, onda ovaj skup dijeli na parno disjunktne podskupove (klase ekvivalencije).

Obrnuti iskaz je također istinit: ako je bilo koja relacija definirana na skupu X, generiše particiju ovog skupa na klase, onda je to relacija ekvivalencije.

Primjer. Na setu X= (1; 2; 3; 4; 5; 6; 7; 8) data je relacija "imati isti ostatak kada se podijeli sa 3". Da li je to relacija ekvivalencije?

Napravimo graf ove veze:

Ova relacija ima svojstva refleksivnosti, simetrije i tranzitivnosti, stoga je relacija ekvivalencije i dijeli skup X u klase ekvivalencije. Svaka klasa ekvivalencije će imati brojeve koji, kada se podijele sa 3, daju isti ostatak: X 1 = {3; 6}, X 2 = {1; 4; 7}, X 3 = {2; 5; 8}.

Smatra se da klasu ekvivalencije određuje bilo koji njen predstavnik, tj. proizvoljni element ove klase. Dakle, klasa jednakih razlomaka može se specificirati specificiranjem bilo kojeg razlomka koji pripada ovoj klasi.

U početnom kursu matematike javljaju se i odnosi ekvivalencije, na primjer, "izrazi X i at imaju iste numeričke vrijednosti", "slika X jednaka figuri at».

Neka je dat neki neprazan skup A i R je neki podskup kartezijanskog kvadrata skupa A: R  A  A.

stav R na setu I naziva se podskup skupa I I(ili I 2 ). Dakle stav postoji poseban slučaj podudaranja gdje je područje dolaska isto kao i područje odlaska. Baš kao i podudaranje, relacija je uređeni par gdje oba elementa pripadaju istom skupu.

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

Činjenica da ( a, b)R se može napisati na sljedeći način: a R b. Piše: " a je u odnosu R prema b" ili "između a i b važi relacija R. Inače napiši: a, b)R ili aR b.

Primjeri relacija na skupu brojeva su sljedeći: "=", "", "", ">", itd. Na skupu zaposlenih u bilo kojoj kompaniji, stav "biti šef" ili "biti podređen", na skupu rođaka - "biti predak", "biti brat", "biti otac “, itd.

Relacije koje se razmatraju nazivaju se binarne (dvomesne) homogene relacije i najvažnije su u matematici. Uz njih, smatraju i oni P-lokalni ili P-ari odnosi:

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

Budući da je odnos poseban slučaj korespondencije, sve prethodno opisane metode mogu se koristiti za njihovo postavljanje.

Očigledno, postavljanjem omjera na matrični način, dobijamo kvadratnu matricu.

Sa geometrijskim (grafičkim) prikazom odnosa, dobijamo dijagram koji uključuje:

vrhovi, označeni tačkama ili krugovima, koji odgovaraju elementima skupa,

i lukovi (linije) koji odgovaraju parovima elemenata uključenih u binarne relacije, označeni linijama sa strelicama usmjerenim od vrha koji odgovara elementu a na vrh koji odgovara elementu b , ako a Rb .

Takva figura se naziva usmjereni graf (ili digraf) binarne relacije.

Zadatak 4.9.1 . Ratio "biti delilac na skupu M = (1, 2, 3, 4)" može se dati matrica:

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

geometrijski (grafički):

1. Na skupu A = (1, 2, 3, 4, 5, 6, 7) napiši uređene parove koji pripadaju sljedećim binarnim relacijama:

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

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

2. Relacija R na skupu X = (a, b, c, d) data je matricom

,

u kojem redoslijed redova i kolona odgovara redoslijedu ispisanih elemenata. Navedite uređene parove koji pripadaju datoj relaciji. Prikažite odnos koristeći graf.

3. Relacija na skupu A = (1, 2, 3, 4) je predstavljena grafom. potrebno:

navesti uređene parove koji pripadaju R;

ispisati odgovarajuću matricu;

definirati ovaj odnos korištenjem predikata.

(odgovor: a-b= 1).

4.10. Osnovni tipovi (osobine) binarnih relacija

Neka je binarna relacija R na setu I 2 : R  A  A = (( a, b) | aA, bA, ( a, b)R)

binarnu relaciju R na setu I pozvao reflektirajuće, ako postoji aA izvedeno aRa, to je ( a,a)R. Glavna dijagonala refleksivne relacijske matrice se sastoji od jedinica. Reflektivni graf relacija nužno ima petlje na svakom vrhu.

Primjeri refleksivni odnosi: , =,  na skupu realnih brojeva, “da ne bude šef” na skupu zaposlenih.

binarnu relaciju R na skupu A se zove antirefleksivan (nerefleksivan), ako postoji aA ne drži relaciju aRa, to je ( a,a)R. Glavna dijagonala matrice nerefleksivnih odnosa sastoji se od nula. Graf nerefleksivne relacije nema petlje.

Primjeri antirefleksivni odnosi:<, >na skupu realnih brojeva, okomitost pravih na skupu pravih.

binarnu relaciju R na setu A pozvao simetrično, ako postoji a, bI od aRb trebalo bi bRa, odnosno, ako ( a, b)R, onda i ( b, a)R. Matrica simetričnog omjera je simetrična oko svoje glavne dijagonale ( σ ij = σ ji). Graf simetrične relacije nije usmjeren (rubovi su prikazani bez strelica). Svaki par vrhova ovdje je povezan neusmjerenim rubom.

Primjeri simetrični odnosi:  na skupu realnih brojeva, "biti relativ" na skupu ljudi.

binarnu relaciju R na setu A zove:

antisimetrično, ako postoji a, bI od aRb i bRa sledi to a=b. To jest, ako ( a, b)R i( b, a)R, onda slijedi to a=b. Antisimetrična matrica omjera duž glavne dijagonale ima sve 1 i nijedan par 1 smještenih na simetričnim lokacijama u odnosu na glavnu dijagonalu. Drugim riječima, sve σ ii=1, i ako σ ij=1, onda nužno σ ji=0. Antisimetrični relacijski graf ima petlje na svakom vrhu, a vrhovi su povezani samo jednim usmjerenim lukom.

Primjeri antisimetrične relacije: , ,  na skupu realnih brojeva; ,  na skupovima;

asimetrično, ako postoji a, bI od aRb praćen neuspehom bRa, odnosno, ako ( a, b)R, zatim ( b, a) R. Matrica omjera nagiba duž glavne dijagonale ima nule ( σ ij=0) sve i bez simetričnih parova jedinica (ako σ ij=1, onda nužno σ ji=0). Graf asimetrične relacije nema petlje, a vrhovi su povezani jednim usmjerenim lukom.

Primjeri asimetričnih odnosa:<, >na skupu realnih brojeva, "biti otac" na skupu ljudi.

binarnu relaciju R na setu A pozvao tranzitivannym, ako postoji a, b, saI od aRb i bRa slijedi da i aRsa. To jest, ako ( a, b)R i( b, sa)R slijedi da ( a, sa)R. Tranzitivnu matricu relacija karakteriše činjenica da ako σ ij=1 i σ jm=1, onda nužno σ ja sam=1. Graf tranzitivne relacije je takav da ako su, na primjer, prvi-drugi i drugi-treći vrh povezani lukovima, onda nužno postoje lukovi od prvog do trećeg vrha.

Primjeri tranzitivni odnosi:<, , =, >,  na skupu realnih brojeva; "biti šef" na skupu zaposlenih.

binarnu relaciju R na setu A pozvao antitransitivninym, ako postoji a, b, saI od aRb i bRa proizilazi da nije ispunjeno aRsa. To jest, ako ( a, b)R i( b, sa)R slijedi da ( a, sa) R. Antitransitivnu matricu relacija karakteriše činjenica da ako σ ij=1 i σ jm=1, onda nužno σ ja sam=0. Graf antitranzitivne relacije je takav da ako su, na primjer, prvi-drugi i drugi-treći vrh povezani lukovima, onda nužno ne postoji luk od prvog do trećeg vrha.

Primjeri antitranzitivnih odnosa: "nepodudaranje pariteta" na skupu cijelih brojeva; "biti neposredni rukovodilac" na skupu zaposlenih.

Ako relacija nema neko svojstvo, onda dodavanjem parova koji nedostaju možete dobiti novu relaciju sa ovim svojstvom. Skup takvih nedostajućih parova se zove zatvaranje odnos za ovu nekretninu. Označite ga kao R* . Na ovaj način možete dobiti refleksivno, simetrično i tranzitivno zatvaranje.

Problem 4.10.1. Na skupu A = (1, 2, 3, 4) relacija R=(( a,b)| a,bA, a+b paran broj). Odredite vrstu ovog odnosa.

Odluka. Matrica ove relacije je:

. Očigledno da je veza reflektirajuće, budući da su jedinice duž glavne dijagonale. To simetrično: σ 13 = σ 31 , σ 24 = σ 42 . tranzitivno: (1,3)R, (3,1)R i (1,1)R; (2,4)R, (4,2)R i (2,2)R itd.

Problem 4.10.2. Koja svojstva na skupu A = ( a, b, c, d) ima binarnu relaciju R = (( a,b), (b,d), (a,d), (b,a), (b,c)}?

Odluka . Konstruirajmo matricu ove relacije i njen graf:

Stav irefleksivno, budući da su svi σ ii= 0. It ne simetrično, pošto je σ 23 =1, a σ 32 =0, međutim, σ 12 =σ 21 =1. Stav ne tranzitivno, jer σ 12 =1, σ 23 =1 i σ 13 =0; σ 12 =1, σ 21 =1 i σ 11 =0; ali istovremeno σ 12 =1, σ 24 =1 i σ 14 =1.

Zadatak 4.10.3. Na skupu A = (1,2,3,4,5) data je relacija R = ((1,2), (2,3), (2,4), (4,5)). Odredite tip relacije i pronađite sljedeća zatvaranja za R:

reflektirajuće;

simetrično;

tranzitivan.

Odluka. Relacija je nerefleksivna jer ne postoji element forme ( a,a). Asimetrično, budući da ne sadrži parove oblika ( a,b) i ( b,a) i svi dijagonalni elementi su 0. Antitransitivni jer (1,2)R, (2,3)R, ali (1,3)R. Slično (2.4)R, (4.5)R, i (2.5)R itd.

refleksivno zatvaranje date relacije R * =((1,1), (2,2), (3,3), (4,4), (5,5));

simetrično zatvaranje: R*=((2,1), (3,2), (4,2), (5,4));

tranzitivno zatvaranje: R*=((1,3), (1,4), (2,5)). Razmotrimo graf izvorne relacije i rezultirajuću tranzitivnu relaciju.

Zadaci za samostalno rješavanje.

1. Zadana je relacija R = ((1,1), (1,2), (1,3), (3,1), (2,3)). Odredite njen tip i pronađite zatvaranja po refleksivnosti, simetriji i tranzitivnosti.

2. Odnos na skupu riječi ruskog jezika definiran je na sljedeći način: a R b ako i samo ako imaju barem jedno zajedničko slovo. Odrediti vrstu relacije na skupu A = (krava, vagon, konac, sjekira).

3. Navedite primjere binarnih relacija na skupu A = (1, 2) i B = (1, 2, 3), što bi bilo:

nije refleksivan, nije simetričan, nije tranzitivan;

refleksivan, nije simetričan, nije tranzitivan;

simetričan, ali ne refleksivan i nije tranzitivan;

tranzitivna, ali ne refleksivna i nesimetrična;

refleksivan, simetričan, ali ne i tranzitivan;

refleksivan, tranzitivan, ali ne i simetričan;

nerefleksivan, simetričan, tranzitivan;

refleksivan, simetričan, tranzitivan.