IB102 úkol 4, příklad 1 Odevzdání: 14. 10. 2019
Jméno: UČO:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
1. [2 body] Uvažte následující čtyři relace na slovech nad abecedou {a, b}:
u R1 v ⇐⇒ #a(u) = #a(v) ∧ #b(u) = #b(v)
u R2 v ⇐⇒ u je prefixem v
u R3 v ⇐⇒ |u| mod 3 = 0 ⇔ |v| mod 3 = 0
u R4 v ⇐⇒ (|u| ≤ 1 ∧ u = v) ∨ (poslední dva znaky u jsou stejné jako poslední dva znaky v)
Pro každou z uvedených relací rozhodněte, zda se jedná o ekvivalenci. Pokud to není ekvivalence,
dokažte proč. Pokud to ekvivalence je, určete její index a popište jednotlivé třídy rozkladu podle
dané relace. Následně rozhodněte, zda jde o pravou kongruenci a své tvrzení dokažte (s důkazem, že
relace je pravá kongruence, vám může pomoct tvrzení 2.21 z třetí přednášky).
Zde uvádíme praktickou pomůcku pro lepší přehled:
ekvivalence? index a třídy rozkladu
důkaz
pravá kongruence? důkaz
důkaz
ano
ne
ε ano
ne
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.