1 Princip indukce
1. Dokažte, že pro každé přirozené číslo n platí:
n
i=1
i3
=
n2
(n + 1)2
4
.
2. Dokažte, že pro každé přirozené číslo n platí:
n
i=1
i(i + 5)
(i + 2)(i + 3)
=
n(n + 1)
n + 3
.
3. Dokažte, že pro každé přirozené číslo n ≥ 2 platí:
n
i=2
1
i2
≥
7
12
−
1
n + 1
.
4. Dokažte, že pro každé přirozené číslo n ≥ 6 platí 2n
> (n + 1)2
.
5. Nechť r je reálné číslo takové, že r + 1
r
je celé číslo. Dokažte, že pak pro každé přirozené
číslo n je rn
+ 1
rn rovněž celé číslo.
6. Dokažte, že součet vnitřních úhlů v (konvexním) n-úhelníku je roven π · (n − 2).
7. V konvexním n-úhelníku jsou sestrojeny některé úhlopříčky přitom žádné dvě se neprotínají
ve vnitřním bodě n-úhelníka. Dokažte, že z některých dvou (nesousedních) vrcholů
n-úhelníka nevychází žádná ze sestrojených úhlopříček. (Zde n ≥ 3, resp. n ≥ 4 v případě
tvrzení o nesousedních vrcholech.)
8. Nechť reálné číslo γ a celé číslo l jsou taková, že l cos γ je celé číslo. Dokažte, že potom
pro každé přirozené číslo n je také ln
cos nγ celé číslo.
Návod: Použijte známý goniometrický vzorec
cos α + cos β = 2 cos α+β
2
cos α−β
2
pro α = nγ a β = (n − 2)γ
9. Máme obdélníkovou tabulku čokolády s m × n dílky. Chceme ji rozlámat na jednotlivé
dílky, a to tak, že vždy jeden obdélník rozlomíme na dva obdélníky menší. Kolik obdélníků
musíme rozlomit nejméně a kolik nejvíce?
Návod: Vždy m · n − 1.
2 Logika a přirozená čísla
1. Ověřte, že následující formule jsou ekvivalentní:
(a) A ∨ B
¬A → B
1
(b) A ∧ B
¬(A → ¬B)
(c) A ↔ B
(A → B) ∧ (B → A)
(d) ¬(p ∧ ¬q) ∧ (¬q ∧ ¬r)
¬p ∧ ¬q ∧ ¬r
2. Nalezněte výrokovou formuli v promněných A, B, C s následující tabulkou pravdivostních
hodnot
A B C
1 1 1 1
1 1 0 0
1 0 1 0
1 0 0 0
0 1 1 0
0 1 0 1
0 0 1 0
0 0 0 0
3. Rozhodněte, zda jsou následující formule pravdivé v R, C, Z, N.
(a) (∀x)(∀y)(x < y → (∃z)(x < z < y))
(b) (∀x)(∀y)(∃z)(x + z = y)
(c) (∃z)(∀x)(z ≤ x)
(d) (∀x)(∀y)(∃z)(z|x ∧ z|y ∧ (∀u)((u|x ∧ u|y) → u|z))
(e) (∃x)(∀y)(y + x = x + y = y)
4. Znegujte formule z předešlého příkladu a upravte je do tvaru, ve kterém se bude negace
vyskytovat jen u atomických formulí.
5. Popište následují vlastnosti formulí a diskutuje jejich pravdivost v číselném oboru N.
(a) každé číslo je dělitelné prvočíslem;
(b) existuje nejmenší společný násobek libovolné dvojice čísel.
6. Je možné zaměnit v libovolné formuli predikátové logiky obecný a existenční kvantifikátor?
Diskutujte obě implikace. Konkrétně mějme formuli predikátové logiky se dvěmi volnými
promněnými f(x, y). Platí (∀x) (∃y) f(x, y) ↔ (∃y) (∀x) f(x, z)? Jako příklad formule
f(x, y) uvažujte x ≤ y.
7. Pro každé a ∈ Z, b ∈ N existují jednoznačně určená q, r ∈ Z, 0 ≤ r < b taková, že platí
a = bq + r. Dokažte.
2
3 Množinová algebra a kartézské součiny množin
1. Určete, která z těchto tvrzení jsou pravdivá:
(a) {∅} = ∅
(b) {∅} ∈ {∅, {∅}}
(c) {{∅}, ∅} = {∅, {∅}}
(d) {∅, ∅} = {∅}
(e) {∅} /∈ {∅, {{∅}}}
(f) {{∅}} ∈ {{∅}}
(g) {{∅}} ∈ {{∅}, {{∅}}}
(h) {{∅}} ∈ {∅, {∅, {∅}}}
2. Nechť A, B, C jsou množiny. Určete, kolik prvků má daná množina. (Pozor, odpovědi se
mohou lišit v závislosti na množinách A, B, C.)
(a) {{{∅, ∅}}, ∅, {{∅}, {∅}}, {{∅}}, {{∅}, {∅, ∅}}}
(b) {A, B, C}
(c) {A, {B, C}}
(d) {A, {B}, ∅}
3. Dokažte, že pro libovolné množiny A,B,C platí:
(a) A ∩ B = A − (A − B)
(b) A ∪ B = (A − B) ∪ (B − A) ∪ (A ∩ B)
(c) A − (B ∩ C) = (A − B) ∪ (A − C)
(d) A ÷ (B ÷ C) = (A ÷ B) ÷ C
(e) A ∩ B ⊆ C ⇐⇒ A ∩ (B − C) = ∅
(f) A ⊆ C =⇒ (A ⊆ B ⇐⇒ (C − B) ⊆ (C − A))
4. Rozhodněte, zda pro libovolné množiny A,B,C platí:
(a) A ∩ (B − C) = (A ∩ B) − C
(b) A ∪ (B − C) = (A ∪ B) − C
(c) A ∩ C ⊆ B =⇒
((A ∩ B) ∪ C = A ∩ (B ∪ C) ⇐⇒ (A ∩ B) ∪ C = B ∩ (A ∪ C))
5. Určete, čemu se rovná:
(a) ∅
(b) ∅
(c) {∅}
3
(d) P(A)
(e) P(A)
6. Nechť I, J jsou neprázdné indexové množiny a nechť A, Bi pro i ∈ I a Cj pro j ∈ J jsou
množiny. Dokažte, že platí:
(a) A ∩ i∈I Bi = i∈I(A ∩ Bi)
(b) A ∪ i∈I Bi = i∈I(A ∪ Bi)
(c) A − i∈I Bi = i∈I(A − Bi)
(d)
i∈I
j∈J
(Bi ÷ Cj) =
i∈I
j∈J
(Bi ∪ Cj) −
i∈I
j∈J
(Bi ∩ Cj)
7. Nechť I je neprázdná indexová množina a nechť A, Bi pro i ∈ I jsou množiny. Rozhodněte,
který z následujících vztahů je pravdivý:
(a) i∈I(A ÷ Bi) ⊆ A ÷ i∈I Bi
(b) A ÷ i∈I Bi ⊆ i∈I(A ÷ Bi)
8. Určete, pro které množiny A platí:
(a) A − {∅} = A ∩ {∅, {∅}, {{∅}}}
(b) A ∪ A = {∅, {∅}}
(c) A = {∅, {∅}}
(d) A = A
(e) A = ( A) ∪ {∅}
9. Nechť I značí množinu všech prvočísel. Pro každé prvočíslo p ∈ P označme Ap = {x ∈
N | (p | x)}. Dokažte, že pak platí:
(a) p∈I Ap = N − {1}
(b) p∈I Ap = ∅
(c) je-li J = ∅ libovolná konečná množina prvočísel, pak p∈J Ap = ∅.
10. Nechť A, B, C, I a Ai pro i ∈ I jsou množiny. Dokažte, že platí:
(a) A × (B ∪ C) = (A × B) ∪ (A × C)
(b) (A − B) × C = (A × C) − (B × C)
(c) A × i∈I Ai = i∈I(A × Ai)
(d) A ∩ B = ∅ =⇒ (A × B) ∩ (B × A) = ∅
11. Určete, pro které množiny A, B a pro které systémy množin Ai, i ∈ I, platí:
(a) P(A − B) ⊆ P(A) − P(B)
(b) P(A − B) ⊇ P(A) − P(B)
(c) i∈I P(Ai) = P( i∈I Ai)
(d) i∈I P(Ai) = P( i∈I Ai)
4
4 Zobrazení
1. Najděte všechna zobrazení množiny A = {1, 2, 3} do množiny B = {i, a}. Najděte všechna
zobrazení množiny B do množiny A. Které z nich jsou bijekce, injekce a surjekce?
2. Určete kolik je zobrazení z konečné a-prvkové množiny A do konečné b-prvkové množiny
B. Rozhodněte, zda je některé z nich injekce, surjekce, resp. bijekce.
3. Pro které konečné množiny A
(a) existuje injektivní zobrazení {0, 1}A
→ A × A,
(b) existuje surjektivní zobrazení A × A → AA
?
4. Nechť A, B jsou neprázdné množiny. Udejte podmínku, která
(a) je nutná a není dostatečná,
(b) je dostatečná a není nutná,
pro to, aby zobrazení f : A → B bylo surjektivní.
5. Rozhodněte zda následující předpisy určují zobrazení? V kladném případě zjistěte, zda je
zobrazení injektivní, příp. surjektivní.
(a) f : Z →]0, 1[, f(x) = |x|,
(b) f : Z → {0, 1, 2}, f(x) =



0 pro x = 0
1 pro x > 1
2 pro x < 2
(c) f : Z → {0, 1, 2}, f(x) = zbytek po dělení x : 3,
(d) f : Z → Z, f(x) = 3x,
(e) f : Z → N, f(x) = (x − 1)2
+ 1,
(f) f : N → Z, f(x) =
y pokud (y − 1)2
+ 1 = x
0 jinak
(g) f : Z × Z → P(Z), f((x, y)) = {x, y},
(h) f : P(Z) → N0, f(X) = počet prvků X,
(i) f : P(N) → N, f(X) = minX.
Upravte zadání předchozích příkladů tak, aby se odpověď změnila; např. změňte výchozí
množinu tak, aby zobrazení bylo prosté, cílovou množinu nebo předpis tak, aby bylo
surjektivní a pod.
6. Najděte a, b ∈ Z tak, aby zobrazení f : Z → Z definované předpisem f(x) = ax+b
2
bylo
injektivní nebo surjektivní. Závorky ⌊ ⌋ značí celou část.
7. Pro bijektivní zobrazení f, g : R → R, zadané vztahy f(x) = x − 2 a g(x) = 2x + 3,
najděte předpis pro f ◦ g, f−1
, g−1
, f ◦ g−1
a pod. Jak se řešení liší, pokud množinu R
nahradíme množinou Z.
5
8. Dokažte, že následující zobrazení jsou bijektivní.
(a) f : N × N → N, f(x, y) = 2x−1
(2y − 1),
(b) f :]a, b[→ R+
, f(x) = x−a
b−x
.
Dejte předpis inverzních zobrazení.
9. Dokažte, že následující zobrazení f, g jsou vzájemně inverzní zobrazení (a tudíž bijekce).
f : N → Z, f(x) = (−1)x
⌊x
2
⌋,
g : Z → N, g(y) = 2|y − 1
4
| + 1
2
10. Pro disjunktní množiny A a B dokažte, že zobrazení f : P(A ∪ B) → P(A) × P(B)
definované předpisem f(X) = (X ∩ A, X ∩ B) je bijekce. Najďete zobrazení inverzní.
11. Dokažte, že pro libovolnou množinu A je zobrazení f : P(A) → {0, 1}A
, které podmnožině
B ⊆ A přiřazuje charakteristickou funkci, bijektivní.
12. Přepište zobrazení z příkladu 10 po ztotožnění P(A) ∼= {0, 1}A
a zobecněte výsledek tak,
abyste dokázali CA∪B ∼= CA
× CB
pro libovolné množiny A, B, C, kde A ∩ B = ∅.
13. Nechť f : A → A je zobrazení takové, že existuje n ∈ N s vlastností fn
= idA. Dokažte,
že f je bijekce.
14. Pro zobrazení f : A → B a g : B → C zjistěte, zda platí následující ekvivalence. Až
zjistíte, že implikace obecně ←− neplatí, pozměňte levou stranu tak, aby platila.
(a) f a g jsou injektivní ←→ g ◦ f je injektivní,
(b) f a g jsou surjektivní ←→ g ◦ f je surjektivní.
15. Nechť A = ∅. Dokažte, že pro jakékoliv zobrazení f : A → B platí
(a) f je injektivní ←→ existuje zobrazení g : B → A tak, že g ◦ f = idA,
(b) f je surjektivní ←→ existuje zobrazení h : B → A tak, že f ◦ h = idB.
16. Nechť A je množina a f : A → A je zobrazení, které není identické. Dejte příklad zobrazení
g, h : A → A tak, aby platilo
(a) f ◦ g = g ◦ f,
(b) f ◦ h = h ◦ f.
17. Každé zobrazení f : A → B idukuje pro libovolné C zobrazení F : AC
→ BC
definované
vztahem F(φ) = f ◦ φ. Dokažte, že f není bijektivní nebo F je bijektivní.
6
5 Relace na množině, ekvivalence a rozklady množin
1. Na množině {0, 1} nalezněte všechny relace (resp. uveďte jejich počet), které jsou:
(a) reflexivní
(b) symetrické
(c) tranzitivní
(d) relace ekvivalence
(e) symetrické a tranzitivní
(f) symetrické a antisymetrické
Totéž v případě jednoprvkové a prázdné množiny.
2. Na množině {1, 2, 3} nalezněte všechny relace ekvivalence.
3. Buď A = {1, 2, 3}. Nalezněte:
(Relace i zobrazení zadávejte výčtem prvků z množiny A × A.)
(a) zobrazení f, g : A → A taková, že f ◦ g = g ◦ f;
(b) injektivní zobrazení f : A → A, které není reflexivní relací;
(c) reflexivní relaci R na množině A, která není zobrazením;
(d) zobrazení f : A → A, které je symetrickou relací a pro něž f ◦ f = f;
(e) dvojici relací R ⊆ S na množině A takových, že R = S, R je zobrazení a S je
tranzitivní relace.
4. Buď s : N → N zobrazení dané předpisem s(n) = n + 1, tj. s = {(n, n + 1) | n ∈ N}. Dále
definujme relaci R< na množině N takto R< = {(a, b) ∈ N × N | a < b}.
Nalezněte: (Relace i zobrazení zadávejte vhodným předpisem (tj. množinově), nikoli obrázkem.)
(a) symetrickou relaci R na množině N takovou, že R ⊆ R<;
(b) tranzitivní relaci R na množině N takovou, že s ⊆ R;
(c) relaci R na množině N takovou, že R< ⊆ R a zároveň R ◦ R = R;
(d) zobrazení f : N → N takové, že f ◦ s = s ◦ f;
(e) relaci R na množině N, která není zobrazení, ale R ◦ R zobrazení je.
5. Je dána relace ρ na množině N. Rozhodněte zda ρ je reflexivní, resp. symetrická, resp.
antisymetrická, resp. tranzitivní relace, je-li pro x, y ∈ N:
(a) xρy ⇐⇒ x · y je liché číslo
(b) xρy ⇐⇒ x, y jsou nesoudělná
(c) xρy ⇐⇒ y = x ∨ y = 2x ∨ y = 3x
(d) xρy ⇐⇒ |x − y| = 3 ∨ x = y
7
6. Je dána relace ρ na množině Z. Rozhodněte zda ρ je reflexivní, resp. symetrická, resp.
antisymetrická, resp. tranzitivní relace, je-li pro x, y ∈ Z:
(a) xρy ⇐⇒ x = y
(b) xρy ⇐⇒ x sudé, y liché
(c) xρy ⇐⇒ x2
= y
(d) xρy ⇐⇒ |x| < y
(e) xρy ⇐⇒ x · y ≤ 0
(f) xρy ⇐⇒ 3|(x + 2y)
(g) xρy ⇐⇒ |x| ≤ |y|
7. Je dána relace ρ na množině P(A), kde A je neprázdná konečná množina. Rozhodněte
zda ρ je reflexivní, resp. symetrická, resp. antisymetrická, resp. tranzitivní relace, je-li pro
X, Y ∈ P(A):
(a) XρY ⇐⇒ X ∪ Y = A
(b) XρY ⇐⇒ X = ∅ ∨ X = A
(c) XρY ⇐⇒ X ∩ Y = ∅
(d) XρY ⇐⇒ množiny X, Y mají stejný počet prvků
(Návod: uvědomte si, že v některých případech může vyšetřovaná vlastnost záviset na
počtu prvků množiny A.)
8. Na množině M = {1, 2, 3, . . ., 18, 19, 20} definujeme relaci ρ takto: xρy ⇐⇒ čísla x, y
mají stejný součet cifer. Dokažte, že ρ je relací ekvivalence na M a sestrojte rozklad M\ρ
(tj. rozklad množiny M přislušný ekvivalenci ρ).
9. Na množině M je definována relace ρ. Rozhodněte, zda ρ je relací ekvivalence na M, je-li
(a) M = Z; ρ = {(x, y) ∈ Z × Z | y = x nebo y = x + 1}
(b) M = R; ρ = {(x, y) ∈ R × R | x − y ∈ Z}
(c) M = R; ρ = {(x, y) ∈ R × R | |x − y| ≤ 1}
(d) M = P(N); ρ = {(A, B) ∈ P(N) × P(N) | (A − B) je konečná množina}
(e) M = P(N); ρ = {(A, B) ∈ P(N) × P(N) | (A ÷ B) je konečná množina} kde A ÷ B
je symetrický rozdíl, tj. A ÷ B = (A − B) ∪ (B − A)
10. Na množině Z je definována relace ρ. Dokažte, že ρ je ekvialencí na Z a popište rozklad
Z\ρ. Přitom pro x, y ∈ Z je:
(a) xρy ⇐⇒ ∃k ∈ Z : y = x + 4k
(b) xρy ⇐⇒ x2
≡ y2
(mod 7)
(c) xρy ⇐⇒ x2
+ 2x = y2
+ 2y
(d) xρy ⇐⇒ 2|(x2
− y2
)
8
11. Na množině Z − {0} je relace ρ definována vztahem xρy ⇔ x · y > 0. Dokažte, že ρ je
ekvivalencí na Z − {0} a popište rozklad (Z − {0})\ρ.
12. Na množině R×R je definována relace ρ. Dokažte, že ρ je ekvivalencí na R×R a načrtněte,
jak vypadá rozklad R × R\ρ (zde R × R chápeme jako množinu všech bodů v rovině).
Přitom pro (x, y), (u, v) ∈ R × R je:
(a) (x, y)ρ(u, v) ⇐⇒ x − u = 0
(b) (x, y)ρ(u, v) ⇐⇒ y − v = 2(x − u)
(c) (x, y)ρ(u, v) ⇐⇒ (x − u)(x + u) = (v − y)(v + y)
(d) (x, y)ρ(u, v) ⇐⇒ x2
+ y2
+ x + y = u2
+ v2
+ u + v
13. Nalezněte jádra následujících zobrazení:
(a) f : R → Z f(x) = ⌊x⌋
(b) f : R → R, f(x) = |x|
(c) f : Z → Z, f(x) je zbytek po dělení čísla x číslem n
(d) f : Z → Z, f(x) = ⌊x
n
⌋
Popište příslušný rozklad.
14. Nechť R, S jsou relace na množině A. Dokažte, že pokud R, S jsou symetrické relace, pak
R ∩ S je také symetrická relace.
15. Nechť R, S jsou relace na množině A. Rozhodněte, zda platí:
(a) R, S reflexivní =⇒ R ◦ S reflexivní;
(b) R, S symetrické =⇒ R ◦ S symetrická;
(c) R, S tranzitivní =⇒ R ◦ S tranzitivní;
16. Dokažte, že pro libovolné relace R, R1, R2 ⊆ A × B, S ⊆ B × C a T ⊆ C × D platí:
(a) (R−1
)−1
= R
(b) T ◦ (S ◦ R) = (T ◦ S) ◦ R
(c) (S ◦ R)−1
= R−1
◦ S−1
(d) S ◦ (R1 ∪ R2) = (S ◦ R1) ∪ (S ◦ R2)
(e) S ◦ (R1 ∩ R2) ⊆ (S ◦ R1) ∩ (S ◦ R2)
(f) (R1 ∪ R2)−1
= R−1
1 ∪ R−1
2
(g) (R1 ∩ R2)−1
= R−1
1 ∩ R−1
2
(h) S ◦ R1 − S ◦ R2 ⊆ S ◦ (R1 − R2)
Dokažte, že v (e) a (h) obecně neplatí rovnost. Zformulujte a dokažte vztahy (d) — (g)
pro libovolná sjednocení resp. průniky.
9
17. Udejte příklad relace na množině N, která je:
(a) symetrická, tranzitivní, ale není reflexivní
(b) symetrická a současně antisymetrická
(c) není symetrická ani antisymetrická
(d) symetrická a není antisymetrická
(e) antisymetrická a není symetrická
(f) reflexivní, tranzitivní, ale není symetrická ani antisymetrická
(g) tranzitivní, reflexivní a symetrická, ale není ekvivalencí
Hledejte co možná nejmenší (vzhledem k inkluzi) relace.
18. Nechť A a B jsou množiny. Charakterizujte zobrazení f : A → B, pro která platí:
(a) Jf = idA
(b) f(A) = B
19. Je sjednocení (resp. průnik) reflexivních (resp. symetrických, resp. tranzitivních) relací
reflexivní (resp. symetrická, resp. tranzitivní) relace? (Používejte i „množinové definice
daných vlastností; např. relace S je tranzitivní, pokud S ◦ S ⊆ S.)
20. Nechť α ⊆ A × A je libovolná relace na množině A. Rozhodněte, zda existuje nejmenší
(vzhledem k inkluzi) relace mezi všemi relacemi β ⊆ A × A, α ⊆ β které jsou:
(a) reflexivní
(b) symetrické
(c) tranzitivní
(d) reflexivní a symetrické
(e) reflexivní a tranzitivní
(f) symetrické a tranzitivní
(g) relace ekvivalence
(h) antisymetrická
Podobně rozhodněte, zda existuje největší (vzhledem k inkluzi) relace mezi všemi relacemi
s danou vlastností, které jsou obsženy v relaci α.
21. Relaci R ⊆ A × A nazývame dichotomickou, pokud R ∪ R−1
= A × A. Rozhodněte, zda
je každá dichotomická relace reflexivní.
Nechť množina A má n prvků. Kolik je na množině A relací, které jsou:
(a) dichotomické
(b) symetrické a dichotomické
10
Rozhodněte (dokažte nebo najděte protipříklad), zda platí následující tvrzení:
Jsou-li R1, R2, . . . , Rn reflexivní relace (n ≥ 1), z nichž alespoň jedna je dichotomická,
pak je relace Rn ◦ Rn−1 ◦ · · · ◦ R1 dichotomická. Platí opačná implikace?
22. Relaci R na množině A nazýváme 3-tranzitivní, jestliže
∀a, b, c, d ∈ A : (((a, b) ∈ R ∧ (b, c) ∈ R ∧ (c, d) ∈ R) ⇒ (a, d) ∈ R).
Rozhodněte, zda platí nasledující tvrzení (tzn. tvrzení dokažte nebo nalezněte protipří-
klad):
(a) Každá 3-tranzitivní relace je tranzitivní.
(b) Každá tranzitivní relace je 3-tranzitivní.
Pokuste se diskutovat obecně vztah n-tranzitivity a m-tranzitivity.
6 Uspořádané množiny
1. Rozhodněte, zda jsou následující relace uspořádání, resp. lineární uspořádání na N. V
případě kladné odpovědi naznačte hasseovský diagram uspořádané množiny (N, ).
(a) x y ⇐⇒ x = y
(b) x y ⇐⇒ x ≤ y
(c) x y ⇐⇒ x < y
(d) x y ⇐⇒ y = 4 ∨ y = x
(e) x y ⇐⇒ počet cifer čísla x je menší nebo roven počtu cifer čísla y
(f) x y ⇐⇒ x ≡ y(mod5)
(g) x y ⇐⇒ (x = y) ∨ (2 | x ∧ 2 | y) ∨ (2 | x + y ∧ x < y)
2. Nechť A je libovolná množina. Dokažte, že (P(A), ⊆) je uspořádáná množina. Sestrojte
Hasseovy diagramy v případě:
(a) A = ∅
(b) A = {a}
(c) A = {a, b}
(d) A = {a, b, c}.
3. Popište maximální a minimální prvky, resp. největší a nejmenší prvek množiny M s uspořádáním
ρ.
(a) M = {a, b, c}, ρ = {(a, a), (b, b), (c, c)}
(b) M = {a, b, c}, ρ = {(a, a), (b, b), (c, c), (a, b), (b, c), (a, c)}
(c) M = {a, b, c, d}, ρ = {(a, a), (b, b), (c, c), (d, d), (a, b), (a, c)}
11
(d) M = P({a, b}), ρ = ⊆
4. Popište maximální a minimální prvky, respektive největší a nejmenší prvek množiny, která
má tento hasseovský diagram:
5. Nakreslete hasseovské diagramy všech uspořádání na
(a) dvojprvkové množině
(b) trojprvkové množině.
6. Na množině M = {1, 2, 3, 4, 5, 6, 7} definujme relaci R tak, že
(x, y) ∈ R ⇐⇒ (∃n ∈ N)(y = n · x).
Dokažte, že R je uspořádání a sestrojte hasseovský diagram množiny (M, R). Uvažujte
relaci R definovanou tímto vztahem na množině N a schematicky naznačte hasseovský
diagram (N, R). Popište maximální, minimální, největší a nejmenší prvky těchto množin.
7. V předchozích příkladech diskutujte existenci suprem a infim.
8. Na R definujme relaci R takto:
(x, y) ∈ R ⇐⇒ (∃c ∈ R)(c ≥ 1 ∧ c · x = y).
Dokažte, že R je uspořádání na R a naznačte hasseovský diagram.
9. Nakreslete hasseovský diagram
(a) čtyřprvkové uspořádáné množiny, která má právě dva maximální prvky a nemá
nejmenší prvek
(b) čtyřprvkové uspořádáné množiny, v níž každý prvek je současně maximální i mini-
mální
(c) konečné uspořádané množiny, která má právě tři minimální prvky a žádný maximální
prvek
10. Uveďte příklad uspořádané množiny (M, ), která
(a) má aspoň dva maximální prvky a aspoň dva minimální prvky
12
(b) má právě jeden maximální prvek a nemá největší prvek
(c) má právě jeden nejmenší prvek a právě tři minimální
(d) obsahuje právě dva nesrovnatelné prvky a nemá přitom žádný maximální prvek ani
minimální prvek
(e) neobsahuje žádné různé srovnatelné prvky
11. Nechť I je neprázdná množina a R, R1, R2, Ri, i ∈ I jsou uspořádání množiny M. Dokažte
nebo vyvraťte následující tvrzení.
(a) R−1
je uspořádání
(b) i∈I Ri je uspořádání
(c) i∈I Ri je uspořádání
(d) R1 ◦ R2 je uspořádání
12. Nechť (A, ≤) a (B, ⊑) jsou uspořádané množiny. Definujme relaci na A × B takto:
(a1, b1) (a2, b2) ⇐⇒ a1 ≤ a2 ∧ b1 ⊑ b2. Dokažte, že je uspořádání množiny A × B.
(Hovoříme o součinu uspořádaných mnžin.) Nakreslete hasseovský diagram uspořádání
množiny P({a, b}) × {1, 2}, kde P({a, b} je uspořádáno inkluzí a {1, 2} dle velikosti.
Rozhodněte, zda platí, že součin řetězců je řetězec. Zobecněte definici uspořádání na
součin konečně mnoha uspořádaných množin a naznačte hasseovský diagram.
13. Nechť (Ai, i), i ∈ I je systém uspořádaných množin, které splňují Aj ∩ Ak = ∅ pro
j = k; j, k ∈ I. Definujme na i∈I Ai relaci takto:
x y ⇐⇒ (∃i ∈ I)(x i y).
Dokažte, že ( i∈I Ai, ) je uspořádaná množina. Nakreslete hasseovský diagram pro
(P({a, b}), ⊆)) a (N, ≤). Jak by vypadal hasseovský diagram v obecném případě?
14. Nechť (A, ) je uspořádaná množina. Definujme relaci ≤ na A × A takto:
(a, b) ≤ (c, d) ⇐⇒ a ≺ c ∨ (a = c ∧ b d).
Dokažte, že ≤ je uspořádání. Rozhodněte, kdy je lineární. Nakreslete hasseovský diagram
pro množinu (P({a, b}), ⊆). Zobecněte tuto definici na konečný součin libovolných
uspořádaných množin. (Hovoříme o lexikografickém součinu.)
15. Rozhodněte, která z následujících zobrazení jsou izotonní, respektive izomorfismy.
(a) N −→ N, x → x + 1
(b) Z −→ Z, x → x + 1
(c) N −→ N, x → x2
(d) Z −→ Z, x → x2
(e) Z −→ Z, x → |x|
(f) N −→ N, x → 1
13
(g) P({a, b}) −→ P({a, b, c}), X → X
(h) P({a, b}) −→ P({a, b, c}), X → X ∪ {c}
16. Najděte všechna izotonní zobrazení mezi uspořádanými množinami s diagramy:
a
17. Najděte všechny automorfismy (izomorfismy do sebe) uspořádané množiny s tímto dia-
gramem.
a c d e
b f
18. Udejte příklad
(a) uspořádané množiny a izotonního bijektivního zobrazení množiny na sebe, jehož
inverze není izotonní.
(b) automorfismu pětiprvkové množiny na sebe, který má právě tři pevné body
19. Najděte všechna izotonní zobrazení (Q, ≤) do ({0, 1}, ≤). Řekněte, čemu odpovídají.
20. Najděte všechny automorfismy ω, ω × ω, Z, Z × Z s obvyklým uspořádáním.
7 Úplné svazy
21. Rozhodněte, které z těchto uspořádaných množin jsou svazy.
14
22. Určete všechny pětiprvkové svazy.
23. Rozhodněte, zda následující uspořádané množiny (M, R) jsou svazy, respektive úplné
svazy.
(a) M = P({A}), A je libovolná množina, R je ⊆
(b) M je množina všech otevřených intervalů na reálné přímce společně s prázdnou
množinou, R je ⊆
(c) A nekonečná, M je množina všech konečných podmnožin A, R je ⊆
(d) M = P({A}) − {∅}, A je libovolná množina, R je ⊆
(e) M = N, R je |
(f) M = ω, R je |
(g) M = N, R je ≤
(h) A nekonečná, M je množina všech podmnožin A s konečným doplňkem, R je ⊆
(i) M je množina všech ekvivalencí na A, A je libovolná množina R je ⊆
24. Dokažte, že jsou-li (A, ≤) a (B, ⊑) svazy, pak součin uspořádaných množin A × B (definovaný
v příkladu 12) je svaz.
25. Nechť A je svaz. Dokažte, že pro libovolné a, b, c ∈ A platí:
(a) (a ∧ b) ∨ (b ∧ c) ∨ (c ∧ a) ≤ (a ∨ b) ∧ (b ∨ c) ∧ (c ∨ a)
(b) a ≤ c ⇒ a ∨ (b ∧ c) ≤ (a ∨ b) ∧ c
15
8 Základní algebraické struktury
1. Rozhodněte, zda daný grupoid je pologrupa, zda obsahuje neutrální prvek, nulový prvek,
zda je to grupa a zda je operace komutativní.
(a) Celá čísla s operací sčítání.
(b) Reálná čísla s operací násobení.
(c) Celá čísla s operací odečítání.
(d) Přirozená čísla s operací největší společný dělitel.
2. Pro množinu X značíme P(X) množinu všech podmnožin množiny X. Pro následující
operace určete, zda grupoid P(X) je pologrupou, zda je operace komutativní a nalezněte
neutrální prvek.
(a) Průnik.
(b) Sjednocení.
(c) Množinový rozdíl. (Y − Z = {x ∈ Y | x ∈ Z})
(d) Symetricky rozdíl. (Y ÷ Z = (Y − Z) ∪ (Z − Y ))
3. Určete, zda operace na tříprvkové množině {a, b, c} daná tabulkou je komutativní, asociativní
a zda má neutrální prvek.
(a)
◦ a b c
a b a a
b a b a
c a a a
(b)
◦ a b c
a b a a
b a b c
c a c a
(c)
◦ a b c
a a a a
b b b b
c c c c
4. Uvažme na množině P(X ×X) všech relací na množině X operaci ◦ definovanou vztahem
ρ ◦ π = {(x, y) ∈ X × X | ∃z ∈ X : (x, z) ∈ π, (z, y) ∈ ρ}.
Ukažte, že ◦ je asociativní. Určete neutrální a nulový prvek. Rozhodněte, zda (S, ◦),
kde S = {ρ ∈ P(X × X) | ρ symetrická}, je grupoid. Rozhodněte, zda (T, ◦), kde
T = {ρ ∈ P(X × X) | ρ tranzitivní}, je grupoid.
5. Pro množinu X označme T(X) množinu všech transformací, tj. T(X) = {f : X → X},
a PT(X) množinu všech parciálních transformací, tj.
PT(X) = {ρ ∈ X × X | ∀x, y, z ∈ X : xρy, xρz =⇒ y = z}.
Ukažte, že (T(X), ◦) resp. (PT(X), ◦), kde ◦ je operace skládání zobrazení, resp. skládání
relací, jsou monoidy. Pro danou množinu transformací (resp. parciálních transformací)
určete, zda společně s operací skládání zobrazení tvoří grupoid, pologrupu, či grupu.
(Pozor: odpovědi se mohou lišit v případech kdy X je jednoprvková, resp. konečná, resp.
nekonečná.)
(a) Všechna injektivní zobrazení.
16
(b) Všechna surjektivní zobrazení.
(c) Všechna bijektivní zobrazení.
6. Uvažujme množinu O = {(a, b) | a, b ∈ R, a < b} ∪ {∅} všech omezených otevřených
intervalů reálných čísel. Ukažte, že průnik ∩ je operací na této množině. Rozhodněte, zda
je operace ∩ asociativní a zda existuje neutrální a nulový prvek. Je (O, ∩) grupa?
7. Rozhodněte, zda daný grupoid (G, ◦) je grupa.
(a) G je množina všech nenulových racionálních čísel a operace ◦ je dána předpisem
x ◦ y = |x · y|.
(b) G je interval 0, 1) a operace ◦ je dána předpisem x ◦ y = x + y − [x + y], kde [z]
značí celou část z čísla z, tj. největší celé číslo menší nebo rovno z.
(c) G je množina všech celých čísel a operace ◦ je dána předpisem x ◦ y = x + (−1)x
y.
(d) G je množina všech uspořádaných dvojic reálných čísel, přičemž první z nich není
0, tj. G = {(x, y) | x, y ∈ R, x = 0} a operace ◦ je dána předpisem (x, y) ◦ (u, v) =
(xu, xv + y).
(e) G je množina všech komplexních čísel, jejichž reálná i imaginární část je celočíselná
a operace ◦ je sčítání komplexních čísel.
8. (a) Dokažte, že v libovolné grupě platí tzv. zákony o krácení
ab = ac =⇒ b = c, ba = ca =⇒ b = c.
(b) Udejte příklad (nekonečné) pologrupy, která není grupou, ale platí v ní zákony o
krácení.
(c) Udejte příklad tříprvkového grupoidu, který není grupou, ale platí v něm zákony o
krácení. Ukažte, že grupoid není pologrupou.
(d) Nalezněte všechny tříprvkové grupy.
(e) Nalezněte všechny čtyřprvkové grupy.
9. Pro dané množiny matic typu 2 krát 2 nad reálnými čísly rozhodněte, zda je sčítání,
resp. násobení, matic operací na této množině. Pokud se jedná o operaci, zjistěte, zda je
operace asociativní či komutativní, zda obsahuje neutrální prvek, a zda se jedná o grupu.
(a) Množina všech matic nad celými čísly.
(b) Množina všech matic nad racionálními čísly.
(c) Množina všech regulárních matic nad racionálními čísly.
(d) Množina všech matic s nulou v levém dolním rohu a s jedničkami na hlavní diagonále.
(e) Množina všech regulárních matic nad celými čísly.
Rozhodněte, zda je daná množina s operacemi sčítání a násobení matic okruhem, oborem
integrity, či tělesem.
17
10. Uvažme následující množiny racionálních čísel:
A =
m
p
| m, p ∈ Z, p = 0, 3 ∤ p, , B =
q
3n
| n ∈ N, q ∈ Z .
Rozhodněte, zda (A, +, ·) (resp. (B, +, ·)), kde operace + a · jsou obvyklé sčítání a násobení
racionálních čísel, je okruh, případně obor integrity. Jde-li o okruh, určete ke kterým
prvkům existuje inverze.
11. Určete, zda je okruh (Z2, +, ·) × (Z3, +, ·) oborem integrity. Je izomorfní s okruhem
(Z6, +, ·)?
12. Dokažte, že následující zobrazení jsou homomorfismy. Určete jejich jádra a obrazy. (Zde
a, b ∈ R, n ∈ N.)
(a) α : (R, +) → (R+
, ·), α(a) = 3a
(b) β : (Z, +) → (C∗
, ·), β(n) = in
(c) γ : (C∗
, ·) → (R+
, ·), γ(a + bi) =
√
a2 + b2
13. U každého z následujících předpisů (kde a, b ∈ Z, p, q ∈ Z − {0}) rozhodněte, zda zadává
zobrazení. Pokud ano, rozhodněte, zda se jedná o homomorfismus či dokonce izomorfismus
grup.
(a) α : (Z4, +) × (Z3, +) → (Z12, +), α(([a]4, [b]3)) = [6a + 4b]12
(b) β : (Z4, +) × (Z3, +) → (Z12, +), β(([a]4, [b]3)) = [a − b]12
(c) γ : (Q∗
, ·) → (Q∗
, ·), γ(p/q) = q/p
(d) δ : (Z15, +) → (Z5, +) × (Z3, +), δ([a]15) = ([a]5, [a]3)
(e) ǫ : (Z2, +) × (Z5, +) → (Z10, +), ǫ(([a]2, [b]5)) = [a + b]10
(f) ζ : (Z4, +) → (C∗
, ·), ζ([a]4) = ia
(g) η : (Z5, +) → (C∗
, ·), η([a]5) = ia
(h) θ : (Z, +) → (Z3, +), θ(a) = [|a|]3
(i) ι : (Z, +) → (Z2, +), ι(a) = [|a|]2
14. Určete jádra a obrazy homomorfismů z předchozího příkladu.
15. Uvažme grupu (G, ·) matic typu 3 krát 3 nad Z, které jsou v horním trojúhelníkovém
tvaru s jedničkami na hlavní diagonále, tj.
G =





1 a b
0 1 c
0 0 1

 | a, b, c ∈ Z



,
kde · je násobení matic. Definujme nyní zobrazení f : (G, ·) → (Z, +), které matici


1 a b
0 1 c
0 0 1


přiřadí číslo a − c. Dokažte, že zobrazení f je homomorfismus grup.
18
16. Uvažme zobrazení f : C → R definované takto: f(a+bi) = a+b pro a, b ∈ R. Rozhodněte,
zda je f homomorfismus okruhu (C, +, ·) do okruhu (R, +, ·).
17. Buď Q(
√
3) = {a + b
√
3 | a, b ∈ Q}. Ukažte, že (Q(
√
3), +, ·) je těleso. Dokažte, že
libovolný okruhový homomorfismus α : Q(
√
3) → C je identický na množině racionálních
čísel, tj. ∀r ∈ Q : α(r) = r. Popište všechny okruhové homomorfismy α : Q(
√
3) → C.
Které z nich jsou izomorfismy?
9 Kombinatorika
1. Buď n přirozené číslo. Čtverec o straně n je rozdělen rovnoběžkami se stranami na n2
jednotkových čtverců. Kolik je v daném obrazci čtverců.
2. Kolika způsoby lze z úplného souboru domina (28 kostek) vybrat dvě tak, abychom je
mohli přiložit k sobě (tedy aby se nějaký počet ok vyskytoval zároveň na obou kostkách)?
3. Na schůzi má promluvit pět řečníků A, B, C, D, E (každý právě jednou).
(a) Určete počet všech možných pořadí jejich vystoupení.
(b) Určete počet všech možných pořadí jejich vystoupení, má-li řečník B promluvit
bezprostředně po A.
(c) Určete počet všech možných pořadí jejich vystoupení, má-li řečník B promluvit až
poté, co promluvil řečník A.
4. Kolik čtyřciferných přirozených čísel s navzájem různými ciframi lze sestavit z cifer
(a) 1, 2, 3, 4
(b) 1, 2, 3, 4, 5, 6
(c) 0, 1, 2, 3, 4, 5
Kolik z nich je sudých? Kolik z nich je dělitelných čtyřmi?
5. V rovině je dáno 6 různých bodů, z nichž žádné tři neleží v jedné přímce. Kolik přímek
tyto body určují.
6. Ze skupiny 7 chlapců a 4 dívek je třeba vybrat šestičlenné volejbalové družstvo, v němž
musí být aspoň dvě dívky. Kolika způsoby to lze učinit?
7. Kolik značek Morseovy abecedy je možné vytvořit, sestavujeme-li tečky a čárky do skupin
o jednom až čtyřech prvcích?
8. Pro osm studentů je připraveno v koleji ubytování ve 3 pokojích, z nichž dva jsou třílůžkové,
jeden dvoulůžkový. Kolik je způsobů rozdělení studentů do jednotlivých pokojů?
9. Dokažte binomickou větu: pro libovolné n ∈ N, a, b ∈ R platí
(a + b)n
=
n
i=0
n
i
ai
bn−i
.
19
10. Mezi 6 dětí rozdělujeme 15 (stejných) tenisových míčků. Určete počet všech možných
rozdělení. Určete počet všech rozdělení, při kterých každé dítě dostane aspoň jeden míček.
11. Pro libovolné pevné k, n ∈ N určete počet všech řešení rovnice
x1 + x2 + · · · + xk = n
v množině celých nezáporných čísel (resp. v množině přirozených čísel).
12. Pro libovolné pevné k, n ∈ N určete počet všech řešení nerovnice
x1 + x2 + · · · + xk ≤ n
v množině celých nezáporných čísel (resp. v množině přirozených čísel).
13. Pro daná čísla n, k ∈ N určete počet k-členných posloupností celých čísel (a1, a2 . . . , ak)
splňujících podmínku 1 ≤ a1 ≤ a2 ≤ · · · ≤ ak ≤ n.
14. Určete počet všech kladných dělitelů přirozeného čísla n.
15. V oddělení výzkumného ústavu pracuje několik osob, z nichž každá zná aspoň jeden z
těchto tří světových jazyků — angličtinu, němčinu nebo francouzštinu. Šest osob ovládá
angličtinu, šest němčinu a sedm francouzštinu, 4 osoby hovoří anglicky i německy, 3 osoby
německy i francouzsky, 2 osoby francouzsky i anglicky, jeden pracovník ovládá všechny
tři uvedené jazyky.
(a) Kolik osob pracuje v oddělení?
(b) Kolik z nich hovoří pouze anglicky?
(c) Kolik z nich hovoří pouze francouzsky?
16. Kolika způsoby můžeme posadit do řady 3 Angličany, 3 Francouze a 3 Němce tak, aby
žádní tři krajané neseděli vedle sebe.
17. Buďte n a k přirozená čísla taková, že k ≤ n. Nechť dále A = {1, 2, . . ., n}, B =
{1, 2, . . ., k}. Určete počet všech:
(a) k prvkových podmnožin množiny A,
(b) podmnožin množiny A,
(c) zobrazení množiny A do množiny B,
(d) bijekcí A na sebe,
(e) injektivních zobrazení množiny B do množiny A,
(f) surjektivních zobrazení množiny A na množinu B,
(g) zobrazení podmnožiny množiny A do množiny B,
(h) izotonních zobrazení uspořádané množiny (A, ≤) do uspořádané množiny (B, ≤),
kde ≤ je uspořádání dle velikosti,
(i) relací na množině A,
(j) reflexivních relací na množině A,
(k) symetrických relací na množině A,
(l) antisymetrických relací na množině A,
20