IBOOO Úvod do informatiky -- príklady na procvičení
Sada 6 -- Zadání
Téma
Vlastnosti relací. Ekvivalence, rozklad množiny, třídy ekvivalence. Uspořádání, předuspořádání.
Minimální, maximální, nejmenší a největší prvky uspořádaných množin. Horní
a dolní závora, suprémum a infimum. Relace pokrytí na uspořádané množině. Hasseovské
diagramy.
Příklad 1.
a) Dokažte, že každé uspořádání je předuspořádání, ale obrácené tvrzení neplatí.
b) Dokažte, že každá ekvivalence je předuspořádání, ale obrácené tvrzení neplatí.
Příklad 2.
Rozhodněte, které z následujících relací jsou předuspořádání, uspořádání, resp. úplná
uspořádání. Svá tvrzení dokažte. Pokud je to nutné, tak v definicích předpokládáme, že
(A, <A) a (B, <B) jsou uspořádné množiny.
a) R= {(a,6),(6,c),(a,c)} C M x M, kde M = {a,b,c}
b) R = {(a, a), (b, b), (b, c), (c, c)} C M x M, kde M = {a, b, c}
c) R = {(X, Y) | X C Y} C 2A
x 2A
d)R={(f,g)\f(A)Cg(A)}CBA
xBA
e) R = {((a, b), (c, d)) | a <A c a d <A b} C (A x A) x (A x A)
f) R = {{a, b) | 3 c G M : a = b + c} C M x M, kde M = {m e N0 | m < n} pro n e N
g) i? = {(o, 0)} U {(a, b) | a ˇ 6 > 0 V a < b} C Z x Z
h) R = {((a, 6), (a^c)) |_6 < ß c} C (A x B) x (A x B)
\) R={(X,Y) \ X CY}C2A
x2A
Příklad 3.
Nechť R C M x M je předuspořádání na M. Nechť ~ je jádro R. Dokažte, že uspořádaná
množina (M/L,<) indukovaná předuspořádáním i? je dobře definovaná. Tj. dokažte, že
~ C M x M je skutečně ekvivalence a < C M/~ x M/~ je skutečně uspořádání.
Příklad 4.
Nechť R C M x M je ekvivalence (je to tedy i předuspořádání).
a) Jak vypadá jádro R?
b) Jak vypadá uspořádání indukované relací R na příslušném rozkladu?
Příklad 5.
Nakreslete grafy relací a Hasseovské diagramy následujících uspořádaných množin.
a ) (2{a
>6
>c
},C)
b) ( { Í Í G N O |  < 10}, |)
c) ( j n e N o I n< 3},<)
d) ( { n e No j n< 3},id)
Příklad 6.
Pro uspořádané množiny zadané Hasseovskými diagramy
as 4 ďí
&2 C2 C3
(B,<B)
2
(A,<A) (C, <c)
e4
ei e2 e3
nakreslete Hasseovské diagramy (nejen) následujících uspořádaných množin.
a) (B x A,<), kde < je uspořádání po složkách
b) (B x A,^<), kde ^ je lexikografické uspořádání
c) (D x >,<), kde < je lexikografické uspořádání
d) (C x E,^<), kde ^ je uspořádání po složkách
Příklad 7.
Nakreslete Hasseovský diagram množiny funkcí {fi, f2, Í3, fá, Í5, fe, Í7} s uspořádáním
po bodech, kde pro i = 1, 2, 3, 4, 5, 6, 7 jsou funkce /j : N --ˇ N definovány následovně
h(n) = 1
Í2(n) = n h(n)
= n2
h(n) = n2
h(n) = n3
fein) = n2
h(n) = 2n
n
Příklad 8.
Určete jádro předuspořádání R, příslušný rozklad a uspořádání indukované na tomto
rozkladu v případě, že
a) R = {(f, g) I f (A) C g(A)} C BA
x BA
, kde A a B jsou libovolné množiny
b) R = {(0, 0)} U {(a, 6) | a ˇ b > 0 V a < b} C Z x Z
c) i? = {(a, 6) | 3 k,l,m,n G No : a = 5m + fc A 6 = 5n + / Ak < 1} C No x No
d) i? = {(a, 6) | pro každé prvočíslo p platí: p | a = ^ p | 6 } C N x N
Příklad 9.
Určete všechny minimální, maximální, nejmenší a největší prvky uspořádané množiny
a) (2M
, C), kde M je libovolná množina
b)(No,|)
c) ({n E No | n < 10}, |)
d) (Z,idz)
e) (AxE, <), kde < je uspořádání po složkách a uspořádané množiny (A, <A) a (E, <E)
jsou zadané následujícími Hasseovskými diagramy.
ß3 0"i
e4
2
ai ei e2 e3
(A < A ) (E, <E)
Příklad 10.
a) Dokažte, že každá uspořádaná množina má nejvýše jeden nejmenší prvek.
b) Dokažte, že každá uspořádaná množina má nejvýše jeden největší prvek.
Příklad 11.
Pro danou uspořádanou množinu (M, <) a její prvek x určete všechny prvky y, které
prvek x pokrývá, a všechny prvky z, které pokrývají prvek x.
a) (M, <) = (2^b
'c
'd
'e
\ C),x = {a, c, d}
b) (M,<) = (No,|),x = 924
c) (M, <) = (A x B, ^ ) , x = (ci2, 62), kde ^ je lexikografické uspořádání a (A, <X) =
= ({ai, 0,2,0,3}, idA U {(0,1,0,2)}) a (S, <B) = ({bi, b2, 63},idß U{(6i, 62), (&2,&3), (&i,&3)})
Příklad 12.
Najděte takovou uspořádanou množinu, v níž každý prvek kromě minimálních a maximálních
prvků bude pokrývat dva prvky a bude pokrýván třemi prvky, a uspořádaná
množina bude obsahovat alespoň tři takové prvky.
Příklad 13.
Pro danou podmnožinu X uspořádané množiny (M, <) určete její dolní závory, horní
závory, infimum a supremum.
a)
b)
c)
d)
e)
0
g)
M, <) = (2A
, C), kde A je množina a pro n eN je X = {Y C A \ \Y\ = n}
M, <) = (2{a
-V,d,e}; c ) , X = {{6, c}, {c, d}}
M, <) = (2{a
-V,d,e}; c ) , X = {{c}, {a, c, d}}
M, <) = (N, <), X = {n G N I n < n0} pro nějaké í i 0 e N
M, <) = (Z, <), X = {3fc - 2 I k E Z}
M, <) = (No, |), X C N, |X| = n pro nějaké n e N
M , < ) = (No,|),X = {2" I ne N}