Binární relace

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Binární relace je pojem z matematiky, vyjadřuje vztah (relaci) prvků jedné množiny k prvkům v množině druhé.

Příklad: Mějme množiny čísel A = (1, 5, 8), B = (3, 5, 6). Definujeme vztah (binární relaci) „je větší“ prvků z A k prvkům z B. Vidíme, že číslo 8 (z množiny A) „je větší“ než číslo 3 z B. A říkáme, že prvek 8 je v binární relaci „je větší“ s prvkem 3, zkráceně (8 „je větší“ 3). Většinou prvky které jsou v binární relaci značíme jen jako uspořádanou dvojici [8,3]. Binární relaci z tohoto příkladu lze popsat jako množinu uspořádaných dvojic R = ([8,3], [8,5], [8,6], [5,3]). Na množinu R lze nahlížet jako na podmnožinu kartézského součinu A\times B. Množiny (A, B, R) lze použít jako definici binární relace.

Formální definice[editovat | editovat zdroj]

Binární relace je uspořádána trojice [A,
 B,
 R], kde A a B jsou libovolné množiny a R je podmnožina kartézského součinu A\times B. Množině A se říká definiční obor, množině B obor hodnot a množinu R nazýváme graf relace.

Značení relací[editovat | editovat zdroj]

Binární relace značíme uspořádanou dvojicí [x,
y] nebo pokud chceme rozlišit o kterou relaci se jedná pak (x
 R
 y), kde x\in A, y\in B a R je označení příslušné množiny z definice.

Druhy relací[editovat | editovat zdroj]

Binární relace je

Příkladem může být relace  R = „je sourozenec“. Je-li A i B množinou všech mých příbuzných, pak musí existovat (já R sestra) a také (sestra R já). (Pokud sourozence nemám, je množina relací prázdná, i taková relace je symetrická).
Příkladem může být už zmíněná relace "je sourozenec" nebo relace "je vyšší". Já jsem vyšší než Petr,(a současně) Petr je vyšší než Ondřej, z toho plyne: Já jsem vyšší než Ondřej. Tranzitivní relací například není relace "být kamarád". Já jsem kamarád Petra, on je kamarád Ondřeje, z toho ale nevyplývá kamarádství mezi mnou a Ondřejem.
  • reflexivní pokud pro všechny x patřící X platí (x  R
 x), to znamená pokud je prvek x v relaci sám se sebou. (Samozřejmě, že první x pochází z množiny A a druhé x pochází z B. Mohou to být stejné množiny.)
Příklad reflexivní relace je "je stejný", příklad nereflexivní je "je vyšší". Neplatí, že (já "je vyšší"(než) já).

Relaci, která je reflexivní, symetrická, a tranzitivní nazýváme relace ekvivalence.

Relaci, která je reflexivní, antisymetrická a tranzitivní nazýváme částečné uspořádání.

Další typy: úplné uspořádání, dobré uspořádání.

Operace[editovat | editovat zdroj]

Na množině binárních relací jsou definovány následující operace - jejich výsledkem je opět relace

  • Inverzní relace k relaci R je taková relace R-1 (R-1) mezi množinami B a A, obsahující právě ty [y,x] ? B × A, že [x,y] ? R.
  • Relace složená z relací R a S je relace T = S \circ R (R složeno s S) z množiny A do množiny C, která obsahuje právě taková [x,z] ? A × C, pro něž existuje takový prvek y v množině B, že [x,y] ? R a [y,z] ? S, tedy
R \circ S = \{[x,z]; \exists y \in B: [x,y] \in R \and [y,z] \in S\}
  • Průnik relací R a S je relace R?S obsahující pouze takové uspořádané dvojice, které se nacházejí současně v obou relacích. Tedy R?S = {[x,y]; [x,y]?R ? [x,y]?S}
  • Sjednocení relací R a S je relace R?S obsahující takové uspořádané dvojice, které se nacházejí alespoň v jedné z relací. Tedy R?S = {[x,y]; [x,y]?R ? [x,y]?S}