RELACIJE
Relacija se može posmatrati kao povezivanje elemenata nekog skupa A sa elementima
nekog skupa B, gde je važno da se zna koji elementi skupa A su u vezi (relaciji), sa kojim
elementima skupa B. Zbog toga se jedna takva relacija u potpunosti može zadati na
sledeći način: ako x  A i y  B i pri tom su x i y u datoj relaciji, onda se uređenom paru
( x, y) A×B pridružuje vrednost T, a ako to nije slučaj, onda se tom uređenom paru
pridružuje vrednost  . Dakle, relacija zapravo razdvaja one uređene parove elemenata
skupova A i B za koje se kaže da jesu od onih za koje se kaže da nisu u toj relaciji. Stoga
se jedna relacija među elementima skupova A i B može zadati kao podskup Dekartovog
proizvoda A×B uređenih parova onih elemenata koji jesu u datoj relaciji.
Definicija 1: Binarna relacija skupa A je svaki podskup  skupa A×A.
Ako je (a, b)   kažemo da su elementi a i b u relaciji  . Ovo se vrlo često piše i na
sledeći način: a  b .
Jedna relacija  nad konačnim skupovima elemenata, može se zadati neposrednim
nabrajanjem uređenih parova koji jesu u relaciji. To, međutim, nije uvek zgodno i
pregledno. Preglednija mogućnost predstavljanja relacije u takvom slučaju je tablica
relacije ili graf relacije. Ako (a, b)   onda se u tablici na mestu gde se presecaju vrsta u
kojoj se nalazi a i kolona u kojoj se nalazi b piše T, a ukoliko (a, b)   , onda se na tom
mestu piše  . Kada se relacija predstavlja grafom, onda se svaki element predstavlja
jednom tačkom, a činjenicva da je a  b označava se povezujući tačku a i b linijom,
naznačujući pri tom strelicom smer od a ka b.
Osobine relacija: Relacija skupa A je
1) refleksivna(R) ako je (x  A)( x x)
2) simetrična(S) ako je (x, y  A)( x y  y  x).
3) antisimetrična(A) ako je (x, y  A)( x y  y  x  x  y).
4) tranzitivna(T) ako je (x, y, z  A)( x y  y  z  x z ).
Definicija 2: Relaciju ~ koja je refleksivna, simetrična i tranzitivna nazivamo relacijom
ekvivalencije.
Svaka relacija ekvivalencije stvara na skupu na kojem je data takozvane klase
ekvivalencije:
Definicija 3: Ako je ~ relacija ekvivalencije na skupu A, tada skup Ca  {x | x  A, a ~ x} ,
gde je a  A nazivamo klasom ekvivalencije elementa a.
Osobine klasa ekvivalencije:
1) a  A Ca   ;
2) ako je a~b, onda je Ca  Cb ;
3) ako nije a~b, onda je Ca  Cb  
Mi se sada nećemo toliko baviti
klasama ekvivalencije ali je
dobro znati šta su one.
Definicija 4: Skup svih klasa koje na skupu A formira relacija  predstavlja se simbolom
A/  (čita se „A posečeno sa  “) naziva se količničkim skupom.
U kasnijem izučavanju matematike
količnički skupovi su od ogromnog
značaja. Za nas, ipak, oni neće biti toliko
važni.
Definicija 5 Relaciju koja je refleksivna, antisimetrična i tranzitivna nazivamo relacijom
poretka.
ZADACI:
1. Na skupu {1, 2,3} data je relacija   {(1,3),(2, 2),(2,3),(3, 2)} . Napraviti tablicu i
i nacrtati graf te relacije.
Rešenje:

1
2
3
1
T


2
T
T

3
T


Graf:
2. Da li je relacija  određena tablicom

1

T
T
1
2
3
2
T

T
3
T

T
relacija ekvivalencije ili poretka?
Rešenje: Nije ni jedno ni drugo, pošto nije refleksivna.
3. U skupu {0,1, 2,3, 4,5} uvedena je relacija x y  ( x  y  3  x  y  1) . Nacrtati
tablicu ove relacije .

0
1
2
3
4
5
Rešenje:
0
1
2
3
4
5








T



























4. U skupu {0,1, 2,3, 4} definisana je relacija x y  y  x  1. Odrediti elemente ove
relacije, nacrtati njenu tablicu i graf. Koja od svojstava refleksivnost, simetrija i
tranzitivnost ima relacija  ?
Rešenja:   {(1,0),(2,1),(3, 2),(4,3)} . Graf i tablicu je lako nacrtati. Ova relacija ne
poseduje nijednu od osobina navedenih u zadatku.
5. U skupu {1, 2,3, 4,5,6,7,8,9} uvedene su relacije:
a) x y  x  y  8
b) x y  x  3 y
Nacrtati graf relacije i ispitati koja od svojstava refleksivnost, simetričnos,
antisimetričnost i tranzitivnost imaju ove relacije.
6. Ispitati koja od svojstava refleksivnosti, simetričnosti, antisimetričnosti i tranzitivnosti
imaju relacije:
a) x  y  x 2  xy  y 2  1
b) x  y  x 2  y 2
u skupu realnih brojeva.
7. Na skupu A  {0,1, 2,3} definisana je relacija  :
a) x y  x  y  2; b) x y  x  y  3; c) x  y  x  y  2; d ) x  y  x  y  3.
Napraviti tablicu za relaciju  i ispitati koja od svojstava: refleksivnost, simetrija,
antisimetrija i tranzitivnost ima relacija  .
8. U skupu A= {5, 4, 3, 2, 1,0,1, 2,3, 4,5} definisana je relacija x y | x || y | .
Doakzati da je  relacija ekvivalencije,odrediti klase i količnički skup.
Rešenje: Klase ekvivalencije su:
C0  {0}, C1  {1,1}, C2  {2, 2}, C3  {3,3}, C4  {4, 4} i C5  {5,5}
A /   {{0},{1,1},{2, 2},{3,3},{4, 4},{5,5}}
9. Na skupu A  {2,3,5, 6,15,30} definisana je relacija  tako da je: x y ako x | y .
Dokazati da je to relacija poretka.
Rešenje: Da bi bila relacija poretka, potrebno je da su ispunjeni uslovi R, A i T.
(R): (x  A) x x  (x  A) x | x , što je tačno jer svaki broj iz skupa A deli samoga
sebe.
(A): (x, y  A) x y  y  x  x  y  (x, y  A) x | y  y | x  y  x što takođe nije
teško zaključiti.
(T): (x, y, z  A) x y  y  z  x z  (x, y, z  A) x | y  y | z  x | z . Ovo tvrđenje
je poznata teorema deljivosti brojeva, ali pošto je još uvek ne znamo dokazaćemo je
služeći se poznatim stvarima. Ako broj x deli broj y onda se y može zapisati kao x puta
neki broj, pa je y=kx, isto to važi i za y i z, pa se može zapisati z=ly, pa ako iz prve
jednaosti zamenimo u drugu y dobijamo z=lkx odakle sledi da broj x deli z što je i trebalo
dokazati.
10. Dopuniti relaciju   {(a, a),(a, c),(b, d ),(c, d )} dodajući joj minimalan broj
elemenata tako da ona postane relacija ekvivalencije na skupu A  {a, b, c, d} .
11. U skupu jednačina:
x 1


J   x  2  0, x  1  0, 2 x  4  0,  , x 2  4, 2 x  2  2 
2 2


uvedena je relacija j1  j2  jednačine j1 i j2 su ekvivalentne. Dokazati da je ~ relacija
ekvivalencije, odrediti klase i količnički skup.
Download

RELACIJE