IB 102 — úkol 4, příklad 1 — řešení
Odevzdání: 15.10. 2012
Vypracoval: James Bond Skupina: MI6
UCO: 007
1. [3 body] Uvažte následující čtyři relace nad abecedou {a, b}:
uRiV uR,2V uR%v uR^v
a) Zjistěte, které z uvedených relací nejsou reflexivní a dokažte to o nich.
b) Zjistěte, které z uvedených relací nejsou tranzitivní a dokažte to o nich.
c) Zjistěte, které z uvedených relací nejsou pravou kongruencí a dokažte to o nich. U relací, které jsou pravou kongruencí určete jejich index.
a) Z uvedených relací není reflexivní R\. Uvažme například slovo u = aa. Neplatí, že aa Ri aa, neboť \aa\ < 10. Neplatí tedy, že všechna slova nad danou abecedou jsou v relaci R\ samy se sebou a relace R\ tak není reflexivní.
b) Relace R2 není tranzitivní. Jako protipříklad uvažme slova u = aa, v = aaa a w = aaaa. Platí, že u R2 v a v R2 w, neboť délka u a délka v se liší maximálně o 1, stejně jako délka v a délka w. Už však neplatí, že u R2 w, neboť délka íiaiose liší o 2. Relace R2 tedy není tranzitivní.
c) Relace R\ není reflexivní, není tudíž ekvivalencí, a proto není ani pravou kongruencí. Relace R2 není tranzitivní, není tudíž ekvivalencí, a proto není ani pravou kongruencí. Relace R% je pravou kongruencí s nekonečným indexem.
Relace R4 je ekvivalencí, ale není pravou kongruencí. Uvažme například slova u = aa, v = ab a slovo w = a. Platí, že u R4 v, neboť \u\ = \v\ = 2 a slova u a v se shodují na první pozici. Neplatí však, že uw R4 vw, neboť uw 7^ vw a zároveň \uw\ 7^ 2n pro žádné n. Relace f?4 tedy není pravou kongruencí.
Řešení