6
Kapitola 2
Výroková logika
2.1 Výroky
2.1.1 Příklad Rozhodněte, zda následující posloupnosti symbolů jsou výrokové
formule. Jde-li o formuli, pak sestrojte její strom, určete její hloubku a
uveďte vechny její podformule (Připomeňte si nai úmluvu o negaci a vynechávání
vnějích závorek!):
a) ¬(¬x ⇒ ¬¬y);
b) x;
c) (¬x ∨ y) ⇒ z;
d) (x ⇒ y) ∧ y ⇔ x;
e) ((¬(x ∧ y) ∨ z) ⇒ u) ⇔ v;
f) (x ⇐ y).
Výsledek: a) Formule, hloubka 4. b) Formule, hloubka 0. c) Formule,
hloubka 3. d) Není formule, chybí pár závorek. e) Formule, hloubka 5. e) Není
formule, ⇐ není logická spojka.
2.1.2 Příklad Ve kterých ohodnoceních u je formule
a) (x ⇒ ¬x) ∧ (¬x ⇒ x) pravdivá;
b) x ⇒ (x ⇒ y) nepravdivá;
c) x ∧ (y ⇒ (z ∨ x)) pravdivá;
d) (x ⇒ ¬x) ⇔ ¬x nepravdivá;
e) (x ∨ ¬y) ⇒ (¬x ∧ y) pravdivá;
e) (((x ∨ y) ∧ z) ∧ y) ∨ x nepravdivá?
Marie Demlová: Příklady k předmětu Matem. logika 8. května 2007, 15:19
2.1. Výroky [070508-1519] 7
Výsledek: a) V žádném pravdivostním ohodnocení. b) Pro pravdivostní
ohodnocení u(x) = 1, u(y) = 0. c) Pro všechna ohodnocení, pro něž je u(x) =
= 1. d) V žádném pravdivostním ohodnocení. e) Pro pravdivostní ohodnocení
u(x) = 0 a u(y) = 1. f) Pro všechna ohodnocení, pro něž logická proměnná x je
nepravdivá a aspoň jedna z logických proměnných y, z je také nepravdivá. Tj.
u(x) = 0 a současně u(y) = 0 nebo u(z) = 0.
2.1.3 Příklad Zjistěte, zda jsou dané formule tautologie, kontradikce nebo
splnitelné formule:
a) (x ⇒ y) ⇒ (x ∨ y);
b) ((x ⇒ y) ⇒ (¬x ∧ y)) ∨ ¬y;
c) ((x ∧ y) ∨ (¬x ∧ ¬y)) ⇔ ((¬x ∨ ¬y) ∧ (x ∨ y));
d) (x ⇒ (x ⇒ y)) ⇒ y;
e) ((x ⇒ z) ∧ (y ⇒ z)) ⇒ ((x ∧ y) ⇒ z);
f) ((x ⇒ z) ∨ (y ⇒ z)) ⇒ (x ⇒ y).
Výsledek: a) Splnitelná formule, která není tautologie. b) Splnitelná formule,
která není tautologie. c) Kontradikce. d) Splnitelná formule, která není
tautologie. e) Tautologie. f) Splnitelná formule, která není tautologie.
2.1.4 Příklad Ukažte, že následující formule jsou tautologie (jde o důležité
tautologie):
a) ¬¬α ⇔ α (dvojí negace);
b) ¬(α ∨ β) ⇔ (¬α ∧ ¬β) (de Morganovo pravidlo);
c) ¬(α ∧ β) ⇔ (¬α ∨ ¬β) (de Morganovo pravidlo);
d) (α ⇒ β) ⇔ (¬α ∨ β);
e) (α ⇔ β) ⇔ ((α ⇒ β) ∧ (β ⇒ α));
f) (α ∧ β) ⇔ (β ∧ α), totéž platí pro disjunkci (komutativita);
g) (α ∧ (β ∧ γ)) ⇔ ((α ∧ β) ∧ γ), totéž platí pro disjunkci (asociativita);
h) (α ∧ (β ∨ γ)) ⇔ ((α ∧ β) ∨ (α ∧ γ)) (distributivita);
i) (α ∨ (β ∧ γ)) ⇔ ((α ∨ β) ∧ (α ∨ γ)) (distributivita);
j) (α ⇒ ¬α) ⇔ ¬α;
k) α ∨ ¬α (vyloučení třetího);
l) (α ∧ ¬α) ⇒ β;
m) (α ⇒ (β ⇒ γ)) ⇔ ((α ∧ β) ⇒ γ);
n) (α ⇒ β) ⇔ (¬β ⇒ ¬α);
o) ((α ⇒ β) ∧ (β ⇒ γ)) ⇒ (α ⇒ γ) (tranzitivita ⇒);
p) (α ⇒ (β ∧ ¬β)) ⇔ ¬α;
q) ((α ⇒ β) ⇒ α) ⇔ α (Peirceův zákon).
Marie Demlová: Příklady k předmětu Matem. logika 8. května 2007, 15:19
8 [070508-1519] Kapitola 2. Výroková logika
2.1.5 Příklad V tomto příkladu je α některá tautologie, β některá kontradikce
a ϕ je výroková formule. Ukažte, že
a) (β ∨ ϕ) ⇔ ϕ je tautologie,
b) (α ∨ ϕ) je tautologie,
c) (β ∧ ϕ) je kontradikce.
2.1.6 Příklad Jestliže formule ϕ ⇒ ψ je tautologie, pak i formule (ϕ ∧ ψ) ⇔
⇔ ϕ a (ϕ ∨ ψ) ⇔ ψ jsou tautologie. Ukažte.
2.2 Sémantický důsledek
2.2.1 Příklad Ukažte, že platí následující konsekventy:
a) {α ⇒ β, β ⇒ γ} |= α ⇒ γ;
b) {α ⇒ β, ¬β} |= ¬α;
c) {α ∨ β, α ⇒ γ, β ⇒ γ} |= γ;
d) {α ⇒ β, α ⇒ ¬β} |= ¬α;
e) {(a ∧ b) ⇒ c, (a ∧ ¬b) ⇒ c} |= a ⇒ c
2.2.2 Příklad Přeformulujte následující věty do formulí výrokového počtu a
zjistěte, zda formule pod čarou je konsekventem množiny formulí nad čarou.
a) Jestliže prší a já si vezmu deštník, nezmoknu.
Vezmu si deštník.
Nezmoknu.
b) Nebude pršet.
Spadnu do potoka.
Když spadnu do potoka, budu mokrý.
Jestliže nebude pršet, budu mokrý.
c) Jestliže sním neznámé houby a není mi dobře, vyhledám lékaře.
Jestliže sním neznámé houby a je mi dobře, nevyhledám lékaře.
d) Není pravda, že Petr hraje fotbal i hokej.
Petr nehraje fotbal.
Petr hraje hokej.
e) Je doma nebo ve škole.
Jestliže je doma, hraje počítačové hry.
Jestliže nehraje počítačové hry, pak je ve škole.
f) Jestliže jsem vzhůru, pracuji, ale jestliže spím, jsem v posteli.
Buď jsem vzhůru nebo spím.
Jestliže pracuji, pak nejsem v posteli, a jestliže spím, pak nepracuji.
Jsem v posteli.
Marie Demlová: Příklady k předmětu Matem. logika 8. května 2007, 15:19
2.2. Sémantický důsledek [070508-1519] 9
Výsledky: a) Označme: p = prší, b = beru si deštník, n = nezmoknu.
Pak výroky nad čarou odpovídají množině {(p ∧ b) ⇒ n, b}, výrok pod čarou
odpovídá formuli n a tento konsekvent neplatí.
b) Označme: n = nebude pršet, s = spadnu do potoka, b = budu mokrý. Pak
výroky nad čarou odpovídají množině {n, s, s ⇒ b}, výrok pod čarou odpovídá
formuli n ⇒ b a tento konsekvent platí.
c) Označme: s = sním neznámé houby, j = je mi dobře, v = vyhledám lékaře.
Pak výroky nad čarou odpovídá formuli (s ∧ ¬j) ⇒ v, výrok pod čarou formuli
(s ∧ j) ⇒ ¬v a tento konsekvent neplatí.
d) Označme: f = Petr hraje fotbal, h = Petr hraje hokej. Pak výroky nad
čarou odpovídají množině {¬(f ∧ h), ¬f}, výrok pod čarou odpovídá formuli h
a tento konsekvent neplatí.
e) Označme: d = je doma, = je ve škole, h = hraje počítačové hry. Pak
výroky nad čarou odpovídají množině {d ∨ , d ⇒ h}, výrok pod čarou odpovídá
formuli ¬h ⇒ a tento konsekvent platí.
f) Označme: v = jsem vzhůru, p = pracuji, s = spím, j = jsem v posteli.
Pak výroky nad čarou odpovídají množině {(v ⇒ p)∧(s ⇒ j), v ⊕s, (p ⇒ ¬j)∧
∧ (s ⇒ ¬p)}, výrok pod čarou formuli j a tento konsekvent neplatí.
2.2.3 Příklad Rozhodněte, zda množina formulí M je splnitelná nebo nespl-
nitelná:
a) M = {a ∨ ¬b, b ∧ ¬a, b ⇒ a},
b) M = {a ⇒ b, a ⇒ ¬b, a ∧ b},
c) M = {(a ∨ b) ⇒ c, (a ∧ ¬b) ⇒ c, a ⇒ c},
d) M = {(a ∧ b) ∧ (¬a ∨ ¬b)}.
Výsledky: a) Nesplnitelná. b) Nesplnitelná. c) Splnitelná. d) Nesplnitelná.
2.2.4 Příklad Je dána množina výrokových formulí S = {α, β, γ}. Ukažte,
že následující tvrzení jsou ekvivalentní:
(i) S je splnitelná množina;
(ii) ¬((α ∧ β) ∧ γ) není tautologie;
(iii) (α ∧ β) ⇒ ¬γ není tautologie.
Marie Demlová: Příklady k předmětu Matem. logika 8. května 2007, 15:19