Ogled vira Relacija

[[Slika:Matematična relacija -2.png|sličica|Relacijski graf <math>R</math>: <math>R = \{(1,2),(1,3),(3,4),(4,2)\}</math>]]
'''Relacija''' je [[Matematika|matematično]] orodje, s katerim opišemo odnos med elementi [[Množica|množic]]. V matematiki se z relacijami srečujemo pogosto, pri čemer so primeri relacij: [[Relacija enakosti|enakost]] (<math>=</math>), relacija "manjše ali enako" (<math>\le</math>), inkluzija množic (<math>\subseteq</math>) in [[deljivost]] števil (<math>|</math>). Slednji primeri relaciji so dvomestne ali binarne relacije – možno pa je definirati tudi relacije za več elementov iz več različnih množic.<ref>{{Navedi knjigo|title=Diskretna matematika|url=http://press.um.si/index.php/ump/catalog/book/323|publisher=Univerzitetna založba Univerze v Mariboru|date=2018|isbn=978-961-286-152-0|doi=10.18690/978-961-286-152-0|language=en|first=Aleksandra|last=Tepeh|first2=Riste|last2=Škrekovski|last3=Univerza v Mariboru, Fakulteta za elektrotehniko, računalništvo in informatiko|last4=Univerza v Ljubljani, Fakulteta za matematiko in fiziko}}</ref> 

Formalno je (dvomestna) relacija <math>R</math> iz množice <math>A</math> v množico <math>B</math> podmnožica [[Kartezični produkt|kartezičnega produkta]] <math>A \times B</math>: 

:<math>R \subseteq A \times B</math> .
Ponavadi uporabimo zapis <math>aRb</math> (<math>a</math> je v relaciji <math>R</math> z <math>b</math>), da označimo dejstvo, da je <math>(a, b) \in R</math>.

== Zgledi ==
* Relacija <math>R = \{(a,b),(b,c),(c,d)(c,c)\}</math> v množici <math>A = \{a,b,c,d\}</math>.
* [[Relacija ekvipolence]] <math>\sim</math>
* [[Relacija urejenosti]] <math>\le</math>
* Relacija "je večje kot" <math>></math> v množici [[Naravno število|naravnih števil]] <math>\mathbb{N}</math>. Relacija <math>></math> je enaka: <math>\{(2,1),(3,1),(3,2)...,(4,1),...\}</math>. Vmesni način zapisa <math>4 > 1</math> je veliko bolj naraven kot zapis <math>(4,1) \in \; ></math>.
* Vsaka [[Funkcija (matematika)|funkcija]] <math>f: A \to B</math> je [[Enočlena operacija|enočlena]] relacija, saj je njen graf <math>\Gamma = \{(a, f(a)) \mid a \in A\}</math>. Pri funkciji vsakemu <math>a \in A</math> priredimo natanko en <math>f(a) \in B</math>. Torej ima lastnost enoličnosti. To pri splošni relaciji ni nujno, poleg tega pa je element <math>a</math> lahko povezan z več elementi iz <math>B</math>.

== Posebne relacije in operacije ==

* <math>R</math> imenujemo '''polna''' relacija, če je <math>R = A \times B</math>.

* <math>R = \emptyset</math> se imenuje '''prazna''' relacija. Definirana je kot: <math>\emptyset = \{x \mid x \ne x \}</math>.
* Relacija '''[[Identična funkcija|identitete]]''' ali enakosti <math>id_A</math> v množici <math>A</math> je množica urejenih parov z enakima koordinatama: <math>id_A = \{(a,a) \;|\; a \in A \}</math>.
* <math>R^{-1}</math> imenujemo '''inverzna''' relacija. Pridelamo jo tako, da zamenjamo koordinati v vseh parih relacije <math>R</math>: <math>R^{-1} = \{(y,x) \;|\; (x,y) \in R \}</math>.
* <math>R^c</math> je '''komplement''' relacije. Definiran je kot množica vseh parov iz <math>A \times B</math>, ki niso v relaciji <math>R</math>: <math>R^c = \{(x, y) \mid (x, y) \in A \times A \land \neg (xRy)\}</math>.
* '''Produkt relacij''' <math>R * S</math> je definiran z naslednjim opisom: <math>xR * Sy</math> natanko tedaj, ko <math>\exists z (xRz \land zSy)</math>.

== Definicijsko območje in zaloga vrednosti ==
Naj bo <math>R</math> relacija v množici <math>A</math>. Definicijsko območje relacije <math>R</math>, označeno z <math>D_R</math>, je množica vseh prvih koordinat parov iz relacije <math>R</math>. Zaloga vrednosti relacije <math>R</math>, označena z <math>Z_R</math>, je množica vseh drugih koordinat parov iz relacije <math>R</math>:<ref>{{Navedi knjigo|title=Diskretne strukture|last=Fijavž|first=Gašper|year=2015|isbn=9789616209854}}</ref>
:<math>D_R = \{x \mid \exists y \in A \, (x R y)\}</math>
:<math>Z_R = \{y \mid \exists x \in A \, (x R y)\}</math>

Na primer, za relacijo <math>R = \{(a, b), (b, c), (c, d), (c, c)\}</math> je definicijsko območje <math>D_R = \{a, b, c\}</math>, zaloga vrednosti pa <math>Z_R = \{b, c, d\}</math>.

== Lastnosti relacij ==
Naj bo <math>R</math> relacija v množici <math>A</math>. Pravimo, da je relacija:

* <math>R</math> [[Refleksivnost|refleksivna]] <math>\Longleftrightarrow \forall x \in A \; (xRx)</math>

* <math>R</math> [[Simetričnost|simetrična]] <math>\Longleftrightarrow \forall x,y \in A \; (xRy \Rightarrow yRx)</math>

* <math>R</math> antisimetrična <math>\Longleftrightarrow \forall x,y \in A \; (xRy \land yRx \Rightarrow x = y)</math>

* <math>R</math> [[Tranzitivnost|tranzitivna]] <math>\Longleftrightarrow \forall x,y,z \in A \; (xRy \land yRz \Rightarrow xRz)</math>

* <math>R</math> sovisna <math>\Longleftrightarrow \forall x,y \in A \; (x \not = y \Rightarrow xRy \lor yRx)</math>

* <math>R</math> enolična <math>\Longleftrightarrow \forall x,y,z \in A \; (xRy \land xRz \Rightarrow y=z)</math>.
Zgornje lastnosti relacij se odražajo tudi grafično na relacijskem grafu. Na primer, če je <math>R</math> refleksivna, potem je v vsaki točki relacije grafa <math>G_R</math> zanka (zanka v <math>G_R</math> je usmerjena povezava, ki povezuje [[Točka (teorija grafov)|vozlišče]] samo s seboj). Če je <math>R</math> simetrična, potem vse povezave v <math>G_R</math> nastopajo v parih. To pomeni, da če imamo povezavo od <math>x</math> do <math>y</math>, obstaja tudi obratna povezava. Če je <math>R</math> tranzitivna, potem velja – če iz nekega vozlišča grafa <math>G_R</math> lahko pridemo v drugo v dveh korakih, lahko pridemo tudi v enem.

==== Ekvivalenčna relacija ====
Kadar je relacija <math>R</math> hkrati refleksivna, simetrična in tranzitivna, je <math>R</math> [[ekvivalenčna relacija|ekvivalenčna]] relacija.

== Ovojnice relacij ==
Ovojnica relacije je najmanjša relacija z določeno lastnostjo <math>\mathcal{L}</math>, ki vsebuje dano relacijo. Najpogosteje obravnavane ovojnice so refleksivna ovojnica, simetrična ovojnica, tranzitivna ovojnica in tranzitivno-refleksivna ovojnica. Refleksivna ovojnica relacije <math>R</math> je enaka <math>R \cup id_A</math>, njena simetrična ovojnica pa je enaka <math>R \cup R^{-1}</math>.

Tranzitivno ovojnico relacije <math>R</math> označimo z <math>R^+</math>. Je [[Unija množic|unija]] vseh pozitivnih [[Potenciranje|potenc]] relacije <math>R</math>:
:<math>R^{+}=\bigcup_{k = 1}^{\infty} R^k.</math>
Tranzitivno-refleksivno ovojnico relacije <math>R</math> označimo z <math>R^*</math>, definirana je zelo podobna kot <math>R^+</math>. Velja da je <math>R^*</math> unija vseh nenegativnih potenc relacije <math>R</math>:
:<math>R^{*}=\bigcup_{k = 0}^{\infty} R^k.</math>

==== Zgled tranzitivne ovojnice ====
Naj bo relacija <math>R=\{(a,b),(b,c),(c,d)\}</math> na množici <math>A=\{a,b,c,d\}</math>. Relacija <math>R</math> sama po sebi ni tranzitivna, saj na primer velja <math>aRb</math> in <math>bRc</math>, ampak ne velja <math>aRc</math>. Da lahko pridelamo <math>R</math> v tranzitivno relacijo, ji moramo dodati vse pare, ki manjkajo zaradi tranzitivnosti. Tranzitivna ovojnica <math>R^+</math> je torej:
:<math>R^+ =\{(a,b),(b,c),(c,d),(a,c),(b,d),(a,d)\}</math>.

== Sklici ==
{{reflist}}

{{normativna kontrola}}
[[Kategorija:Relacije| ]]
[[Kategorija:Teorija množic]]