IB005 úkol 4, příklad 2 Odevzdání: 18. 3. 2024 12:00
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.
2. [0,5 bodu] Uvažte následující čtyři relace na slovech nad abecedou Σ = {a, b, c}:
a) uR1v
def
⇐⇒ 2 | #a(u) ⇐⇒ 2 | #a(v)
b) uR2v
def
⇐⇒ u a v začíná na stejný počet písmen a
c) uR3v
def
⇐⇒ u končí na a ∧ v končí na a
d) uR4v
def
⇐⇒ u končí na aa ⇐⇒ v končí na aa
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, toto tvrzení nedokazujte, pouze 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 ze skript,
nezapomeňte však, že pokud se odvoláváte na definice, věty nebo důkazy z materiálů, musíte vždy
uvést, kde a jak je používáte).
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.