Zkoušková písemka z předmětu ,,Úvod do informatiky", 27.1. 2005, varianta A.
Příklady 1­8 (160 bodů celkem) Jméno:
Souřadnice:
Řešení každého příkladu napište (pouze) na ten papír, na kterém je jeho zadání. Každý papír musí být
podepsaný (!!!).
Každý musí vypracovat své řešení zcela samostatně. Pište krátce, jasně a čitelně. Špatně čitelná
řešení nebudou opravena a budou ohodnocena 0 body. Počty bodů za jednotlivé příklady a výsledek
zkoušky Vám budou zaslány elektronickou poštou.
Příklad 1: Dokažte, že jestliže f : A  B a g : B  A jsou funkce takové, že (g  f)(a) = a pro
každé a  A, pak funkce f je injektivní.
Příklad 2: Necht' M = {a, b, c, d} a necht' N = {X, Y, Z} je (nějaký) rozklad na M. Nakreslete
Hasseovský diagram uspořádané množiny (N, ).
Příklad 3: Uvažme relaci R = {(i, 3+i) | i  N0} na množině N0 nezáporných celých čísel. Zapište
(jako množinu) relaci S, která je reflexivním, symetrickým a tranzitivním uzávěrem relace R.
Příklad 4: Uvažme uspořádané množiny (A, A), (B, B), kde A = {a, b, c, d}, B = {x, y},
A = {(a, a), (b, b), (c, c), (d, d), (a, b), (a, c), (a, d), (b, d), (c, d)}, B = {(x, x), (y, y), (x, y)}.
Nakreslete Hasseovský diagram množiny (A × B, ), kde je lexikografické uspořádání.
Zkoušková písemka z předmětu ,,Úvod do informatiky", 27.1. 2005, varianta A.
Příklady 1­8 (160 bodů celkem) Jméno:
Souřadnice:
Příklad 5: Napište formuli  výrokové logiky pro kterou platí, že formule    je tautologií pro
každou formuli  výrokové logiky.
Příklad 6: Zapište (jako relace) všechna předuspořádání na množině {a, b}.
Příklad 7: Uvažme uspořádanou množinu (Q, ), kde Q je množina racionálních čísel a  ,,obvyklé"
uspořádání na Q (tj. uspořádání ,,podle velikosti"). Dokažte, že pro libovolné x  Q neexistuje žádné
y  Q takové, že y pokrývá x.
Příklad 8: Zapište (jako relace) všechny parciální funkce z množiny  do množiny .
Zkoušková písemka z předmětu ,,Úvod do informatiky", 27.1. 2005, varianta A.
Příklad 2 (150 bodů) Jméno:
Souřadnice:
Zadání: Uvažme deklaraci obsahující rovnice
f(x) = if x then f(x - 1) + h(x - 1) else 0
h(x) = if x then h(x - 1) + f(x) else 0
Dokažte, že pro každé n  N0 platí h(n)  0.