Relacija je matematično orodje, s katerim opišemo odnos med elementi množic. V matematiki se z relacijami srečujemo pogosto, pri čemer so primeri relacij: enakost (), relacija "manjše ali enako" (), inkluzija množic () in deljivost števil (). Slednji primeri relaciji so dvomestne ali binarne relacije – možno pa je definirati tudi relacije za več elementov iz več različnih množic.[1]

Relacijski graf :

Formalno je (dvomestna) relacija iz množice v množico podmnožica kartezičnega produkta :

.

Ponavadi uporabimo zapis ( je v relaciji z ), da označimo dejstvo, da je .

Zgledi

uredi
  • Relacija   v množici  .
  • Relacija ekvipolence  
  • Relacija urejenosti  
  • Relacija "je večje kot"   v množici naravnih števil  . Relacija   je enaka:  . Vmesni način zapisa   je veliko bolj naraven kot zapis  .
  • Vsaka funkcija   je enočlena relacija, saj je njen graf  . Pri funkciji vsakemu   priredimo natanko en  . Torej ima lastnost enoličnosti. To pri splošni relaciji ni nujno, poleg tega pa je element   lahko povezan z več elementi iz  .

Posebne relacije in operacije

uredi
  •   imenujemo polna relacija, če je  .
  •   se imenuje prazna relacija. Definirana je kot:  .
  • Relacija identitete ali enakosti   v množici   je množica urejenih parov z enakima koordinatama:  .
  •   imenujemo inverzna relacija. Pridelamo jo tako, da zamenjamo koordinati v vseh parih relacije  :  .
  •   je komplement relacije. Definiran je kot množica vseh parov iz  , ki niso v relaciji  :  .
  • Produkt relacij   je definiran z naslednjim opisom:   natanko tedaj, ko  .

Definicijsko območje in zaloga vrednosti

uredi

Naj bo   relacija v množici  . Definicijsko območje relacije  , označeno z  , je množica vseh prvih koordinat parov iz relacije  . Zaloga vrednosti relacije  , označena z  , je množica vseh drugih koordinat parov iz relacije  :[2]

 
 

Na primer, za relacijo   je definicijsko območje  , zaloga vrednosti pa  .

Lastnosti relacij

uredi

Naj bo   relacija v množici  . Pravimo, da je relacija:

  •   refleksivna  
  •   simetrična  
  •   antisimetrična  
  •   tranzitivna  
  •   sovisna  
  •   enolična  .

Zgornje lastnosti relacij se odražajo tudi grafično na relacijskem grafu. Na primer, če je   refleksivna, potem je v vsaki točki relacije grafa   zanka (zanka v   je usmerjena povezava, ki povezuje vozlišče samo s seboj). Če je   simetrična, potem vse povezave v   nastopajo v parih. To pomeni, da če imamo povezavo od   do  , obstaja tudi obratna povezava. Če je   tranzitivna, potem velja – če iz nekega vozlišča grafa   lahko pridemo v drugo v dveh korakih, lahko pridemo tudi v enem.

Ekvivalenčna relacija

uredi

Kadar je relacija   hkrati refleksivna, simetrična in tranzitivna, je   ekvivalenčna relacija.

Ovojnice relacij

uredi

Ovojnica relacije je najmanjša relacija z določeno lastnostjo  , ki vsebuje dano relacijo. Najpogosteje obravnavane ovojnice so refleksivna ovojnica, simetrična ovojnica, tranzitivna ovojnica in tranzitivno-refleksivna ovojnica. Refleksivna ovojnica relacije   je enaka  , njena simetrična ovojnica pa je enaka  .

Tranzitivno ovojnico relacije   označimo z  . Je unija vseh pozitivnih potenc relacije  :

 

Tranzitivno-refleksivno ovojnico relacije   označimo z  , definirana je zelo podobna kot  . Velja da je   unija vseh nenegativnih potenc relacije  :

 

Zgled tranzitivne ovojnice

uredi

Naj bo relacija   na množici  . Relacija   sama po sebi ni tranzitivna, saj na primer velja   in  , ampak ne velja  . Da lahko pridelamo   v tranzitivno relacijo, ji moramo dodati vse pare, ki manjkajo zaradi tranzitivnosti. Tranzitivna ovojnica   je torej:

 .

Sklici

uredi
  1. Tepeh, Aleksandra; Škrekovski, Riste; Univerza v Mariboru, Fakulteta za elektrotehniko, računalništvo in informatiko; Univerza v Ljubljani, Fakulteta za matematiko in fiziko (2018). Diskretna matematika (v angleščini). Univerzitetna založba Univerze v Mariboru. doi:10.18690/978-961-286-152-0. ISBN 978-961-286-152-0.{{navedi knjigo}}: Vzdrževanje CS1: več imen: seznam avtorjev (povezava)
  2. Fijavž, Gašper (2015). Diskretne strukture. ISBN 9789616209854.