PLIN004 cvičení, podzim 2010
Př. 1
Mějme definována přirozená čísla a základní operace na nich. Definujte
dělitelnost.
Př. 2
Na základě definice dělitelnosti definujte sudé a liché číslo. Definujte je
i bez využití dělitelnosti.
Př. 3
Dokažte, že součet dvou, tří, čtyř sudých čísel je sudé číslo. Využijte přímý
důkaz i důkaz sporem.
Př. 4
Dokažte, že součet dvou lichých čísel je sudé číslo. Dokažte, že součet tří
lichých čísel je liché číslo. Využijte přímý důkaz i důkaz sporem.
Př. 5
Dokažte, že pro libovolná přirozená čísla a, b platí:
pokud 2 * a * a = b * b, pak b je sudé.
Př. 6
Vyjádřete výroky (𝐴 ∧ 𝐵), (𝐴 ∨ 𝐵) pouze pomocí negace a implikace.
Př. 7
Vyjádřete výrok (𝐴 ⇒ 𝐵) pouze pomocí negace a disjunkce.
Př. 8
Mějme výroky:
∙ A: x je sudé.
∙ B: y je sudé.
∙ C: x + y je sudé
Přečtěte následující výroky:
∙ 𝐴 ⇒ 𝐶
1
PLIN004 cvičení, podzim 2010
∙ (𝐴 ∨ 𝐵) ⇒ 𝐶
∙ (𝐴 ∧ ¬𝐴)
∙ (𝐴 ∧ ¬𝐴) ⇒ 𝐶
∙ (¬𝐴 ∧ ¬𝐵) ⇒ 𝐶
∙ (¬𝐴 ∧ ¬𝐵) ⇒ ¬𝐶
Které z nich jsou pravdivé?
Př. 9
Přepište v jazyce predikátové logiky:
∙ Všechna prvočísla jsou lichá.
∙ Všechna prvočísla menší než 5 jsou sudá.
∙ Všechna prvočísla větší než 5 jsou lichá.
∙ Existuje sudé prvočíslo.
Můžete používat predikát Prime(x) a aritmetiku nad celými čísly. Které
z výroků výše jsou pravdivé?
Př. 10
Přepište v jazyce predikátové logiky a dokažte:
∙ žádné sudé číslo není zároveň liché
∙ (2 * 𝑥 * 𝑥 = 𝑦 * 𝑦) ⇒ y je sudé
∙ žádné prvočíslo větší než 2 není sudé
Můžete používat predikát Prime(x), aritmetiku nad celými čísly a operátor
dělitelnosti (|).
Př. 11
Dokažte indukcí pro všechna přirozená 𝑛 ≥ 1:
∙ 𝑛 + 1 ≤ 2 * 𝑛
∙ 2 * 𝑛 ≤ 2 𝑛
2
PLIN004 cvičení, podzim 2010
∙ 1 + 2 + ... + 𝑛 = 𝑛/2 * (1 + 𝑛)
Př. 12
Induktivně definujte:
∙ přirozená čísla pomocí konstanty 1 a operace +
∙ celočíselné výrazy s operací +
∙ celočíselné výrazy s operací + a *
∙ nekonečnou posloupnost 7, 11, 15, 19, 23, ...
∙ nekonečnou posloupnost 2, 5, 11, 23, 47, ...
Př. 13
Dokažte strukturální indukcí, že každý celočíselný výraz podle definice
výše má sudý počet závorek.
Př. 14
Jsou následující výroky pravdivé?
∙ {∅} ∈ {∅}
∙ {∅} ⊆ {∅}
∙ {∅} ∈ {{∅}}
∙ {∅} ⊆ {{∅}}
∙ {4} ∈ {𝑥 ∈ 𝑁 | 𝑥 > 3}
∙ 4 ∈ {𝑥 ∈ 𝑁 | 𝑥 > 3}
∙ {4} ⊆ {𝑥 ∈ 𝑁 | 𝑥 > 3}
∙ 4 ⊆ {𝑥 ∈ 𝑁 | 𝑥 > 3}
∙ {4} ∈ {{𝑥} | 𝑥 ∈ 𝑁 ∧ 𝑥 > 3}
Př. 15
Zapište 𝒫(𝐴) pro množiny:
3
PLIN004 cvičení, podzim 2010
∙ 𝐴 = {1, 2, 3}
∙ 𝐴 = {∅, {∅}}
Př. 16
Zapište:
∙ množinu všech sudých čísel
∙ množinu všech prvočísel
Můžete používat množinu 𝑁, aritmetiku nad ní a operátor dělitelnosti.
Př. 17
Definujte:
∙ množinový rozdíl
∙ symetrický množinový rozdíl
Př. 18
Dokažte:
∙ 𝑎 ∈ 𝐴 ∩ 𝐵 ⇒ 𝑎 ∈ 𝐴
∙ 𝑎 ∈ 𝐴 ∩ 𝐵 ⇒ 𝑎 ∈ 𝐴 ∪ 𝐵
∙ 𝑎 ∈ 𝐴 ∧ 𝐴 ⊆ 𝐵 ⇒ 𝑎 ∈ 𝐵
Př. 19
Přepište v jazyce predikátové logiky Peanovy axiomy
∙ existuje nula
∙ každé číslo 𝑥 má následníka 𝑆(𝑥)
∙ nula není následníkem žádného čísla
∙ různá čísla mají různé následníky: 𝑎 ̸= 𝑏 ⇒ 𝑆(𝑎) ̸= 𝑆(𝑏)
4
PLIN004 cvičení, podzim 2010
Př. 20
Mějme definováno sčítání a násobení následujícími předpisy:
∙ 𝑎 + 0 = 𝑎
∙ 𝑎 + 𝑆(𝑏) = 𝑆(𝑎 + 𝑏)
∙ 𝑎 * 0 = 0
∙ 𝑎 * 𝑆(𝑏) = (𝑎 * 𝑏) + 𝑎
Vypočtěte podle definic:
∙ 1 + 1
∙ 2 + 2
∙ 2 * 1
∙ 1 * 2
( 1 = S(0), 2 = S(1) )
Př. 21
Definujme induktivně slova nad množinou {𝑎, 𝑏, 𝑐}:
∙ 𝑎, 𝑏, 𝑐 jsou slova
∙ pokud 𝑥 je slovo, pak 𝑎𝑥, 𝑏𝑥, 𝑐𝑥 jsou slova
Definujme sčítání řetězců následovně: Pro slova 𝑥 a 𝑦
∙ 𝑎 + 𝑥 = 𝑎𝑥
∙ 𝑏 + 𝑥 = 𝑏𝑥
∙ 𝑐 + 𝑥 = 𝑐𝑥
∙ 𝑦𝑎 + 𝑥 = 𝑦 + 𝑎𝑥
∙ 𝑦𝑏 + 𝑥 = 𝑦 + 𝑏𝑥
∙ 𝑦𝑐 + 𝑥 = 𝑦 + 𝑐𝑥
Vypočtěte podle definice:
∙ abc + aaa
5
PLIN004 cvičení, podzim 2010
∙ aaa + bbb
∙ ab + aaabac
∙ aaabac + ab
Př. 22
Přepište jako množiny čísla:
∙ 1
∙ 2
∙ 4
0 ≡ ∅, 𝑆(𝑥) ≡ 𝑥 ∪ {𝑥}
Př. 23
Přepište jako množiny:
∙ (𝑎, 𝑏)
∙ (1, 2, 3)
∙ (𝜑, 𝜓, 𝜔)
Př. 24
Zapište kartézský součin 𝐴𝑥𝐵, resp. 𝐴𝑥𝐵𝑥𝐶 pro množiny:
∙ 𝐴 = {1, 2, 3}, 𝐵 = {4, 5}
∙ 𝐴 = {1, 2, 3}, 𝐵 = ∅
∙ 𝐴 = {1, 2, 3}, 𝐵 = {4, 5}, 𝐶 = {1, 2, 3}
∙ 𝐴 = 𝑁, 𝐵 = {1, 2, 3}
∙ 𝐴 = 𝑁, 𝐵 = 𝑁
Př. 25
Mějme následující relace nad množinou {𝑎, 𝑏}:
6
PLIN004 cvičení, podzim 2010
∙ 𝑅1 = {(𝑎, 𝑎), (𝑏, 𝑏)}
∙ 𝑅2 = {(𝑎, 𝑏), (𝑏, 𝑎)}
∙ 𝑅3 = {(𝑎, 𝑏), (𝑏, 𝑎), (𝑎, 𝑎), (𝑏, 𝑏)}
∙ 𝑅4 = {(𝑎, 𝑎), (𝑎, 𝑏), (𝑏, 𝑏)}
∙ 𝑅5 = {(𝑎, 𝑎), (𝑏, 𝑎), (𝑏, 𝑏)}
∙ 𝑅6 = ∅
∙ 𝑅7 = {(𝑎, 𝑎), (𝑏, 𝑎)}
Které z nich jsou reflexivní, symetrické, antisymetrické, tranzitivní? Které
z nich jsou funkce? Které z funkcí jsou úplné, injektivní, surjektivní, bijekce?
Př. 26
Vyjádřete se k vlastnostem následujících relací:
∙ relace dělitelnosti ({(𝑎, 𝑏) | ∃𝑘 ∈ 𝑁(𝑎 * 𝑘 = 𝑏)})
∙ {(𝑎, 2 * 𝑎)|𝑎 ∈ 𝑁}
Př. 27
Jsou následující množiny spočetné? Pokud ano, pokuste se najít bijekci
mezi přirozenými čísly a příslušnou množinou:
∙ sudá čísla
∙ lichá čísla
∙ celá čísla
∙ racionální čísla
∙ reálná čísla v intervalu < 0, 1 >
Př. 28
7
PLIN004 cvičení, podzim 2010
Vypište přechodovou funkci následujícího automatu:
Př. 29
Který jazyk generují následující gramatiky?:
∙ 𝑆 → 𝐴𝐵, 𝐴 → 𝑎, 𝐵 → 𝑏
∙ 𝑆 → 𝑎𝑎𝑆, 𝑆 → 𝑎𝑎
∙ 𝑆 → 𝑋, 𝑆 → 𝑎𝑆, 𝑋 → 𝑎𝑏, 𝑋 → 𝑎𝑋𝑏
Př. 30
Napište (bezkontextovou) gramatiku generující následující jazyky:
∙ {𝑎}
∙ {𝑎, 𝑎𝑎, 𝑎𝑏}
∙ ∅
∙ {𝑎𝑏, 𝑎𝑏𝑎𝑏, 𝑎𝑏𝑎𝑏𝑎𝑏, ...}
∙ {𝑎, 𝑎𝑏, 𝑎𝑏𝑎, 𝑎𝑏𝑎𝑏, 𝑎𝑏𝑎𝑏𝑎, 𝑎𝑏𝑎𝑏𝑎𝑏, 𝑎𝑏𝑎𝑏𝑎𝑏𝑎, ...}
∙ {𝑎𝑖
𝑏𝑗
| 𝑖, 𝑗 > 0}
∙ {𝑎𝑖
𝑏𝑖
| 𝑖 > 0}
Je možné pro dané jazyky sestrojit také konečný automat? Pokud ano, napište
jej. Pokud ne, zamyslete se, proč to nejde.
Př. 31
Kolik existuje posloupností obsahujících právě následující prvky?
8
PLIN004 cvičení, podzim 2010
∙ Slunce, Měsíc, Země
∙ a, a, b, b, c
∙ a, a, a, a, a, b, c, d
Př. 32
Hážeme třikrát po sobě kostkou. Jaká je je pravděpodobnost, že
∙ padne po řadě 1, 2, 3
∙ padnou tři stejná čísla
∙ padne součet 5
∙ padne součet 7
Př. 33
Z místa A do místa B vedou 4 cesty, z místa B do místa C vedou 3 cesty.
Kolika různými způsoby se můžeme dostat z A do C a zpět, pokud
∙ nemáme žádná omezení na výběr cest
∙ nechceme jít dvakrát stejnou cestou
∙ chceme jít tam i zpět stejnou cestou
Jaká je pravděpodobnost, že při náhodném výběru cest si vybereme stejné
cesty jako náš kamarád, který jde stejnou trasu? (určete pro všechny výše
uvedené případy)
Př. 34
Hážeme třemi nerozlišitelnými mincemi.
∙ Kolik různých kombinací může padnout (pokud nejsme schopni rozlišit
jednotlivé mince)?
∙ Jaká je pravděpodobnost, že padnou právě tři panny?
∙ Jaká je pravděpodobnost, že padne právě jedna panna a dva orli?
9
PLIN004 cvičení, podzim 2010
Př. 35
Hážeme třemi nerozlišitelnými kostkami.
∙ Kolik různých kombinací může padnout (pokud nejsme schopni rozlišit
jednotlivé kostky)?
∙ Jaká je pravděpodobnost, že padnou tři stejná čísla?
∙ Jaká je pravděpodobnost, že padne součet 5?
Př. 36
Kolik je tříprvkových podmnožin
∙ množiny {1, 2, 3}
∙ množiny {1, 2, 3, 4, 5}
∙ množiny {1, 2, ..., 𝑛} (𝑛 ∈ 𝑁, 𝑛 > 2)
Kolik je 𝑚-prvkových podmnožin výše uvedených množin (pro libovolné
přirozené 𝑚 menší než velikost příslušné množiny)?
Př. 37
Mějme statistický soubor 2, 3, 3, 3, 5, 4, 5, 9. Určete modus, medián,
průměr, rozptyl a směrodatnou odchylku. Nakreslete histogramy pro četnost,
relativní četnost a kumulativní četnosti. (V tomto i v dalších příkladech
můžete používat kalkulačky i jiné inteligentní stroje :) na písemce budou
příklady zadány tak, aby vycházely pěkně.)
Př. 38
Pro následující soubory nakreslete graf závislosti na souboru z minulého
cvičení, pokuste se odhadnout korelaci a poté korelaci vypočtěte dosazením
do vzorce:
∙ 2, 3, 3, 3, 5, 4, 5, 9
∙ 2, 2, 2, 3, 8, 8, 5, 8
∙ 10, 9, 9, 9, 6, 7, 6, 2
∙ 1, 9, 1, 9, 1, 9, 1, 9
10
PLIN004 cvičení, podzim 2010
Př. 39
Sestavte statistický soubor, který bude mít alespoň 5 prvků, z nichž
maximálně dva budou stejné, tak, aby měl:
∙ modus 4
∙ medián 5
∙ průměr 6
∙ rozptyl 9
∙ všechny výše uvedené
∙ průměr 1000 a medián 3
∙ modus 4, medián 5 a rozptyl 0
Ke každému z navržených souborů se pokuste navrhnout druhý tak, aby jejich
korelace byly postupně -1; 0; 0,5; 1. Nakreslete grafy závislosti souborů.
11
PLIN006 cvičení, jaro 2011
Př. 1
Nakreslete grafy a určete stupně jednotlivých vrcholů:
∙ 𝑉 = {1, 2, 3, 4}, 𝐸 = {{1, 2}, {1, 4}, {2, 3}, {3, 4}, {2, 4}}
∙ 𝑉 = {𝑤, 𝑥, 𝑦, 𝑧}, 𝐸 = {{𝑤, 𝑥}, {𝑥, 𝑦}, {𝑦, 𝑧}}
∙ 𝑉 = {1, 2, 3, 4}, 𝐸 = {{1, 2}}
∙ 𝑉 = {1, 2}, 𝐸 = ∅
∙ 𝑉 = ∅, 𝐸 = ∅
Které z nich jsou souvislé, které z nich jsou stromy? Vyjádřete tyto grafy jako
relace.
Př. 2
Nakreslete a zapište množinovým zápisem následující grafy:
∙ úplný graf na 4 vrcholech
∙ úplný graf na 3 vrcholech
∙ úplný graf na 2 vrcholech
∙ úplný graf na 1 vrcholu
∙ úplný graf na 6 vrcholech
∙ kružnici na 6 (resp. 5, 4, 3, 2, 1) vrcholech
∙ cestu na 6 (resp. 5, 4, 3, 2, 1) vrcholech
∙ graf, který má stupně vrcholů postupně 2, 3, 3, 2
∙ graf, který má stupně vrcholů postupně 3, 3, 4, 4, 4
∙ graf, který má stupně vrcholů postupně 2, 4, 4, 2
Najděte v těchto grafech největší kliky, největší cykly a nejdelší cesty.
1
PLIN006 cvičení, jaro 2011
Př. 3
Které z následujících grafů jsou izomorfní? Najděte isomorfismy, případně
určete, proč grafy izomorfní nejsou.
Př. 4
Najděte nejdelší cesty a cykly v následujících grafech:
2
PLIN006 cvičení, jaro 2011
Př. 5
Nakreslete následující orientované grafy:
∙ 𝑉 = {1, 2, 3, 4}, 𝐸 = {(1, 2), (1, 4), (2, 3), (3, 4), (2, 4)}
∙ 𝑉 = {𝑤, 𝑥, 𝑦, 𝑧}, 𝐸 = {(𝑤, 𝑥), (𝑥, 𝑦), (𝑧, 𝑦), (𝑤, 𝑧)}
∙ 𝑉 = {1, 2, 3, 4}, 𝐸 = {(1, 2)}
∙ 𝑉 = {1, 2}, 𝐸 = ∅ Najděte v těchto grafech největší cykly a nejdelší
cesty.
Př. 6
V následujících grafech najděte minimální kostry a nejkratší cesty mezi
vybranými dvojicemi vrcholů. Nejprve „selským rozumem”, poté použijte
Kruskalův a Dijkstrův algoritmus.
3
PLIN006 cvičení, jaro 2011
Př. 7
V orientovaném grafu z předchozího cvičení najděte silně souvislé kompo-
nenty.
Př. 8
Naprogramujte Kruskalův a Dijkstrův algoritmus v Pythonu.
Př. 9
Zapište v jazyce logiky vlastnosti, které musí splňovat pravděpodobnostní
rozložení.
Př. 10
Vyjádřete funkčním zápisem a grafem rozložení pravěpodobnosti při hodu
kostkou.
Př. 11
Mějme následující statistický soubor (výška lidí ve skupině):
160, 160, 160, 170, 170, 180, 180, 180, 190, 210
Nakreslete graf pravděpodobnostního rozložení výšky lidí na základě tohoto
souboru. Jaká je pravděpodobnost, že člověk bude vyšší než 185?
4
PLIN006 cvičení, jaro 2011
Nakreslete graf distribuční funkce pro statistický soubor výše.
Př. 12
Hážeme dvakrát po sobě kostkou. Poprvé padlo 5. Jaká je pravděpodobnost,
že padne součet větší než 8? Použijte vzorec podmíněné pravděpodobnosti.
Př. 13
Mějme následující údaje o skupině lidí:
ID Výška (cm) Váha (kg)
1 180 80
2 170 90
3 190 60
4 190 80
5 180 80
6 190 90
Mějme člověka, o kterém víme, že měří 190 cm. Jaká je pravděpodobnost,
že jeho váha bude alespoň 80 kg? (Předpokládejme, že naše data jsou
reprezentativní. (Kterému zákonu tento náš předpoklad odporuje?))
Př. 14
Dokažte Bayesův vzorec.
Př. 15
Všichni chlapci nosí kalhoty, polovina dívek nosí také kalhoty (druhá
polovina nosí sukně :) ). Vidíme z dálky člověka, který má kalhoty. Jaká je
pravděpodobnost, že je to chlapec?
Př. 16
Mějme následující text a předpokládejme, že pro dané účely je to reprezentativní
vzorek:
Stát má stát na straně pro stát vhodné. Stát na straně občanů je pro stát
obvykle nevýhodné. Nicméně stát by se mohl stát poctivějším.
Jaká je pravděpodobnost, že slovo „stát” (bez rozlišení velikosti písmen)
je sloveso (podst. jméno), pokud:
5
PLIN006 cvičení, jaro 2011
∙ neuvažujeme žádnou informaci o kontextu
∙ slovo „stát” stojí na začátku věty
∙ předchozí slovo je předložka
∙ následující slovo obsahuje právě dvě písmena
Př. 17
Máme podezření, že hrací kostka není vyvážená, ale že na ní častěji padají
šestky. Máme v úmyslu kostku sérií 20 pokusů vyzkoušet. Kolikrát musí
padnout šestka, aby se naše podezření statisticky potvrdilo s možností chyby
méně než 1 %?
6