Matematická logika cvi£ení 47 Libor B¥hounek
www.cs.cas.cz/behounek/teaching/malog12
LS 2012/13, P°F OU, 4.25. 3. 2013
Cvi£ení 1. Posu¤te následující výroky z hlediska adekvátnosti dvojhodnotové sémantiky
(a jejich pravdivostní hodnoty):
1. Knihovna je otev°ená. 2. Úst°ední knihovna MKO byla 3. 3. 2013 ve 14 hodin otev°ená. 3.
x>5
4.
20! > 1020
5.
15
je malé p°irozené £íslo.
6. Judea je hornatá. 7. Zítra vypukne námo°ní bitva. 8. Ve vzdálenosti 45 miliard sv¥telných let existuje obydlená planeta. 9. Pro kaºdý systém neprázdných mnoºin existuje mnoºina mající jednoprvkový pr·nik s kaºdou z nich. 10. Existuje nekone£n¥ mnoho prvo£íselných dvoj£at. 11. Existuje mnoºina reálných £ísel, kterou nelze bijektivn¥ zobrazit na mnoºinu v²ech p°irozených £ísel ani na mnoºinu v²ech reálných £ísel. 12. Sou£asný francouzský král je holohlavý. 13. S£ítání in nitesimáln¥ malých veli£in je komutativní. Cvi£ení 2. Formalizujte následující výroky pomocí základních výrokových spojek. Pozorujte
p°ípadnou nejednozna£nost formalizace a vyjasn¥te jejich pravdivostní podmínky:
1. Není pravda, ºe Jan není nezam¥stnaný. 2. Není horko ani zima. 3. Není ani £ervený ani velký. Není £ervený a velký. 4. Nenastává p°ípad, ºe tekutina v°e nebo mrzne. 5. Nem·ºe být £ervený a velký. Nem·ºe být £ervený a nem·ºe být velký. 6. Je £ervený nebo velký. Je bu¤ £ervený, nebo velký.
1
7. Sedím nebo pí²u. Sedím, nebo pí²u. 8. Jestliºe
2 + 2 = 5,
jsem papeº.
Cvi£ení 3. Posu¤te adekvátnost formalizace následujících výrok· pomocí p°íslu²ných výro-
kových spojek:
1. Není vysoký. Je nevysoký. Není nevysoký. 2. Vstal a upadl. Upadl a vstal. 3. Jana a Petra jely spolu na kole. Dámy a pánové se p°ed tancem spárovali. Jablka a hru²ky byly promíchány. 4. Za stovku dostanu krabi£ku Marlborek a za stovku dostanu krabi£ku Camelek. Za stovku dostanu krabi£ku Marlborek a krabi£ku Camelek. 5. Nezabil jsem ji a nezabil jsem ji a nezabil jsem ji! 6. Jestliºe nezabil Kennedyho Oswald, zabil ho n¥kdo jiný. Kdyby nezabil Kennedyho Oswald, zabil by ho n¥kdo jiný. 7. Kdyby klokani nem¥li ocas, p°epadávali by dop°edu. 8. Pokud klesá po£et pirát·, dochází ke globálnímu oteplování. 9. New York je v USA, práv¥ kdyº Titan je m¥sícem Saturnu. 10. Jestliºe 43 není d¥litelné 7, pak 43 je prvo£íslo. Jestliºe 42 je d¥litelné 7, pak 43 je prvo£islo. islo 43 je prvo£íslo, práv¥ kdyº není d¥litelné 7. Cvi£ení 4. Doloºte, ºe výroková spojka
A
nutn¥
A
není extenzionální: tj. najd¥te p°íklady
výrok·: 1. nutn¥ pravdivých, 2. pravdivých, ale nikoli nutn¥ (tzv.
kontingentn¥
pravdivých),
3. nutn¥ nepravdivých a 4. nepravdivých, ale nikoli nutn¥. (Jak z jejich existence plyne neextenzionalita
?)
Cvi£ení 5. Nech´ atomický výrok
p
je pravdivý,
q
nepravdivý a
r
pravdivý. Vypo£t¥te prav-
divostní hodnotu výrok·:
1.
(p ∧ q) ↔ (r ∨ ¬p)
2.
¬¬p ∨ ¬p
3.
((p → q) → q) → p
Cvi£ení 6. Vypo£ítejte pravdivostní tabulky formulí:
1.
(p ↔ q) ↔ (¬q ↔ r)
2.
p ∧ ¬p
3.
(p → q) ∨ (q → p)
Cvi£ení 7. Porovnejte pravdivostní tabulky sloºených výrok·
jící dvojzna£nému výroku p a
q
nebo
r.
(p∧q)∨r a p∧(q∨r), odpovída-
Najd¥te matematický, p°írodov¥decký nebo právní
výrok, kde tato dvojzna£nost hraje roli. Vymyslete jiné dvojzna£nosti dané nevyzna£ením závorek v p°irozené °e£i a jejich (pokud moºno fatální) následky.
2
Cvi£ení 8. Ov¥°te, zda jsou výroky ve dvojici logicky ekvivalentní:
1. Jestliºe
5
je liché £íslo, pak
52
je liché £íslo. Jestliºe
5
je liché £íslo, pak
52
je liché £íslo. íslo
52
není liché £íslo, pak
5
není liché
£íslo. 2. Jestliºe
52
je liché, práv¥ kdyº £íslo
Cvi£ení 9. Ov¥°te v²echny logické ekvivalence z p°edná²ky, tj.:
1.
A ≡ A ∧ A ≡ A ∨ A ≡ ¬¬A ≡ ¬A → A
2.
A∧B ≡B∧A
3.
A∨B ≡B∨A
4.
(A ∧ B) ∧ C ≡ A ∧ (B ∧ C)
5.
(A ∨ B) ∨ C ≡ A ∨ (B ∨ C)
6.
A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C)
7.
A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C)
8.
¬(A ∧ B) ≡ ¬A ∨ ¬B
9.
¬(A ∨ B) ≡ ¬A ∧ ¬B
10.
A → B ≡ ¬A ∨ B ≡ ¬(A ∧ ¬B)
11.
A ∧ B ≡ ¬(¬A ∨ ¬B) ≡ ¬(A → ¬B)
12.
A ∨ B ≡ ¬(¬A ∧ ¬B) ≡ ¬A → B
13.
A ↔ B ≡ (A → B) ∧ (B → A) ≡ (A ∧ B) ∨ (¬A ∧ ¬B)
14.
A ? B : C ≡ (A → B) ∧ (¬A → C)
15.
A NAND B ≡ ¬(A ∧ B)
16.
> ≡ A → A ≡ A ∨ ¬A ≡ ¬(A ∧ ¬A) ≡ A ↔ A ≡ ¬⊥
17.
⊥ ≡ ¬> ≡ A ∧ ¬A
Cvi£ení 10. Dokaºte, ºe následující mnoºiny spojek jsou funk£n¥ úplné:
1.
{∨, ¬}
2.
{→, ¬}
3.
{NAND}
4.
{NOR}
Cvi£ení 11. Dokaºte, ºe následující mnoºiny spojek nejsou funk£n¥ úplné:
1.
{∧, ∨}
2.
{→}
3
5
je liché.
Cvi£ení 12. Najd¥te disjunktivní normální formu následujících formulí (úplnou, pokud exis-
tuje):
1.
¬(p ↔ q)
2.
(p ∨ q) ∧ (r ∨ s) ∧ (t ∨ u)
Cvi£ení 13. Najd¥te konjunktivní normální formu následující formule (úplnou, pokud exis-
tuje):
1.
¬(p → q)
Cvi£ení 14. Sestavte obvod z
pem
z = FNAND (x, y)),
NAND-hradel (tj. sou£ástek s dv¥ma vstupy x, y a jedním výstup, q, r výstup daný pravdivostní funkcí
který dává vstupu s hodnotami
formulí:
1.
p ∨ q , p ∧ q , ¬p, p → q , p ↔ q
2. Ud¥lejte totéº z
NOR-hradel.
(Vyuºijte výsledky cvi£ení 10.3. et°ete hradla uvaºte, ºe výstup lze kopírovat.) Cvi£ení 15. Sestavte z
NAND-hradel
obvod, který se£te dv¥ dvouciferná dvojková £ísla.
Cvi£ení 16. Ov¥°te tautologi£nost tautologií z p°edná²ky, tj.:
1.
((p → q) → p) → p
2.
A ∨ ¬A
3.
¬(A ∧ ¬A)
4.
¬A → (A → B)
5.
(A ∧ ¬A) → B
6.
A → (B → A)
7.
(A → B) ∨ (B → A)
Cvi£ení 17. Rozhodn¥te tautologi£nost následujících formulí. Uvaºte, která z metod rozhodo-
vání tautologi£nosti probíraných na p°edná²ce (pravdivostní tabulka, p°evod na logicky ekvivalentní známou tautologii, zkrácené prohledávání pravdivostní tabulky £i analytická tabla) je v daném p°ípad¥ nejrychlej²í.
1.
(p → q) ∨ (q → r)
2.
¬(p → q) → ¬q
3.
(p → ¬p) → p
4.
(p → ¬p) → ¬p
5.
((p → q) → q) → p
6.
(((p → q) → r) & ((q → p) → r)) → r 4
7.
((p ↔ q) ↔ r) ↔ (p ↔ (q ↔ r))
8.
((p ∨ q ∨ r) ∧ (s ↔ t)) ∨ (¬p ∧ ¬(¬r → q)) ∨ (s ∧ ¬t) ∨ (t ∧ ¬s)
Cvi£ení 18. Uvaºujme restrikci klasické výrokové logiky, kdy máme k dispozici jedinou vý-
rokovou prom¥nnou.
1. Rozmyslete, jak bude vypadat její Lindenbaumova algebra. 2. Rozmyslete totéº pro dv¥ výrokové prom¥nné. Cvi£ení 19. Nech´
1. Ov¥°te
ϕ
je formule
¬(p ∧ q) → (¬r ∧ q)
a
ψ
formule
(s → p) ∧ (s → ¬r).
ϕ |= ψ .
2. Ov¥°te tvrzení anglické Wikipedie (heslo Craig interpolation k 18. 3. 2013), ºe interpolantem
ϕ |= ψ
je
p ∨ ¬r.
3. Najd¥te interpolant
ϕ |= ψ
algoritmem z d·kazu v¥ty o interpolaci.
5
