Binarni odnosi.

Neka su A i B proizvoljni skupovi. Uzmimo po jedan element iz svakog skupa, a iz A, b iz B, i zapišimo ih ovako: (prvo element prvog skupa, zatim element drugog skupa - tj. važan nam je redosled kojim se elementi uzimaju). Takav objekat ćemo nazvati naručeni par. Jednako Brojaćemo samo one parove čiji su elementi sa istim brojevima jednaki. = , ako je a = c i b = d. Očigledno, ako je a ≠ b, onda ≠ .

Kartezijanski proizvod proizvoljni skupovi A i B (označeni: AB) je skup koji se sastoji od svih mogućih uređenih parova, od kojih prvi element pripada A, a drugi B. Po definiciji: AB = ( | aA i bB). Očigledno, ako je A≠B, onda AB ≠ BA. Dekartov proizvod skupa A sa samim sobom n puta se zove Kartezijanska moć A (označeno sa: A n).

Primjer 5. Neka je A = (x, y) i B = (1, 2, 3).

AB = ( , , , , , }.

BA = (<1, x>, <2, x>, <3, x>, <1, y>, <2, y>, <3, y>}.

AA = A 2 = ( , , , }.

BB = B 2 = (<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <2, 3>, <3, 1>, <3, 2>, <3, 3>}.

Binarna relacija na skupu M je skup nekih uređenih parova elemenata skupa M. Ako je r binarna relacija i par pripada ovoj relaciji, onda pišu: r ili x r y. Očigledno, r Í M 2 .

Primjer 6. Postavite (<1, 2>, <2, 2>, <3, 4>, <5, 2>, <2, 4>) je binarna relacija na skupu (1, 2, 3, 4, 5).

Primjer 7. Relacija ³ na skupu cijelih brojeva je binarna relacija. Ovo je beskonačan skup uređenih parova oblika , gdje su x ³ y, x i y cijeli brojevi. Ova relacija uključuje, na primjer, parove<5, 3>, <2, 2>, <324, -23>i ne pripadaju parovima<5, 7>, <-3, 2>.

Primjer 8. Relacija jednakosti na skupu A je binarna relacija: I A = ( | x O A). I A se zove dijagonalno setovi A.

Pošto su binarne relacije skupovi, na njih su primenljive operacije unije, preseka, sabiranja i razlike.

Domen definicije binarne relacije r je skup D(r) = ( x | postoji y takvo da je xry). Raspon vrijednosti binarne relacije r je skup R(r) = ( y | postoji x takav da je xry ).

stav, obrnuto na binarnu relaciju r Í M 2, binarnu relaciju r -1 = ( | O r). Očigledno je da je D(r‑1) = R(r), R(r‑1) = D(r), r‑ 1 Í M 2.

Kompozicija binarne relacije r 1 i r 2 definisane na skupu M, binarna relacija r 2 o r 1 = ( | postoji y takvo da O r 1 i Í r 2 ). Očigledno je da je r 2 o r 1 Í M 2 .

Primjer 9. Neka je binarna relacija r definirana na skupu M = (a, b, c, d), r = ( , , , ). Tada je D(r) = (a, c), R(r) = (b, c, d), r ‑1 = ( , , , ), r o r = ( , , , ), r‑1 o r = ( , , , ), r o r ‑1 = ( , , , , , , }.

Neka je r binarna relacija na skupu M. Relacija r se zove reflektirajuće, ako je x r x za bilo koje x O M. Relacija r se zove simetrično, ako zajedno sa svakim parom sadrži i par . Relacija r se zove tranzitivan, ako iz činjenice da su x r y i y r z slijedi da je x r z. Relacija r se zove antisimetrično, ako istovremeno ne sadrži par I različiti elementi x ¹ y skupa M.

Naznačimo kriterijume za ispunjavanje ovih svojstava.

Binarna relacija r na skupu M je refleksivna ako i samo ako I M Í r.

Binarna relacija r je simetrična ako i samo ako je r = r‑1.

Binarna relacija r na skupu M je antisimetrična ako i samo ako je r Ç r ‑1 = I M .

Binarna relacija r je tranzitivna ako i samo ako je r o r Í r.

Primjer 10. Relacija u primjeru 6 je antisimetrična, ali nije simetrična, refleksivna ili tranzitivna. Relacija u primjeru 7 je refleksivna, antisimetrična i tranzitivna, ali nije simetrična. Relacija I A ima sva četiri razmatrana svojstva. Relacije r ‑1 o r i r o r ‑1 su simetrične, tranzitivne, ali ne i antisimetrične i refleksivne.

Stav ekvivalencija na skupu M je tranzitivna, simetrična i refleksivna binarna relacija na M.

Stav delimičan red na skupu M je tranzitivna, antisimetrična i refleksivna binarna relacija r na M.

Primjer 11 Relacija u primjeru 7 je relacija parcijalnog reda. Relacija I A je relacija ekvivalencije i parcijalnog reda. Relacija paralelizma na skupu linija je relacija ekvivalencije.

Definicija. Binarna relacija R naziva se podskup parova (a,b)∈R Dekartov 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.

Metode za specificiranje binarnih relacija

1. Lista (nabrajanje parova) za koju ova relacija vrijedi.

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, smješten na presjeku i- redak i j-ti stupac, jednak je 1 ako postoji relacija R između a i i a j, ili 0 ako je odsutna:

Svojstva odnosa

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

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

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 jedinica simetričnih oko glavne dijagonale);

tranzitivno ako je Ɐ a, b, c ∈ A: a R b & b R c ⇒ a R c (u matrici takve relacije mora biti zadovoljen uslov: ako postoji jedinica u i-tom redu, npr. , u j-tim koordinatnim (kolona) redovima, tj. c ij = 1, onda sve jedinice u j-tom redu (neka ove jedinice odgovaraju k e koordinatama tako da je c jk = 1) moraju odgovarati jedinicama u i- red 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“, definisane na skupu prirodnih brojeva.

Rješenje.

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;

tranzitivan, 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.

Problem 3.2. Odrediti svojstva relacije R – „biti brat“, definisane na skupu ljudi.
Rješenje.

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

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

nije simetrično, jer u opštem slučaju između brata a i sestre b postoji aRb, 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 ljude koji imaju zajedničke roditelje (oca i majku) nazivate braćom.

Problem 3.3. Odrediti svojstva relacije R – „biti šef“, definisane na skupu elemenata strukture

Rješenje.

Relacija R = ((a,b) : a je glavni od b):

• nije reflektirajuća, antirefleksivna, ako nema smisla u specifičnoj interpretaciji;
• nije simetrično, antisimetrično, jer za sve a≠b aRb i bRa nisu zadovoljeni istovremeno;
• tranzitivan, jer ako je a šef od b i b je šef od c, onda je a šef od c.

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

1. R 1 “imaju isti ostatak kada se podijeli 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 puno ljudi.
4. R 4 “biti upoznat”; M 4 puno 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 definisane na skupu A.

Union 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 stav U: = ((a;b)/a ∈ A & b ∈ A). ;

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

identičan odnos I: = ((a;a) / a ∈ A);

inverzna relacija R -1 1 Motor: 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 simetričan ⇔ R = R -1.
3. R tranzitivna ⇔ R º R ⊂ R
4. R je antisimetričan ⇔ R ⌒ R -1 ⊂ I .
5. R je antirefleksivan ⇔ R ⌒ I = ∅ .

Problem 3.4 . Neka je R relacija između skupova (1,2,3) i (1,2,3,4), data 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 .

Rješenje.
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 ) -1 .

Problem 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 .

Rješenje.

R -1 - relacija “...dijete...”;

S -1 - odnos “...brat ili sestra...”;

R º S - relacija “...roditelj...”;

S -1 º R -1 - odnos “...dijete...”

R º R - odnos “...baka ili djed...”

Problemi koje treba riješiti samostalno

1) Neka je R relacija “...otac...” i 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...” i 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...” i S relacija “...sin...” na skupu svih ljudi. Dajte verbalni opis odnosa:

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

5) Neka je R relacija “...nećakinja...” i 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...” i 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...” i 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...” i 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...” i S relacija “...brat...” na skupu svih ljudi. Dajte verbalni opis odnosa:

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

Povezane definicije

Svojstva odnosa

Binarne relacije mogu imati različita svojstva, kao npr

Vrste odnosa

• Refleksivna tranzitivna relacija naziva se relacija kvazi-reda.
• Refleksivna simetrična tranzitivna relacija naziva se relacija ekvivalencije.
• Refleksivna antisimetrična tranzitivna relacija naziva se (parcijalna) relacija reda.
• Antirefleksivna antisimetrična tranzitivna relacija naziva se relacija strogog reda.
• Potpuna antisimetrična (za bilo koje vrijednosti x, y xRy ili yRx) tranzitivna relacija naziva se relacija linearnog reda.
• Antirefleksivni asimetrični odnos naziva se odnos dominacije.

Vrste dvostrukih odnosa

• Obrnuti stav [odrediti] (relacija inverzna prema R) je binarna relacija koja se sastoji od parova elemenata (y, x) dobijenih permutacijom parova elemenata (x, y) date relacije R. Označava se sa: R −1. Za ovu relaciju i njen inverz vrijedi sljedeća jednakost: (R −1) −1 = R.
• Recipročni odnosi(recipročni odnosi) - odnosi koji su inverzni jedni prema drugima. Raspon vrijednosti jednog od njih služi kao raspon definicije drugog, a raspon definicije prvog služi kao raspon vrijednosti drugog.
• Reflektivni stav- binarna relacija R definirana na određenom skupu i karakterizirana time da je za bilo koji x ovog skupa element x u odnosu R prema sebi, odnosno za bilo koji element x ovog skupa vrijedi xRx. Primjeri refleksivnih odnosa: jednakost, istovremenost, sličnost.
• Antirefleksivan stav(Nerefleksivna relacija, imajte na umu da se kao što se antisimetrija ne poklapa sa asimetrijom, nerefleksivnost se ne podudara sa nerefleksivnošću.) - relacija na dva mjesta R definirana na određenom skupu i karakterizirana time da za bilo koji element x ovog skupa nije tačno da je u odnosu R prema sebi (nije tačno da je xRx), odnosno moguće je da element skupa nije u odnosu R prema sebi. Primjeri nerefleksivnih stavova: „brinuti se“, „zabavljati“, „nervozno“.
• Tranzitivna relacija- binarnu relaciju R, definiranu na određenom skupu i karakteriziranu time da za bilo koje x, y, z ovog skupa, xRy i yRz impliciraju xRz (xRy&yRzxRz). Primjeri tranzitivnih odnosa: “više”, “manje”, “jednako”, “slično”, “iznad”, “sjever”.
• Intranzitivna relacija [odrediti] - binarna relacija R definirana na određenom skupu i karakterizirana time da za bilo koje x, y, z ovog skupa xRy i yRz ne impliciraju xRz ((xRy&yRzxRz)). Primjer intranzitivne relacije: "x je otac y"
• Simetrična relacija- relacija R na dva mjesta, definirana na određenom skupu i karakterizirana time da za bilo koje elemente x i y ovog skupa, iz činjenice da je x prema y u odnosu R (xRy), slijedi da je y u istom odnos prema x ( yRx). Primjer simetričnih odnosa može biti jednakost (=), odnos ekvivalencije, sličnosti, istovremenosti, neki odnosi srodstva (na primjer, odnos bratstva).
• Antisimetrična relacija- relacija R na dva mjesta, definirana na određenom skupu i karakterizirana time da za bilo koje x i y iz xRy i xR −1 y slijedi x = y (odnosno, R i R −1 su istovremeno zadovoljeni samo za članove koji su jednake jedna drugoj).
• Asimetrični odnos [odrediti] je relacija R na dva mjesta, definirana na određenom skupu i karakterizirana time da za bilo koje x i y, xRy implicira yRx. Primjer: odnos “više od” (>) i “manje od” (<).
• Relacija ekvivalencije(odnos identiteta [ odrediti], relacija tipa jednakosti) je relacija R na dva mjesta između objekata x i y u predmetnoj oblasti D, koja zadovoljava sljedeće aksiome (uslove): Dakle, relacija tipa jednakosti je istovremeno refleksivna, simetrična i tranzitivna. Primjeri: jednakost, jednaka kardinalnost dva skupa, razmjenjivost dobara na tržištu, sličnost, istovremenost. Primjer relacije koja zadovoljava aksiom (3), ali ne zadovoljava aksiome (1) i (2): „više“.
• Odnosi reda- relacije koje imaju samo neka od tri svojstva relacije ekvivalencije. Konkretno, relacija koja je refleksivna i tranzitivna, ali asimetrična (na primjer, „ne više“) formira „laksi“ poredak. Relacija je tranzitivna, ali nerefleksivna i asimetrična (na primjer, "manje od") - "strogi" red.
• Funkcija- dvostruki odnos R, definiran na određenom skupu, karakteriziran time da za svaku vrijednost x odnos xRy y. Primjer: " y otac x" Svojstvo funkcionalnosti relacije R zapisuje se kao aksiom: ( xRy I xRz)→(y≡z). Od svake vrijednosti x u izrazima xRy I xRz onda odgovara istoj vrijednosti y I z poklapaju, ispostavi se da je isto. Funkcionalna relacija je jedinstvena, jer svaka vrijednost x ima relaciju xRy odgovara samo jednoj vrijednosti y, ali ne i obrnuto.
• Bijection(one-place relation) - dvomjesni odnos R, definiran na određenom skupu, karakteriziran time što u njemu svaka vrijednost x odgovara jednoj vrijednosti at, i svaku vrijednost at odgovara jednoj vrijednosti X. Relacija jedan-na-jedan je poseban slučaj relacije jedan-na-jedan.
• Povezani odnos- ovo je odnos na dva mesta R, definiran na određenom skupu, karakteriziran time da za bilo koja dva različita elementa X I at ovog skupa, jedan od njih je u odnosu R drugom (to jest, jedna od dva odnosa je zadovoljena: xRy ili yRx). Primjer: relacija "manje od" (<).

Operacije na odnosima

Budući da su relacije definirane na fiksnom paru skupova , , podskupovi skupa , skup svih ovih relacija formira Bulovu algebru s obzirom na operacije ujedinjenja, presjeka i sabiranja relacija. Posebno za proizvoljno

Često, umjesto kombinovanja, ukrštanja i dopunjavanja odnosa, oni govore o njihovoj disjunciji, konjukciji i negaciji.

Na primjer, , , to jest, unija relacije strogog reda s relacijom jednakosti poklapa se s relacijom nestrogog reda, a njihov presjek je prazan.

Pored navedenih, važne su i operacije inverzije i množenja relacija koje su definisane na sledeći način.

Ako , tada je inverzna relacija relacija definirana na paru i koja se sastoji od onih parova za koje . Na primjer, .

Neka sada, . Proizvod odnosa je odnos takav da

Ako , i , tada je proizvod odnosa nedefiniran. Ako uzmemo u obzir relacije definirane na nekom skupu, onda do takve situacije ne dolazi.

Na primjer, uzmite u obzir strogi odnos reda definiran na skupu prirodnih brojeva. Lako je to primijetiti

Binarni odnosi se nazivaju komutativni ako . Lako je vidjeti da za bilo koju binarnu relaciju definiranu na , gdje simbol označava jednakost definiranu na . Međutim, jednakost nije uvijek pravedna.

Važe sljedeći identiteti:

Imajte na umu da analogi posljednja dva identiteta ne vrijede.

Neka svojstva relacije mogu se odrediti pomoću relacijskih operacija:

vidi takođe

Književnost

• A. I. Maltsev. Algebarski sistemi. - M.: Nauka, 1970.

Wikimedia fondacija. 2010.

- predikat na dva mjesta na datom skupu. Pod B. o. ponekad shvaćen kao podskup skupa uređenih parova (a, 6) elemenata datog skupa A. B. o. poseban slučaj veze. Neka bude. Ako, onda se za element kaže da je binarno...... Mathematical Encyclopedia

U logici, nešto što, za razliku od svojstva, ne karakteriše pojedinačni objekat, već par, tri, itd. stavke. Tradicionalna logika nije razmatrala O.; u modernoj logici O. je propoziciona funkcija dvije ili više varijabli. binarni... Philosophical Encyclopedia

stav- VEZA je skup uređenih n ok pojedinaca (gdje je n 1), tj. dvojke, trojke itd. Broj n se naziva "lokalitet", ili "arity", O. i, shodno tome, govore o n lokalnom (n arno) O. Tako se, na primjer, dvostruko O. zove ... ... Enciklopedija epistemologije i filozofije nauke

U teoriji potrošača, ovo je formalni opis sposobnosti potrošača da uporedi (red po želji) različite skupove dobara (potrošačke pakete). Da bismo opisali odnos preferencija, nije potrebno mjeriti poželjnost... ... Wikipedia

Ovaj izraz ima druga značenja, pogledajte Stav. Relacija je matematička struktura koja formalno definira svojstva različitih objekata i njihovih odnosa. Odnosi se obično klasifikuju prema broju objekata koji se povezuju... Wikipedia

Ovaj izraz ima druga značenja, pogledajte Stav. Relacija u logici prvog reda prema dva ili više predikata argumenata (više predikata), dva ili više svojstava predikata. Znak odnosa: R.[navedite] U smislu odnosa....... Wikipedia, A.I. Širokov. Priručnik je sedmi dio odjeljka “Osnovne teorijske konstrukcije skupova” nastavne discipline “Diskretna matematika”. Uvodi i analizira takve... eBook

Predavanje 3.

klauzula 3. Relacije na skupovima. Svojstva binarnih relacija.

3.1. Binarni odnosi.

Kada govore o odnosu dvoje ljudi, na primjer, Sergeja i Ane, misle da postoji određena porodica kojoj oni pripadaju. Naručeni par (Sergei, Ana) razlikuje se od drugih naređenih parova ljudi po tome što postoji neka vrsta odnosa između Sergeja i Ane (rođak, otac, itd.).

U matematici, među svim uređenim parovima direktni proizvod dva skupa A I B (A´ B) „posebni“ parovi se razlikuju i zbog činjenice da između njihovih komponenti postoje neki „srodstveni“ odnosi koje drugi nemaju. Kao primjer, razmotrite set S studenti nekih univerziteta i mnogi K kurseve koji se tamo predaju. U direktnom proizvodu S´ K može se odabrati veliki podskup uređenih parova ( s, k) ima svojstvo: student s pohađa kurs k. Konstruisani podskup odražava odnos "...sluša..." koji prirodno nastaje između grupe studenata i kurseva.

Za strogi matematički opis bilo koje veze između elemenata dva skupa, uvodimo koncept binarne relacije.

Definicija 3.1. Binarno (ili duplo )stav r između setova A I B poziva se proizvoljan podskup A´ B, tj.

Konkretno, ako A=B(tj. rÍ A 2), tada kažu da je r relacija na skupu A.

Elementi a I b su pozvani komponente (ili koordinate ) odnos r.

Komentar. Složimo se da za označavanje odnosa između elemenata skupova koristimo grčku abecedu: r, t, j, s, w, itd.

Definicija 3.2. Domen definicije D r=( a| $ b, Šta a r b) (lijeva strana). Raspon vrijednosti binarne relacije r naziva se skup R r=( b| $ a, Šta a r b) (desni dio).

Primjer 3. 1. Neka su data dva skupa A=(1; 3; 5; 7) i B=(2; 4; 6). Postavimo relaciju na sljedeći način t=(( x; y)Î A´ B | x+y=9). Ova relacija će se sastojati od sljedećih parova (3; 6), (5; 4) i (7; 2), koji se mogu zapisati kao t=((3; 6), (5; 4), (7;2 ) ). U ovom primjeru D t=(3; 5; 7) i R t= B={2; 4; 6}.

Primjer 3. 2. Relacija jednakosti na skupu realnih brojeva je skup r=(( x; y) | x I y– realni brojevi i x jednaki y). Za ovaj odnos postoji posebna oznaka: “=”. Domen definicije poklapa se sa domenom vrijednosti i predstavlja skup realnih brojeva, D r= R r.

Primjer 3. 3. Neka A– puno robe u radnji, i B– skup realnih brojeva. Tada je j=(( x; y)Î A´ B | y- Cijena x) – odnos skupova A I B.

Ako obratite pažnju na primjer 3.1., primijetit ćete da je ova relacija prvo navedena u obliku t=(( x; y)Î A´ B | x+y=9), a zatim se zapisuje kao t=((3; 6), (5;4), (7;2)). Ovo sugerira da se relacije na skupovima (ili jednom skupu) mogu specificirati na različite načine. Pogledajmo načine definiranja binarnih odnosa.

Metode za definisanje odnosa:

1) upotrebom odgovarajućeg predikata;

2) skup uređenih parova;

3) u grafičkom obliku: neka A I B– dva konačna skupa i r – binarna relacija između njih. Elementi ovih skupova su predstavljeni tačkama na ravni. Za svaki uređeni par relacija, r crta strelicu koja povezuje tačke koje predstavljaju komponente para. Takav objekat se zove usmjereni graf ili digraf, tačke koje predstavljaju elemente skupova se obično nazivaju vrhovima grafa.

4) u obliku matrice: neka A={a 1, a 2, …, an) I B={b 1, b 2, …, bm), r – omjer uključen A´ B. Matrična reprezentacija r se naziva matrica M=[mij] veličina n´ m, definisan relacijama

.

Inače, matrična reprezentacija je reprezentacija relacije u računaru.

Primjer 3. 4. Neka su data dva skupa A=(1; 3; 5; 7) i B=(2; 4; 6). Relacija je data na sljedeći način t=(( x; y) | x+y=9). Definišite ovu relaciju kao skup uređenih parova, digraf, u obliku matrice.

Rješenje. 1) t=((3; 6), (5; 4), (7; 2)) - je definicija relacije kao skupa uređenih parova;

2) odgovarajući usmjereni graf je prikazan na slici.

https://pandia.ru/text/78/250/images/image004_92.gif" width="125" height="117">. ,

Primjer 3. 5 . Kao primjer možemo razmotriti predloženo J. von Neumann(1903 – 1957) blok dijagram sekvencijalnog računara, koji se sastoji od mnogo uređaja M:

,

Gdje a- ulazni uređaj, b– aritmetički uređaj (procesor), c- kontrolni uređaj, d- memorijski uređaj, e– izlazni uređaj.

Razmotrimo razmjenu informacija između uređaja mi I mj, koji su u odnosu r ako iz uređaja mi informacije ulaze u uređaj mj.

Ova binarna relacija se može definirati navođenjem svih njenih 14 uređenih parova elemenata:

Odgovarajući digraf koji definira ovu binarnu relaciju prikazan je na slici:

Matrični prikaz ove binarne relacije je:

. ,

Za binarne relacije, teorijske skupove operacije se definišu na uobičajen način: unija, presek, itd.

Hajde da uvedemo generalizovani koncept odnosa.

Definicija 3.3. n-mesto (n-ary ) relacija r je podskup direktnog proizvoda n skupovi, odnosno skup uređenih skupova ( tuples )

rÍ A 1 An={(a 1, …, an)| a 1O A 1Ù…Ù anÎ An}

Pogodno je definirati relacije više mjesta koristeći relacione tabele . Ovaj zadatak odgovara nabrajanju skupa n-na odnos r. Relacione tabele se široko koriste u računarskoj praksi u relacionim bazama podataka. Imajte na umu da se relacijske tablice koriste u svakodnevnoj praksi. Sve vrste proizvodnih, finansijskih, naučnih i drugih izveštaja često imaju oblik relacionih tabela.

riječ " relacijski“ dolazi od latinske riječi odnos, što u prevodu na ruski znači „stav“. Stoga se u literaturi slovo koristi za označavanje odnosa R(latinski) ili r (grčki).

Definicija 3.4. Neka rÍ A´ B postoji stav prema A´ B. Tada se naziva omjer r-1 inverzna relacija na dati odnos r by A´ B, koji je definiran na sljedeći način:

r-1=(( b, a) | (a, b)Îr).

Definicija 3.5. Neka je r N A´ B postoji stav prema A´ B, a s N B´ C – stav prema B´ C. Kompozicija odnosi s i r se naziva relacija t N A´ C, koji je definiran na sljedeći način:

t=s◦r= (( a, c)| $bÎ B, šta (a, b)Îr I (b, c)Îs).

Primjer 3. 6 . Neka i C=(, !, d, a). I neka omjer bude r A´ B i omjer je uključen B´ C dati su u obliku:

r=((1, x), (1, y), (3, x)};

s=(( x,), (x, !), (y, d), ( y, à)}.

Naći r-1 i s◦r, r◦s.

Rješenje. 1) Po definiciji r-1=(( x, 1), (y, 1), (x, 3)};

2) Koristeći definiciju sastava dvije relacije, dobijamo

s◦r=((1,), (1, !), (1, d), (1, a), (3,), (3, !)), (3, !)),

budući da od (1, x)Îr i ( x,)Îs slijedi (1,)Îs◦r;

od (1, x)Îr i ( x, !)Îs slijedi (1, !)Îs◦r;

od (1, y)Îr i ( y, d)Îs slijedi (1, d)Îs◦r;

od (3, x)Îr i ( x, !)Îs slijedi (3, !)Îs◦r.

Teorema 3.1. Za bilo koje binarne relacije vrijede sljedeća svojstva:

2) ;

3) - asocijativnost kompozicije.

Dokaz. Svojstvo 1 je očigledno.

Dokažimo svojstvo 2. Da bismo dokazali drugo svojstvo, pokazaćemo da se skupovi napisani na lijevoj i desnoj strani jednakosti sastoje od istih elemenata. Neka ( a; b) O (s◦r)-1 Û ( b; a) O s◦r Û $ c takav da ( b; c) O r i ( c; a) O s Û $ c takav da ( c; b) O r-1 i ( a; c) O s-1 Š ( a; b) O r -1◦s -1.

Svojstvo 3 dokažite sami.

3.2. Svojstva binarnih relacija.

Razmotrimo posebna svojstva binarnih relacija na skupu A.

Svojstva binarnih relacija.

1. Omjer r uključen A´ A pozvao reflektirajuće , Ako ( a,a) pripada r za sve a od A.

2. Relacija r se zove antirefleksno , ako od ( a,b)Îr slijedi a¹ b.

3. Omjer r simetrično , ako za a I b pripada A, od ( a,b)Ili iz toga slijedi da ( b,a)Îr.

4. Relacija r se zove antisimetrično , ako za a I b od A, od pripadnosti ( a,b) I ( b,a) relacija r implicira da a=b.

5. Omjer r tranzitivno , ako za a, b I c od A iz činjenice da ( a,b)Îr i ( b,c)Ir, slijedi da ( a,c)Îr.

Primjer 3. 7. Neka A=(1; 2; 3; 4; 5; 6). Na ovom skupu data je relacija rÍ A 2, koji ima oblik: r=((1, 1), (2, 2), (3, 3), (4; 4), (5; 5), (6; 6), (1; 2 ) , (1; 4), (2; 1), (2;4), (3;5), (5; 3), (4; 1), (4; 2)). Koja svojstva ima ovaj odnos?

Rješenje. 1) Ovaj odnos je refleksivan, jer za svaki aÎ A, (a; a)Îr.

2) Relacija nije antirefleksivna, jer uslov ovog svojstva nije zadovoljen. Na primjer, (2, 2)Îr, ali to ne znači da je 2¹2.

3) Razmotrimo sve moguće slučajeve, pokazujući da je relacija r simetrična:

	(a, b)Îr	(b, a)	(b, a)Îr?

4) Ova relacija nije antisimetrična, budući da (1, 2)Îr i (2,1)Îr, ali iz toga ne slijedi da je 1=2.

5) Moguće je pokazati da je relacija r tranzitivna korištenjem metode direktnog nabrajanja.

	(a, b)Îr	(b, c)Îr	(a, c)	(a, c)Îr?

Kako koristiti matričnu reprezentaciju

odrediti svojstva binarne relacije

1. Refleksivnost: Sve jedinice su na glavnoj dijagonali; nule ili jedinice su označene zvjezdicama.

.

2. Anti-refleksivnost: Sve nule na glavnoj dijagonali.

3. Simetrija: Ako .

4. Antisimetrija: svi elementi izvan glavne dijagonale su nula; mogu biti i nule na glavnoj dijagonali.

.

Operacija “*” se izvodi prema sljedećem pravilu: , Gdje , .

5. Tranzitivnost: Ako . Operacija “◦” se izvodi po uobičajenom pravilu množenja, a potrebno je uzeti u obzir: .

3.3 Relacija ekvivalencije. Parcijalni odnos poretka.

Relacija ekvivalencije je formalizacija situacije kada govorimo o sličnosti (istosti) dva elementa skupa.

Definicija 3.6. Omjer r uključen A Tu je odnos ekvivalencije, ako refleksivna, simetrična i tranzitivna. Relacija ekvivalencije a r bčesto označavano: a~ b.

Primjer 3. 8 . Relacija jednakosti na skupu cijelih brojeva je relacija ekvivalencije.

Primjer 3. 9 . Relacija “iste visine” je relacija ekvivalencije na skupu ljudi X.

Primjer 3. 1 0 . Neka je ¢ skup cijelih brojeva. Nazovimo dva broja x I y od ¢ uporedivi po modulum(m O¥) i napišite , ako su ostaci ovih brojeva nakon dijeljenja sa m, tj. razlika ( x-y) podijeljena m.

Relacija „uporedivo u modulu m cijeli brojevi" je relacija ekvivalencije na skupu cijelih brojeva ¢. Zaista:

ovaj odnos je refleksivan, jer za " x΢ imamo x-x=0, pa je stoga djeljiv sa m;

ova relacija je simetrična, jer ako ( x-y) podijeljena m, zatim ( y-x) je također djeljiv sa m;

ova relacija je tranzitivna, jer ako ( x-y) podijeljena m, zatim za neki cijeli broj t 1 imamo https://pandia.ru/text/78/250/images/image025_23.gif" width="73" height="24 src=">, odavde , tj. ( x-z) podijeljena m.

Definicija 3.7. Omjer r uključen A Tu je parcijalni odnos poretka, ako refleksivni, antisimetrični i tranzitivni i označen je simbolom °.

Djelomični red je važan u situacijama kada želimo nekako okarakterizirati prednost. Drugim riječima, odlučite pod kojim uslovima da jedan element skupa smatrate superiornijim u odnosu na drugi.

Primjer 3. 11 . Stav x£ y postoji relacija parcijalnog reda na skupu realnih brojeva. ,

Primjer 3. 1 2 . U skupu podskupova nekog univerzalnog skupa U stav AÍ B postoji odnos parcijalne narudžbe.

Primjer 3. 1 3 . Šema organizacije subordinacije u instituciji je odnos djelomičnog reda u nizu pozicija.

Prototip relacije parcijalnog poretka je intuitivni koncept relacije preferencije (prednost). Relacija preferencije identifikuje klasu problema koji se mogu kombinovati kao problem izbora najbolji objekat .

Formulacija problema: neka postoji kolekcija objekata A i potrebno ih je uporediti prema preferenciji, odnosno postaviti relaciju preferencije na skupu A i identificirati najbolje objekte.

Odnos preferencija P, koji se može definisati kao " aPb, a, bÎ AÛ objekt a ništa manje poželjniji od objekta b"je refleksivan i antisimetričan po značenju (svaki predmet nije gori od sebe, a ako je predmet a ništa gore b I b ništa gore a, onda su isti po želji). Prirodno je pretpostaviti da je odnos P tranzitivno (iako u slučaju kada, na primjer, o preferencijama raspravlja grupa ljudi sa suprotstavljenim interesima, ovo svojstvo može biti narušeno), tj. P– odnos parcijalnog naloga.

Jedan od mogućih načina da se riješi problem poređenja objekata po preferencijama je rasponu , tj. naručivanje objekata u skladu sa opadajućom preferencijom ili ekvivalentnošću. Kao rezultat rangiranja, identifikujemo „najbolje“ ili „najgore“ objekte sa stanovišta odnosa preferencija.

Područja upotrebe problemi o problemu izbora najboljeg objekta: teorija odlučivanja, primijenjena matematika, tehnologija, ekonomija, sociologija, psihologija.

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

2. Refleksivnost

Definicija. Stav R na razne načine 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. Anti-refleksivnost

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

R anti-refleksivan uključen X Û(" XÎ X)

Primjer. Direktan odnos X okomito na pravu liniju at» na skupu ravnih linija je antirefleksivan, jer nijedna prava linija ravni nije okomita na samu sebe.

Grafikon antirefleksivnog stava ne sadrži ni jednu petlju.

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

Dot X simetrično prema tački X- istinito; dot at simetrično prema tački at– netačno, dakle, ne možemo tvrditi da su sve tačke ravni simetrične same sebi, a isto tako ne možemo tvrditi da nijedna tačka ravni nije simetrična sama sebi.

3. Simetrija

Definicija. Stav R na razne načine 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. Direktan odnos X seče pravu at na skupu pravih ravni” je simetrična, jer ako je ravno X seče pravu at, zatim linija at definitivno će preći granicu X.

Grafikon simetrične relacije 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 razne načine 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 to istovremeno reći X < at I at<X.

Asimetrični relacioni graf nema petlje, a ako su dva vrha grafa povezana strelicom, onda postoji samo jedna strelica.

5. Antisimetrija

Definicija. Stav R na razne načine 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 = u.

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

Primjer. stav " X£ at» antisimetrično, jer uslovima X£ at I at£ X izvršavaju se istovremeno samo kada X = u.

Antisimetrični relacioni graf ima petlje, a ako su dva vrha grafa povezana strelicom, onda postoji samo jedna strelica.

6. Tranzitivnost

Definicija. Stav R na razne načine 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 transitivenona X Û(" X, at, zÎ X) x R y Ù y R zÞ x R z

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

Graf tranzitivnih odnosa 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 razne načine 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 Ú y R zÚ X= at

Drugim riječima: stav R na razne načine X naziva se povezano 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» koherentno, jer bez obzira koje realne brojeve uzmemo, jedan od njih će definitivno biti veći od drugog ili će biti jednaki.

U povezanom relacionom grafu, svi vrhovi su međusobno povezani strelicama.

Primjer. Provjerite koja svojstva ima

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, jer 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, ovaj odnos ima svojstva refleksivnosti, asimetrije i tranzitivnosti.

§ 3. Relacija ekvivalencije.
Veza između relacije ekvivalencije i podjele skupa na klase

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

Primjer. Razmotrite odnos " X drug iz razreda at„na mnogim studentima Pedagoškog fakulteta. Ima sljedeća svojstva:

1) refleksivnost, jer svaki učenik je sam sebi drug iz razreda;

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

3) tranzitivnost, jer ako je student X- drugarica iz razreda at, i student at– drugarica iz razreda z, zatim student Xće biti učenikov drug iz razreda z.

Dakle, ova relacija ima svojstva refleksivnosti, simetrije i tranzitivnosti, te je stoga relacija ekvivalencije. Istovremeno, mnogi studenti Pedagoškog fakulteta mogu se podijeliti u podskupove koje se sastoje od studenata koji studiraju na istom predmetu. Dobijamo 5 podskupova.

Relacije ekvivalencije su i, na primjer, odnos paralelnosti pravih, odnos jednakosti figura. Svaki takav odnos povezan je sa dijeljenjem 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 snimanju X= (1; 2; 3; 4; 5; 6; 7; 8) specificirana 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 na klase ekvivalencije. U svakoj klasi ekvivalencije biće brojevi 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. proizvoljan element ove klase. Dakle, klasa jednakih razlomaka može biti specificirana specificiranjem bilo kojeg razlomka koji pripada ovoj klasi.

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