PLIN004 cvičení, podzim 2010
Př. 1
Vyjádřete výroky (A ∧ B), (A ∨ B) pouze pomocí negace a implikace.
Př. 2
Vyjádřete výrok (A ⇒ B) pouze pomocí negace a disjunkce.
Př. 3
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:
• A ⇒ C
• (A ∨ B) ⇒ C
• (A ∧ ¬A)
• (A ∧ ¬A) ⇒ C
• (¬A ∧ ¬B) ⇒ C
• (¬A ∧ ¬B) ⇒ ¬C
Které z nich jsou pravdivé?
Př. 4
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.
1
PLIN004 cvičení, podzim 2010
Můžete používat predikát Prime(x) a aritmetiku nad celými čísly. Které
z výroků výše jsou pravdivé?
Př. 5
Přepište v jazyce predikátové logiky a dokažte:
• žádné sudé číslo není zároveň liché
• (2 ∗ x ∗ x = y ∗ y) ⇒ 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ř. 6
Dokažte indukcí pro všechna přirozená n ≥ 1:
• n + 1 ≤ 2 ∗ n
• 2 ∗ n ≤ 2n
• 1 + 2 + ... + n = n/2 ∗ (1 + n)
Př. 7
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ř. 8
Dokažte strukturální indukcí, že každý celočíselný výraz podle definice
výše má sudý počet závorek.
Př. 9
Jsou následující výroky pravdivé?
2
PLIN004 cvičení, podzim 2010
• {∅} ∈ {∅}
• {∅} ⊆ {∅}
• {∅} ∈ {{∅}}
• {∅} ⊆ {{∅}}
• {4} ∈ {x ∈ N | x > 3}
• 4 ∈ {x ∈ N | x > 3}
• {4} ⊆ {x ∈ N | x > 3}
• 4 ⊆ {x ∈ N | x > 3}
• {4} ∈ {{x} | x ∈ N ∧ x > 3}
Př. 10
Zapište P(A) pro množiny:
• A = {1, 2, 3}
• A = {∅, {∅}}
Př. 11
Zapište:
• množinu všech sudých čísel
• množinu všech prvočísel
Můžete používat množinu N, aritmetiku nad ní a operátor dělitelnosti.
Př. 12
Definujte:
• množinový rozdíl
• symetrický množinový rozdíl
Př. 13
Dokažte:
3
PLIN004 cvičení, podzim 2010
• a ∈ A ∩ B ⇒ a ∈ A
• a ∈ A ∩ B ⇒ a ∈ A ∪ B
• a ∈ A ∧ A ⊆ B ⇒ a ∈ B
Př. 14
Přepište v jazyce predikátové logiky Peanovy axiomy
• existuje nula
• každé číslo x má následníka S(x)
• nula není následníkem žádného čísla
• různá čísla mají různé následníky: a = b ⇒ S(a) = S(b)
Př. 15
Mějme definováno sčítání a násobení následujícími předpisy:
• a + 0 = a
• a + S(b) = S(a + b)
• a ∗ 0 = 0
• a ∗ S(b) = (a ∗ b) + a
Vypočtěte podle definic:
• 1 + 1
• 2 + 2
• 2 * 1
• 1 * 2
( 1 = S(0), 2 = S(1) )
Př. 16
Definujme induktivně slova nad množinou {a, b, c}:
• a, b, c jsou slova
4
PLIN004 cvičení, podzim 2010
• pokud x je slovo, pak ax, bx, cx jsou slova
Definujme sčítání řetězců následovně: Pro slova x a y
• a + x = ax
• b + x = bx
• c + x = cx
• ya + x = y + ax
• yb + x = y + bx
• yc + x = y + cx
Vypočtěte podle definice:
• abc + aaa
• aaa + bbb
• ab + aaabac
• aaabac + ab
Př. 17
Přepište jako množiny čísla:
• 1
• 2
• 4
0 ≡ ∅, S(x) ≡ x ∪ {x}
Př. 18
Přepište jako množiny:
• (a, b)
• (1, 2, 3)
• (φ, ψ, ω)
5
PLIN004 cvičení, podzim 2010
Př. 19
Zapište kartézský součin AxB, resp. AxBxC pro množiny:
• A = {1, 2, 3}, B = {4, 5}
• A = {1, 2, 3}, B = ∅
• A = {1, 2, 3}, B = {4, 5}, C = {1, 2, 3}
• A = N, B = {1, 2, 3}
• A = N, B = N
Př. 20
Mějme následující relace nad množinou {a, b}:
• R1 = {(a, a), (b, b)}
• R2 = {(a, b), (b, a)}
• R3 = {(a, b), (b, a), (a, a), (b, b)}
• R4 = {(a, a), (a, b), (b, b)}
• R5 = {(a, a), (b, a), (b, b)}
• R6 = ∅
• R7 = {(a, a), (b, a)}
Které z nich jsou reflexivní, symetrické, antisymetrické, tranzitivní? Které
z nich jsou funkce? Které z funkcí jsou úplné, injektivní, surjektivní, bijekce?
Př. 21
Vyjádřete se k vlastnostem následujících relací:
• relace dělitelnosti ({(a, b) | ∃k ∈ N(a ∗ k = b)})
• {(a, 2 ∗ a)|a ∈ N}
Př. 22
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:
6
PLIN004 cvičení, podzim 2010
• sudá čísla
• lichá čísla
• celá čísla
• racionální čísla
• reálná čísla v intervalu < 0, 1 >
Př. 23
Vypište přechodovou funkci následujícího automatu:
Př. 24
Který jazyk generují následující gramatiky?:
• S → AB, A → a, B → b
• S → aaS, S → aa
• S → X, S → aS, X → ab, X → aXb
Př. 25
Napište (bezkontextovou) gramatiku generující následující jazyky:
• {a}
• {a, aa, ab}
• ∅
• {ab, abab, ababab, ...}
7
PLIN004 cvičení, podzim 2010
• {a, ab, aba, abab, ababa, ababab, abababa, ...}
• {ai
bj
| i, j > 0}
• {ai
bi
| i > 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ř. 26
Kolik existuje posloupností obsahujících právě následující prvky?
• Slunce, Měsíc, Země
• a, a, b, b, c
• a, a, a, a, a, b, c, d
Př. 27
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ř. 28
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
8
PLIN004 cvičení, podzim 2010
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ř. 29
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?
Př. 30
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ř. 31
Kolik je tříprvkových podmnožin
• množiny {1, 2, 3}
• množiny {1, 2, 3, 4, 5}
• množiny {1, 2, ..., n} (n ∈ N, n > 2)
Kolik je m-prvkových podmnožin výše uvedených množin (pro libovolné
přirozené m menší než velikost příslušné množiny)?
Př. 32
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
9
PLIN004 cvičení, podzim 2010
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ř. 33
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
Př. 34
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ů.
10