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