IB005 úkol 4, příklad 2 Odevzdání: 21. 3. 2022 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í tři relace na slovech nad abecedou Σ = {a, b, c}:
s R1 t
def
⇐⇒ |s| < 2 ∧ s = t ∨ |s| ≥ 2 ∧ |t| ≥ 2 ∧ penultimate(s) = penultimate(t)
s R2 t
def
⇐⇒ s = sR =⇒ t = tR
s R3 t
def
⇐⇒ #a(s) + #b(s) = |t| − #c(s) ∧ #a(s) mod 2 = #a(t) mod 2
Operace penultimate z relace R1 je operace, která vrací předposlední písmeno slova (je definovaná
pouze pro slova s délkou alespoň 2).
Formálně bychom ji definovali následovně:
penultimate(s) =
d, kde ∃u ∈ Σ∗, e ∈ Σ: u · d · e = s ∧ |d| = 1 pokud |s| ≥ 2,
nedefinováno pokud |s| < 2.
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.