PRUMYSL.CZ KONSTRUKTER.CZ 3D-TISK.CZ MATEMATIKA.CZ NOVAMEDIA.CZ

Binární relace

Zobrazit kapitoly článku
  1. Relace
  2. Operace s relacemi
  3. Binární relace
  4. Binární relace na množině
  5. Relace ekvivalence
  6. Relace uspořádání
  7. Svazy

Binární relace je speciální typ relace s aritou dva. Mezi typické binární relace patří například menší než, rovnost, dělitelnost, větší než, apod.

Ukázky #

Binární relace je jedna z typických a běžně se vyskytovaných relací. Zároveň má některé zajímavé vlastnosti, které si zde popíšeme.

Příkladem binární relace může být: vztah „otec – syn“, dvojice „dopravní prostředek – počet kol“ či obecnější „objekt – vlastnost objektu“. Objektem může být zvíře a vlastností počet nohou, průměrná délka života, počet chlupů na hlavě a podobně.

Binární relaci R mezi množinami M1 a M2 můžeme definovat takto: \(R \subseteq M_1 \times M_2\). Binární relace je tak množina dvojic, přičemž tato množina je podmnožinou kartézského součin dvou množin, mezi kterými relaci zavádíme. Takže relace „otec – syn“ může být relaci mezi množinami všech lidí, mezi množinami všech lidí v Evropě nebo v Praze. Množinu můžeme omezit i jiným směrem, můžeme říci, že tu relaci definujeme mezi množinami všech mužů, ne lidí obecně.

Pro binární relace obvykle používáme speciální značení. Místo toho, abychom psali \([a, b] \in R\), můžeme napsat aRb. Například místo \([3, 1] \in >\) můžeme napsat 1 > 3. Podobně pro ostatní relace. Takže zápis aSb je ekvivalentní zápisu \([a, b] \in S\).

Inverzní relace #

Inverzní relace je relace opačná k současné relace. (Pozor, neplést s doplňkem relace.). Jaká je opačná relaci k relaci menší než? Větší než. Pokud relace menší než obsahuje prvek [4, 7], tedy 4 < 7, tak inverzní prvek bude opačný: 7 > 4, v inverzní relaci bude inverzní dvojice [7, 4].

Máme-li relaci \(R \subseteq M_1 \times M_2\), tak inverzní relace R−1 sestrojíme tak, že vezmeme všechny prvky \([a, b] \in R\) a do R−1 vložíme jejich inverzi. Tedy pokud relace R obsahuje prvek [a, b], tak relace R−1 musí obsahovat prvek [b, a]. Platí to i naopak, pokud R−1 obsahuje prvek [b, a], pak relace R musí obsahovat prvek [a, b].

Kdybychom to zadefinovali, tak relace R−1 je inverzní k R právě když platí:

\[\forall a\in M_1\,\forall b\in M_2:\quad [a, b]\in R \Leftrightarrow [b, a]\in R^{-1}\]

Platí tak, že 6 < 8 právě když 8 > 6. Podobně pro další dvojice.

Skládání relací #

Binární relace můžeme mezi sebou skládat. Mějme dvě relace, první, R, bude „být otcem svého syna“ a druhá, S, „být bratrem své sestry“. Relace R tak obsahuje dvojice [otec, syn], druhá relace obsahuje dvojice [bratr, sestra].

V tuto chvíli zkusíme relace složit. Vznikne nám nová relace, označíme ji \(R \circ S\), přičemž tato relace obsahuje prvek [a, c] právě když \([a, b] \in R\) a zároveň \([b, c] \in S\). Všimněte si, že se v obou prvcích vyskytuje b, jednou na druhém místě a pak na prvním místě dvojice. To je jakýsi propojovací prvek skládání.

Příklad: R = {[Tonda, Marek], [Petr, Jakub]} a S = {[Marek, Jana], [Marek, Lenka], [Jakub, Lucie]}. Tonda je otcem Marka, Petr je otcem Jakuba. Marek má sestry Janu a Lenku a Jakub má sestru Lucii.

Nyní složíme relace: \(R \circ S\). Hledáme takovou dvojici z R, která má na místě syna někoho, kdo je veden jako bratr v relaci S. Například tyto dvě dvojice: [Tonda, Marek] a [Marek, Jana]. Marek je propojovací element, ten dále nepotřebujeme a ze zbylých jmen vytvoříme novou dvojici: [Tonda, Jana]. Relace \(R \circ S\) tak obsahuje dvojici [Tonda, Jana]. Marek má ještě jednu sestru, Lenku, tu také přidáme do složené relace: [Tonda, Lenka]. Nakonec zbývá syn Jakub. Ten má sestru Lucii. Takže máme dvě dvojice: [Petr, Jakub] a [Jakub, Lucie]. Tím vytvoříme další prvek: [Petr, Lucie].

Výsledkem je relace: \(R \circ S = {[Tonda, Jana], [Tonda, Lenka], [Petr, Lucie]}\). Jak bychom mohli tuto relaci pojmenovat? Nejspíše „být otcem své dcery“.

Ještě jednou celá definice:

\[[a, c] \in (R \circ S) \Leftrightarrow \exists b\quad [a, b] \in R \wedge [b, c] \in S\]

Poznámka: někdy se používá obrácený zápis, to znamená, že pro stejnou definici by se místo \(R \circ S\) použilo \(S \circ R\).

 

Tento web používá k poskytování služeb, personalizaci reklam a analýze návštěvnosti soubory cookie. Používáním tohoto webu s tím souhlasíte. Další informace