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, iz pripadanja ( 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

određuju 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 smatramo da je jedan element skupa superiorniji od drugog.

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

Kartezijanski proizvod dva seta X I Y zove set svima naručeni parovi ( x, y ) takav da
, A
.

Primjer 1 . Neka .

onda , .

Očigledno je da
, tj. Dekartov proizvod operacije skupova nije komutativan.

Dekartov proizvod skupova
zove set
svi naručeni setovi
takav daAko
, tada je dekartov proizvod označen
.

Reći ćemo da je prepiska data q između setova X I Y, ako je data uređena trojka
, Gdje
.Gomila X naziva se područje polaska, i Y– područje pristizanja korespondencije q(označiti
). Svaki element y uparen sa
nazvana slikom elementa x (x– prototip elementa y) za ovu prepisku q.

Prepiska
pozvao displej setovi X u mnogima Y, ako je svaki element
ima sliku
, tj.

Display
pozvao funkcionalan , ako je svaki element
Ima jedini slika
:. Mnogo slika za dati prikaz
označeno sa
:.

Ako je set
poklapa se sa skupom Y, onda to kažu
displeji on gomila Y.

Prepiska
pozvao jedan na jedan (bijekcija) , ako je a) preslikavanje; b) funkcionalno; c) displeji X"na" set Y; d) iz uslova
trebalo bi
.

Drugim riječima,
je bijekcija ako je svaki element
ima jednu sliku
, i svaki element
ima jedan prototip
sa ovim ekranom:

(1.2)

1.2.2 Definicija binarne relacije

Definicija. Kažu to na mnogima X data binarna relacija R, ako je dat podskup kartezijanskog proizvoda
(oni.
).

Primjer 2 . Neka
Podesimo ga na X sljedeći odnosi:

– odnos jednakosti;

– odnos prioriteta;

podijeljena – odnos djeljivosti.

Svi ovi odnosi su specificirani korištenjem karakterističnog svojstva. Elementi ovog odnosa su navedeni u nastavku:

Činjenica da je par ( x, y) pripada ovoj relaciji R, pisaćemo:
ili xRy. Na primjer, za odnos Q unos 4 Q 2 znači 4 je djeljiv sa 2, tj.

Domen definicije
binarnu relaciju R zove set
Raspon vrijednosti
zove set

Da, za vezu R iz primjera 2 domen definicije je skup
, a raspon vrijednosti je
.

1.2.3 Metode za određivanje binarne relacije

Binarna relacija se može specificirati specificiranjem karakterističnog svojstva ili navođenjem svih njegovih elemenata. Vizuelniji načini specificiranja binarne relacije su graf relacija, relacioni dijagram, graf relacija, matrica odnosa.

Raspored odnosi su prikazani u kartezijanskom koordinatnom sistemu; horizontalna osa označava domen definicije, vertikalna osa označava skup vrednosti relacija; element relacije ( x,y) odgovara tački na ravni sa ovim koordinatama. Na sl. 1.7,a) prikazuje grafik omjera Q primjer 2.

Šema odnosi su prikazani pomoću dvije okomite linije, od kojih lijeva odgovara domeni definicije odnosa, a desna skupu vrijednosti odnosa. Ako element ( x,y) pripada odnosu R, zatim odgovarajuće tačke iz
I
spojena pravolinijskim segmentom. Na sl. 1.7,b) prikazuje dijagram odnosa Q iz primjera 2.

Graf odnos
je konstruisan na sledeći način. Tačke – elementi skupa – prikazani su na ravni bilo kojim redoslijedom X. Par bodova X I at je spojen lukom (linija sa strelicom) ako i samo ako je par ( x,y) pripada odnosu R. Na sl. 1.8,a) prikazuje graf relacija Q primjer 2.

Neka
. Matrix odnos
Ima n linije i n kolone i njegov element utvrđeno pravilom:

Slika 1.8b) prikazuje matricu relacija Q primjer 2.

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 takođe 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 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» 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 učenik 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».

Neka R je neka binarna relacija na skupu X, a x, y, z su bilo koji od njegovih elemenata. Ako je element x u odnosu R sa elementom y, onda napišite xRy.

1. Relacija R na skupu X naziva se refleksivnom ako je svaki element skupa u toj vezi sa samim sobom.

R -refleksivan na X<=>xRx za bilo koje x€ X

Ako je relacija R refleksivna, tada postoji petlja na svakom vrhu grafa. Na primjer, odnosi jednakosti i paralelizma za segmente su refleksivni, ali odnosi okomitosti i „duže“ nisu refleksivni. Ovo se odražava na grafikonima na slici 42.

2. Relacija R na skupu X naziva se simetrična ako iz činjenice da je element x u datoj vezi sa elementom y, slijedi da je element y u istoj vezi sa elementom x.

R - simetrično na (xYay =>y Rx)

Graf simetrične relacije sadrži uparene strelice koje idu u suprotnim smjerovima. Relacije paralelizma, okomitosti i jednakosti za segmente su simetrične, ali „duža“ relacija nije simetrična (slika 42).

3. Relacija R na skupu X naziva se antisimetrična ako za različite elemente x i y iz skupa X, iz činjenice da je element x u datoj vezi sa elementom y, slijedi da element y nije u ovom odnosu sa elementom x.

R - antisimetrično na X « (xRy i xy ≠ yRx)

Napomena: preklopna traka označava negaciju iskaza.

U antisimetričnom relacionom grafu, dve tačke mogu biti povezane samo jednom strelicom. Primjer takve relacije je “duža” relacija za segmente (slika 42). Odnosi paralelizma, okomitosti i jednakosti nisu antisimetrični. Postoje odnosi koji nisu ni simetrični ni antisimetrični, na primjer relacija „biti brat“ (Sl. 40).

4. Relacija R na skupu X naziva se tranzitivna ako iz činjenice da je element x u datoj vezi sa elementom y, a element y u ovoj vezi sa elementom z, slijedi da je element x u datu relaciju sa elementom Z

R - tranzitivan na A≠ (xRy i yRz=> xRz)

Na grafovima „dužih“, paralelnih i jednakosti relacija na slici 42, možete primijetiti da ako strelica ide od prvog elementa do drugog i od drugog do trećeg, onda definitivno postoji strelica koja ide od prvog elementa. element do trećeg. Ovi odnosi su tranzitivni. Okomitost segmenata nema svojstvo tranzitivnosti.

Postoje i druga svojstva odnosa između elemenata istog skupa koja ne razmatramo.

Ista relacija može imati nekoliko svojstava. Tako, na primjer, na skupu segmenata relacija “jednako” je refleksivna, simetrična, tranzitivna; relacija “više” je antisimetrična i tranzitivna.

Ako je relacija na skupu X refleksivna, simetrična i tranzitivna, onda je to relacija ekvivalencije na ovom skupu. Takvi odnosi dijele skup X na klase.

Ovi odnosi se očituju, na primjer, prilikom izvršavanja zadataka: „Pokupite trake jednake dužine i rasporedite ih u grupe“, „Posložite kuglice tako da svaka kutija sadrži kuglice iste boje“. Relacije ekvivalencije („biti jednake dužine“, „biti iste boje“) određuju u ovom slučaju podjelu skupova pruga i kuglica na klase.

Ako je relacija na skupu 1 tranzitivna i antisimetrična, onda se naziva relacija reda na ovom skupu.

Skup sa datom relacijom reda naziva se uređenim skupom.

Na primjer, prilikom izvršavanja zadataka: „Uporedi trake po širini i poredaj ih od najužeg ka najširem“, „Uporedi brojeve i poredaj kartice s brojevima po redu“, djeca poređaju elemente skupova traka i brojčanih kartica. korištenje odnosa naloga; „biti širi“, „pratiti“.

Općenito, odnosi ekvivalencije i reda igraju veliku ulogu u formiranju kod djece ispravnih ideja o klasifikaciji i uređenju skupova. Osim toga, postoje mnoge druge relacije koje nisu ni odnosi ekvivalencije ni relacije poretka.

6. Koje je karakteristično svojstvo skupa?

7. U kojim odnosima mogu postojati skupovi? Dajte objašnjenja za svaki slučaj i oslikajte ih pomoću Ojlerovih krugova.

8. Definirajte podskup. Navedite primjer skupova od kojih je jedan podskup drugog. Zapišite njihov odnos pomoću simbola.

9. Definirajte jednake skupove. Navedite primjere dva jednaka skupa. Zapišite njihov odnos pomoću simbola.

10. Definirajte presjek dva skupa i oslikajte ga korištenjem Ojlerovih krugova za svaki pojedinačni slučaj.

11. Definirajte uniju dva skupa i oslikajte je koristeći Ojlerove krugove za svaki pojedinačni slučaj.

12. Definirajte razliku između dva skupa i oslikajte je koristeći Ojlerove krugove za svaki pojedinačni slučaj.

13. Definirajte komplement i oslikajte ga pomoću Ojlerovih krugova.

14. Šta se zove particioniranje skupa na klase? Navedite uslove za tačnu klasifikaciju.

15. Šta se zove korespondencija između dva skupa? Imenujte metode za određivanje korespondencije.

16. Koja vrsta korespondencije se zove jedan na jedan?

17. Koji skupovi se nazivaju jednaki?

18. Koji skupovi se nazivaju ekvivalentni?

19. Imenujte načine za definiranje relacija na skupu.

20. Koja se relacija na skupu naziva refleksivna?

21. Koja se relacija na skupu naziva simetrična?

22. Koja se relacija na skupu naziva antisimetrična?

23. Koja se relacija na skupu naziva tranzitivna?

24. Definirajte odnos ekvivalencije.

25. Definirajte odnos poretka.

26. Koji skup se naziva uređenim?

U svakodnevnom životu stalno se moramo baviti konceptom „veze“. Relacije su jedan od načina da se specificiraju odnosi između elemenata skupa.

Unarne (jednomjesne) relacije odražavaju prisustvo nekog atributa R u elementima skupa M (na primjer, "biti crven" na skupu kuglica u urni).

Binarni (dvomjesni) odnosi se koriste za definiranje uzajamnih

veze koje karakteriziraju parove elemenata u skupu M.

Na primjer, na skupu ljudi mogu se definirati sljedeći odnosi: „živi u istom gradu“, „ x radi pod rukovodstvom y", "biti sin", "biti stariji" itd. na skupu brojeva: "broj a više broja b", "broj a je djelitelj broja b", "brojevi a I b dati isti ostatak kada se podijeli sa 3.”

U direktnom proizvodu, gdje A- mnogi studenti bilo kojeg univerziteta, B- različiti predmeti koji se proučavaju, može se identifikovati veliki podskup uređenih parova (a, b), koji ima svojstvo: „student a proučava predmet b" Konstruisani podskup odražava odnos “studija” koji nastaje između skupova učenika i objekata. Broj primjera se može nastaviti

Odnos između dva objekta predmet je proučavanja ekonomije, geografije, biologije, fizike, lingvistike, matematike i drugih nauka.

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

Binarna relacija između skupova A i Bnaziva se podskup R direktnog proizvoda. U slučaju kada možete jednostavno razgovarati o vezi R on A.

Primjer 1. Zapišite uređene parove koji pripadaju binarnim relacijama R 1 I R 2, definisan na skupovima A I : , . Podset R 1 sastoji se od parova: . Podset.

Domena R postoji skup svih elemenata iz A tako da za neke elemente imamo . Drugim riječima, domen definicije R je skup svih prvih koordinata uređenih parova R.

Višestruka značenja odnos R ali ima mnogo svih takvih da za neke . Drugim riječima, mnogo značenja R je skup svih drugih koordinata uređenih parova od R.

U primjeru 1 za R 1 domen definicije: , skup vrijednosti - . Za R 2 domen definicije: , skup vrijednosti: .

U mnogim slučajevima zgodno je koristiti grafički prikaz binarne relacije. To se radi na dva načina: pomoću tačaka na ravni i pomoću strelica.

U prvom slučaju, dvije međusobno okomite linije biraju se kao horizontalna i vertikalna osa. Elementi skupa su iscrtani na horizontalnoj osi A i nacrtajte okomitu liniju kroz svaku tačku. Elementi skupa su iscrtani na vertikalnoj osi B, nacrtajte horizontalnu liniju kroz svaku tačku. Točke sjecišta horizontalnih i vertikalnih linija predstavljaju elemente direktnog proizvoda.

Primjer 5. Neka , .

Neka R 1 definisano navođenjem uređenih parova: . Binarna relacija R 2 na skupu je specificirano pomoću pravila: par je naređen ako a podijeljena b. Onda R 2 sastoji se od parova: .

Binarne relacije, iz primjera 2, R 1 I R 2 su grafički prikazane na Sl. 6 i sl.7.

Rice. 6 Fig. 7

Da bi se prikazao binarni odnos pomoću strelica, elementi skupa su prikazani na lijevoj strani kao tačke A, desno - setovi B. Za svaki par (a, b) sadržane u binarnoj relaciji R, strelica je nacrtana iz a To b, . Grafički prikaz binarne relacije R 1 dato u primjeru 6 prikazano je na slici 8.

Fig.8

Binarne relacije na konačnim skupovima mogu se specificirati matricama. Pretpostavimo da nam je data binarna relacija R između setova A I B. , .

Redovi matrice su numerisani elementima skupa A, a kolone su elementi skupa B. Matrična ćelija na raskrsnici i- Oh linije i j Stupac se obično označava sa C ij, a popunjava se na sljedeći način:

Rezultirajuća matrica će imati veličinu .

Primjer 6. Neka je dat skup. Na skupu definirajte relaciju sa listom i matricom R- "da bude striktno manje."

Stav R kako skup sadrži sve parove elemenata ( a, b) od M takav da .

Matrica relacija konstruisana prema gornjim pravilima ima sledeći oblik:

Svojstva binarnih relacija:

1. Binarna relacija R na skupu se zove reflektirajuće, ako je za bilo koji element a od M par (aa) pripada R, tj. važi za bilo koga a od M:

Veze “žive u istom gradu”, “studiram na istom fakultetu”, “ne budi više” reflektirajuće.

2. Binarna relacija se zove antirefleksno, ako nema svojstvo refleksivnosti za bilo koje a:

Na primjer, "biti veći", "biti mlađi" je antirefleksne veze.

3. Binarna relacija R pozvao simetrično, ako za bilo koje elemente a I b od M od kakvog para (a, b) pripada R...iz toga sledi da je par (b,a) pripada R, tj.

Simetrično paralelizam pravih, jer ako onda // . Simetričan odnos“biti jednak” na bilo kojem skupu ili “biti koprost na N”.

Relacija R je simetrična ako i samo ako je R=R -1

4. Ako je za nepodudarne elemente relacija tačna, ali netačna, onda je relacija antisimetrično. Možete reći drugačije:

Odnosi su antisimetrični“biti veći”, “biti djelitelj sa N”, “biti mlađi”.

5. Binarna relacija R pozvao tranzitivan, ako za bilo koja tri elementa tog para (a, b) I (b, c) pripadati R, slijedi da par (a, c) pripada R:

Odnosi su tranzitivni: “biti veći”, “biti paralelan”, “biti jednak” itd.

6. Binarna relacija R antitransitivni, ako nema svojstvo tranzitivnosti.

Na primjer, “biti okomit” na skup pravih linija ( , , ali nije tačno da ).

Jer Budući da se binarna relacija može specificirati ne samo direktnim popisom parova, već i matricom, preporučljivo je saznati koje karakteristike karakteriziraju matricu relacija R, ako je: 1) refleksivna, 2) antirefleksivna, 3) simetrična, 4) antisimetrična, 5) tranzitivna.

Neka R postavljeno na .R se ili izvršava u oba smjera ili se uopće ne izvršava. Dakle, ako matrica sadrži jedan na sjecištu i- Oh linije i j- ta kolona, ​​tj. C ij=1, onda mora biti na raskrsnici j- Oh linije i i- ta kolona, ​​tj. C ji=1, i obrnuto, ako C ji=1, dakle C ij=1. dakle, matrica simetrične relacije je simetrična oko glavne dijagonale.

4. R antisimetrično ako i slijedi: . To znači da u odgovarajućoj matrici za br i, j nije izvršeno C ij =C ji=1. dakle, u matrici antisimetričnog omjera nema jedinica koje su simetrične oko glavne dijagonale.

5. Poziva se binarna relacija R na nepraznom skupu A tranzitivan Ako

Gornji uslov mora biti zadovoljen za bilo koji element matrice. I obrnuto, ako je u matrici R postoji barem jedan element C ij=1, za koje ovaj uslov nije zadovoljen R nije tranzitivan.