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 iI Bi = iI(A Bi) (b) A iI Bi = iI(A Bi) (c) A - iI Bi = iI(A - Bi) (d) iI jJ (Bi ÷ Cj) = iI jJ (Bi Cj) - iI jJ (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) iI(A ÷ Bi) A ÷ iI Bi (b) A ÷ iI Bi iI(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) pI Ap = N - {1} (b) pI Ap = (c) je-li J = libovolná konečná množina prvočísel, pak pJ 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 × iI Ai = iI(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) iI P(Ai) = P( iI Ai) (d) iI P(Ai) = P( iI 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 CAB = 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) xy x y je liché číslo (b) xy x, y jsou nesoudělná (c) xy y = x y = 2x y = 3x (d) xy |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) xy x = y (b) xy x sudé, y liché (c) xy x2 = y (d) xy |x| < y (e) xy x y 0 (f) xy 3|(x + 2y) (g) xy |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) XY X Y = A (b) XY X = X = A (c) XY X Y = (d) XY 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: xy čí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) xy k Z : y = x + 4k (b) xy x2 y2 (mod 7) (c) xy x2 + 2x = y2 + 2y (d) xy 2|(x2 - y2 ) 8 11. Na množině Z - {0} je relace definována vztahem xy x y > 0. Dokažte, že je ekvialencí 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) iI Ri je uspořádání (c) iI 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 iI Ai relaci takto: x y (i I)(x i y). Dokažte, že ( iI 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ý dia- gram 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 (defi- novaný 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í, asoci- ativní 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 : xy, xz = 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áso- bení 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, 20 (j) reflexivních relací na množině A, (k) symetrických relací na množině A, (l) antisymetrických relací na množině A, Výsledky: 1) n i=1 i2 = n(n+1)(2n+1) 6 ; 2) 147; 3) 120, 24, 60; 4) 24, 360, 300; 12, 180, 156; 6, 96; 5) 15; 6) 371; 7) 30; 8) 560; 10) 20 5 , 14 5 ; 11) n+k-1 k-1 , pro k n: n-1 k-1 , jinak 0; 12) n+k k , pro k n: n k , jinak 0; 13) n+k-1 k ; 14) Pokud n = p1 1 p2 2 pk k je jednoznačný rozklad na prvočinitele (tj. p1, . . . , pk jsou různá prvočísla a 1, . . . , k N), pak počet dělitelů je (1 + 1) (2 + 1) (k + 1); 15) 11, 1, 3; 16) 9! - 3 1 3!7! + 3 2 (3!)2 5! - (3!)4 = 283824 21