Zhrnutie na Binárne relácie a ich reprezentácia

## Úvod Binárne relácie sú základným nástrojom na popis vzťahov medzi dvojicami prvkov. V tejto látke sa naučíme, čo je karteziánsky súčin, čo znamená binárna relácia, ako sa relácie zapisujú a ako ich možno graficky znázorniť. Materiál je určený pre samoukov (Not attending student) a obsahuje príklady a použitie v praxi. ## Základné pojmy ### Karteziánsky súčin > **Definícia:** Karteziánsky súčin dvoch množín $A$ a $B$ je množina všetkých usporiadaných dvojíc $[x,y]$, pre ktoré platí $x\in A$ a $y\in B$, označujeme ho $A\times B$. - Ak $A = \{1,2\}$ a $B = \{a,b\}$, potom $$A\times B = \{[1,a],[1,b],[2,a],[2,b]\}$$ - Poradie prvkov v usporiadanej dvojici je dôležité: $[1,a] \neq [a,1]$ ak prvky nie sú rovnaké. ### Binárna relácia > **Definícia:** Binárna relácia $R$ na množinách $A$ a $B$ je ľubovoľná podmnožina karteziánskeho súčinu $A\times B$. Relácia obsahuje tie usporiadané dvojice $[x,y]$, pre ktoré platí $xRy$. - Zápis: $R \subseteq A\times B$, alebo explicitne $R = \{[x,y] \in A\times B \mid xRy\}$. - Príklad: Na množine osôb definujeme reláciu "byť starší ako". Ak $A$ obsahuje veky dvoch osôb, relácia bude obsahovať dvojice, kde prvý vek je väčší. ### Usporiadaná dvojica > **Definícia:** V usporiadanej dvojici $[x,y]$ nazývame $x$ prvkom na prvom mieste a $y$ prvkom na druhom mieste. - Poznámka: Pri práci s reláciami vždy berieme do úvahy poradie. ## Grafické znázornenie relácií > **Definícia:** Binárnu reláciu možno znázorniť pomocou orientovaného grafu, kde každý prvok množiny je vrchol a každá usporiadaná dvojica $[x,y]$ je orientovaná hrana od $x$ do $y$. - Orientovaná šípka z $x$ do $y$ reprezentuje $[x,y]$. - Ak $[x,x]$ patrí do relácie, znázorní sa slučkou pri vrchole $x$. Príklad: Množina vrcholov $\{1,2,3\}$ a relácia $R = \{[1,2],[2,3],[1,1]\}$ sa graficky zobrazí šípkami $1\to 2$, $2\to 3$ a slučkou pri $1$. ## Porovnanie súvisiacich pojmov | Pojem | Charakteristika | | --- | --- | | Karteziánsky súčin $A\times B$ | Množina všetkých usporiadaných dvojíc $[x,y]$ s $x\in A$, $y\in B$ | | Binárna relácia $R$ | Podmnožina $A\times B$, obsahuje len tie dvojice, ktoré spĺňajú vzťah $xRy$ | | Usporiadaná dvojica $[x,y]$ | Dôležité je poradie: prvok na prvom mieste a na druhom mieste | | Grafické znázornenie | Orientovaný graf: hrany reprezentujú dvojice, slučka znamená $[x,x]$ | ## Vlastnosti relácií (stručný prehľad) - Relácia môže byť definovaná na dvoch rôznych množinách alebo na tej istej množine. - Relácie môžu mať vlastnosti ako reflexívnosť, symetrickosť, antisymetrickosť, tranzitivita — tieto vlastnosti sú predmetom ďalšieho štúdia. ## Praktické príklady a aplikácie 1. Rôzne reálne vzťahy: "byť starší ako", "byť vyšší ako", "byť rovnobežný s" sú binárne relácie medzi objektmi. 2. Databázy: vzťah medzi dvoma tabuľkami možno chápať ako množinu dvojíc (kľúč z tabuľky A, kľúč z tabuľky B). 3. Grafy a siete: orientované hrany v sieťach predstavujú binárne relácie medzi uzlami. ## Krok za krokom: Ako vytvoriť reláciu 1. Určite množiny $A$ a $B$. 2. Vypíšte karteziánsky súčin $A\times B$ ak potrebujete všetky možnosti. 3. Definujte podmienku, kedy $xRy$ platí. 4. Zostavte podmnožinu $R$ z prvkov $A\times B$ spĺňajúcich túto podmienku. ## Príklad so všetkými krokmi Nech $A = \{1,2,3\}$ a definujme reláciu "deliť bez zvyšku" na $A$ sám so sebou: $xRy$ ak $x$ delí $y$. - Karteziánsky súčin: $$A\times A = \{[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]\}$$ - Relácia $R = \{[1,1],[1,2],[1,3],[2,2],[3,3]\}$, pretože $1$ delí všetko, $2$ delí $2$, $3$ delí $3$. - Graficky: šípky 1\to1 (slučka), 1\to2, 1\to3, 2\to2, 3\to3. Fun fact: Binárne relácie sú základom pre definíciu funkcií; funkcia je špeciálny typ relácie, kde každému prvku z jednej množiny prislúcha práve jeden prvok z druhej množiny.