Příklady o relacích
Zkoušejte hledat řešení (důkazy) pro následující příklady.
Mnoho zdaru!
Příklad 2.1. Na množině všech přirozených čísel od 0 do 1000 definujeme
binární relaci R následovně: (a, b)  R právě když platí
a) -1  a2 - b2  4,
b) 0  a - b  1 nebo číslo a je trojnásobkem čísla b,
c) 0  a - b  1 nebo číslo a je polovinou čísla b.
Odpovězte, jaké vlastnosti relace R má: je reflexivní, symetrická, antisymetrická,
tranzitivní? Pokud některou z těchto vlastností relace R nemá,
napište konkrétními čísly protipříklad.
Příklad 2.2. Mějme relaci soudělnosti nad přirozenými čísly, kde dvě
čísla x, y jsou v relaci pokud mají společného dělitele většího než 1. Které z
vlastností z Definice tato relace má?
Příklad 2.3. Nakreslete si částečné uspořádání dělitelností čísel 1, . . . , 12
Hasseovým diagramem.
a) Jaký je v něm nejdelší řetězec?
b) Je v něm nejmenší či největší prvek?
c) Kolik je tam maximálních prvků?
Příklad 2.4. Na systémy všech 5-prvkových podmnožin množiny
{1, 2, . . . , 12} definujeme ekvivalenci následovně: Dvě množiny jsou ekvivalentní,
pokud mají stejné nejmenší číslo. Kolik tříd ekvivalence v příslušném
rozkladu získáme? Jak velká je největší třída?
Příklad 2.5. Na množině všech slov-řetězců nad běžnou abecedou definujme
relaci následovně: Slovo x je v relaci se slovem y pokud je y obsaženo
jako podřetězec v x. O jaký známý typ relace se jedná? Zdůvodněte.
Příklad 2.6. Na množině všech slov-řetězců nad běžnou abecedou definujme
relaci následovně: Slovo x je v relaci se slovem y pokud lze x získat z
y jen přeházením písmen. O jaký známý typ relace se jedná? Zdůvodněte.
Příklad 2.7. Mezi všemi studenty na přednášce UInf definujeme
následující binární relaci: Každý student je v relaci sám se sebou, tj. je
1
to reflexivní relace. Každý student A je v relaci s jiným studentem B, právě
když B sedí
a) ve stejné řadě nalevo od A,
b) ve stejné řadě jako A nebo v řadě hned za A,
c) v poslední řadě (nezáleží, kde sedí A),
d) v některé řadě před A.
Jaké vlastnosti má tato relace (jako symetrická, antisymetrická, tranzitivní)?
Jedná se třeba o částečné uspořádání nebo o ekvivalenci? Vaši
odpověď dobře zdůvodněte.
2