Zhrnutie na Binárne relácie a karteziánsky súčin

## Úvod Binárne relácie a množinové operácie sú základom pre porovnávanie prvkov v matematike a informatike. V tejto kapitole si vysvetlíme základné pojmy, ukážeme, ako sa relácie zapisujú, zobrazujú a použijú v praxi, a porovnáme súvisiace koncepty pre ľahšie zapamätanie. ## Základné pojmy > **Definícia (Binárna relácia):** Binárna relácia na množinách A a B je ľubovoľná podmnožina karteziánskeho súčinu $A\times B$. Reláciu zapisujeme ako $R \subseteq A\times B$ a platí, že pre usporiadanú dvojicu $[x,y]$ máme $x\,R\,y$ práve vtedy, keď $[x,y] \in R$. > **Definícia (Karteziánsky súčin):** Karteziánsky súčin dvoch množín A a B je množina všetkých usporiadaných dvojíc $[x,y]$ takých, že $x\in A$ a $y\in B$. Zapisujeme $A\times B$. > **Definícia (Usporiadaná dvojica):** Usporiadaná dvojica $[x,y]$ určuje poradie prvkov: prvok $x$ je prvý a prvok $y$ je druhý; $[x,y]$ sa líši od $[y,x]$ všeobecne. ## Rozklad tém na menšie časti ### Karteziánsky súčin - Ak $A = \{1,2\}$ a $B = \{a,b\}$, potom $$A\times B = \{[1,a],[1,b],[2,a],[2,b]\}.$$ - Karteziánsky súčin je základom pre všetky možné binárne relácie medzi A a B. ### Binárna relácia - Relácia je ľubovoľná podmnožina $A\times B$. Napr. ak $A=B=\{1,2,3\}$ a relácia "byť menší" definujeme ako $R = \{[1,2],[1,3],[2,3]\}$, potom $1\,R\,2$ a $2\,R\,1$ neplatí. - Značenie: reláciu môžeme zapisovať aj explicitne $R = \{[x,y],\dots\}$ alebo popisne: $x\,R\,y \Leftrightarrow x<y$. ### Grafické znázornenie relácií - Reláciu na konečnej množine môžeme kresliť ako orientovaný graf: vrcholy predstavujú prvky množiny, orientované šípky znázorňujú usporiadané dvojice. - Poznámka: usporiadanú dvojicu $[x,x]$ zobrazíme slučkou (šípka z vrcholu späť do seba). Fun fact: Binárne relácie sú univerzálny nástroj — používajú sa pri modelovaní príbuzenských väzieb, poradia úloh v plánovaní a prepojení webových stránok. ## Vlastnosti binárnych relácií (stručne) Používajú sa tieto bežné vlastnosti, ktoré pomáhajú kategorizovať relácie: - Reflexívnosť: pre všetky $x$ platí $x\,R\,x$. - Symetrickosť: ak $x\,R\,y$, potom $y\,R\,x$. - Antisymetrickosť: ak $x\,R\,y$ a $y\,R\,x$, potom $x=y$. - Transitívnosť: ak $x\,R\,y$ a $y\,R\,z$, potom $x\,R\,z$. ### Tabuľka porovnania vlastností | Vlastnosť | Význam | Príklad relácie | | --- | --- | --- | | Reflexívna | $\forall x\; x\,R\,x$ | Rovnako "byť rovný" | | Symetrická | $x\,R\,y \Rightarrow y\,R\,x$ | "Byť priateľom" | | Antisymetrická | $x\,R\,y$ a $y\,R\,x \Rightarrow x=y$ | "\u2264" na číslach | | Transitívna | $x\,R\,y$ a $y\,R\,z \Rightarrow x\,R\,z$ | "\u2264" na číslach | ## Praktické príklady a aplikácie 1. Porovnávanie dát: relácia "byť starší" medzi ľuďmi je binárna relácia na množine ľudí. Ak $a$ je starší ako $b$, zapíšeme $a\,R\,b$. 2. Databázy: vzťah medzi tabuľkami (napr. "objednávka má zákazníka") môžeme formálne vnímať ako binárnu reláciu medzi množinou objednávok a množinou zákazníkov. 3. Grafové algoritmy: orientované hrany v grafe predstavujú binárnu reláciu medzi vrcholmi; hľadanie dosiahnuteľnosti využíva transitívnosť prechodov. ### Príklad: poradie v \,studentoch Nech $S = \{Anna,Boris,Catka\}$ a relácia $R$ je "má lepšie známky než". Ak Anna má lepšie známky než Boris a Boris má lepšie známky než Catka, potom $R$ je transitívna, pretože Anna\,R\,Catka. ## Ako čítať a zapisovať reláciu - Zapis explicitne: $R = \{[x,y],[y,z],\dots\}$. - Popisne: $x\,R\,y \Leftrightarrow$ (podmienka medzi $x$ a $y$). - Pri práci s množinami používajte vždy $A\times B$ ako univerzum možných usporiadaných dvojíc. Did you know that orientované grafy (digrafy) sú presne binárne relácie na množine vrcholov a mnohé problémy v teorii grafov sú preložené do vlastností relácií? ## Porovnávanie prístupov (rýchly prehľad) | Koncept | Ako ho získať | Kedy použiť | | --- | --- | --- | | Karteziánsky súčin | Všetky možné usporiadané dvojice $A\times B$ | Keď potrebujete univerzum párov | | Binárna relácia | Podmnožina $A\times B$ | Keď definujete konkrétny