Základy matematiky -- podzim 2008 -- 1. termín -- 19.1.2009
Jméno:. . . . . . . . . . . . . . . . . . . . . . . . . .
test
Hodnocení
cel.suma zn.
UČO: . . . . . . . . . . . . . . . . . . . . . . . . . .
1 2 3 4 5 6 7 8 9
1. (7krát 1 bod (správně 1 bod, chybně -1, bez odpovědi 0 -- při záporném součtu se do celkového hodnocení
započítá 0))
Odpovězte (škrtnutím nehodícího se ano nebo ne na patřičném řádku), zda jsou pravdivá následující
tvrzení (čtěte velmi pozorně!):
(a) ano -- ne Množina všech konečných podmnožin množiny N je spočetná.
(b) ano -- ne Pro libovolné množiny A, B, C a zobrazení f : A  B, g : B  C platí:
f je injektivní a g je surjektivní = g  f je bijekce.
(c) ano -- ne Pro každé uspořádání R množiny N existuje minimální nebo maximální prvek v
(N, R).
(d) ano -- ne Má-li podmožina X uspořádané množiny infimum, pak má i supremum.
(e) ano -- ne Číslo 0 je neutrální prvek v grupoidu (Z, -).
(f) ano -- ne Pokud binární relace R na množině A je reflexivní, pak R-1
je také reflexivní.
(g) ano -- ne Existuje jediný izomorfismus uspořádané množiny (Z, ) do sebe.
2. (7 bodů) Definujte formálně Zn (množinu zbytkových tříd modulo n). Definujte operace + a  na
Zn a napište, co je třeba ukázat, aby tato definice byla korektní. Určete, pro která n  N je (Zn, )
grupa a pro která n  N je (Zn, +, ) těleso.
3. (3krát 2 body) Politická strana má k dispozici 10 kandidátů ­ 5 mužů a 5 žen. Určete, kolika
způsoby lze vytvořit kandidátní listinu (tj. pořadí kandidátů) tak, aby
(a) -- (bez omezení);
(b) na prvních 3 místech byly ženy;
(c) se pravidelně střídali muži a ženy.
Odpověď: a) b) c)
4. (5krát 2 body) Udejte příklad
(a) svazu, který nemá maximální prvek;
(b) nespočetného úplného svazu;
(c) konečné grupy, která není komutativní;
(d) relace ekvivalence R na množině N, pro niž má rozklad N\R právě 2 prvky;
(e) uspořádání na množině Z, kde je nekonečně mnoho maximálních prvků, nekonečně mnoho
minimálních prvků a každý maximální prvek je větší než libovolný minimální prvek.
5. (10 bodů) Buď n přirozené číslo, n  2. Na množině M = Zn × Z2 definujeme binární operaci 
vztahem
([a]n, [b]2)  ([c]n, [d]2) = ([a + (-1)b
c]n, [b + d]2), pro a, b, c, d  Z .
Dokažte, že daný předpis korektně definuje operaci na množině M.
Určete, pro která n je  asociativní operace.
Určete, pro která n existuje pro operaci  neutrální prvek.
Určete, pro která n je (M, ) grupa.
Určete, pro která n je (M, ) komutativní grupa.
Odpovědi zdůvodněte.
6. (10 bodů) Nechť M je konečná n-prvková množina, n  3.
Určete, kolik je lineárních uspořádání množiny M.
Určete, kolik je uspořádání na množině M, kde existují právě 2 prvky, které jsou nesrovnatelné.
Určete, kolik je uspořádání na množině M, kde existují právě 3 minimální prvky, které jsou menší
než všech zbývajících n - 3 prvků, a kde je těchto n - 3 zbývajících prvků uspořádáno lineárně.
Postup výpočtu komentujte.
7. (10 bodů) Označme M = {x  N | x < 200}. Pro n  M značíme s(n) ciferný součet čísla n  M,
tj. pro n = 100a + 10b + c, kde a, b, c  {0, 1, 2, . . . , 9}, definujeme s(n) = a + b + c.
Na množině M definujme binární relaci  takto:
x  y  (20 | x - y  s(x) = s(y)), pro x, y  M.
Dokažte, že  je relace ekvivalence na množině M.
Popište rozklad M\.
Určete, kolik má tento rozklad tříd a kolik prvků mají jednotlivé třídy.
8. (10 bodů) Buď n  N a A = {1, 2, . . . , n}. Na množině M = P(A) - {} definujeme binární relaci
takto:
X Y  ( min(X) < min(Y )  (min(X) = min(Y )  X  Y ) ), pro X, Y  M.
Dokažte, že je uspořádání množiny M.
Nalezněte všechny minimální a maximální prvky uspořádané množiny (M, ).
Je (M, ) svaz?
Je (M, ) úplný svaz?
Odpovědi zdůvodněte. (Pro X  M, tj. X neprázdnou podmnožinu množiny A, značí min(X) nejmenší
přirozené číslo v X  A vzhledem k velikosti.)
9. (10 bodů) Buď A libovolná množina a R relace na této množině. Pro i  N definujeme induktivně
Ri
takto: R1
= R a Rk+1
= Rk
 R pro k  N. Ekvivalentně: pro a, b  A platí (a, b)  Ri
tehdy a
jen tehdy, když existují prvky a0, a1, . . . , ai  A takové, že a = a0, b = ai a platí (ak-1, ak)  R pro
libovolné k  {1, . . . , i}. Položme nyní R = iN Ri
.
Dokažte, že R je tranzitivní relace.
Dokažte, že R je nejmenší tranzitivní relace obsahující R.
Tzn. ukažte, že pokud S je tranzitivní relace s vlastností R  S potom R  S.
Určete R v případě, kdy A = Z a R = {(n, n + 1) | n  Z}.