IBOOO Úvod do informatiky -- příklady na procvičení
Sada 8 -- Řešení
Upozornění
Vzorová řešení dostáváte k dispozici, abyste mohli zkontrolovat správnost svých řešení.
Můžete je použít i jako návody k řešení jednotlivých příkladů tak, že je budete číst po
částech a budete se snažit další krok provést vždy sami. Příklady ztratí veškerý svůj smysl,
pokud se je budete učit jako básničku. Snažte se nad nimi přemýšlet a vyřešit je sami,
než se podíváte do vzorových řešení.
Téma
Vhodně definované vlastnosti relací, uzávěry relací. Výroky. Výroková logika, valuace,
normální tvar výrokových formulí, negace výrokových formulí, pravdivost a splnitelnost
výrokových formulí. Predikátová logika, negace formulí predikátové logiky.
Příklad 1.
a) Určete reflexivní uzávěr relace {(x,y) \ xy = 0} C No x Nob)
Určete symetrický uzávěr relace {(x,y) \ xy = 0} C No x Noc)
Určete tranzitivní uzávěr relace {(x,y) \ xy = 0} C No x Nod)
Určete reflexivní, symetrický a tranzitivní uzávěr relace {(x,y) \ xy = 0} C No x Noe)
Určete reflexivní uzávěr relace {(2i + 1, li + 3) | i E No}.
f) Určete symetrický uzávěr relace {(2i + 1, 2i + 3) | i E No}.
g) Určete tranzitivní uzávěr relace {(2i + 1, 2i + 3) | i E No}.
h) Určete reflexivní, symetrický a tranzitivní uzávěr relace {(2i + 1, 2i + 3) | i E No}.
i) Nechť R = {(x, y) \ x < 2y A y < 2x} C M x R , kde ÍR značí množinu všech reálných
čísel. Určete R o R.
Příklad 2.
Nechť A, B, C, D jsou atomické propozice. Nechť v je valuace, která splňuje v(Ä) =
= ľ{B) = true a v(C) = v(D) = false. Podle definice Sv určete Sv(<p), je-li
a) (p = (C V D) => -.(> A (A => B))
b) ip = (-.A => (B A -.)) => ^ A
c) (p = (-.C => - ( - A <& -iß)) A ((Ľ => S) V (-.B => C))
Řešení
Poznámka k terminologii: Na přednášce byl místo pojmu ,,atomická propozice" definován
pojem ,,výroková proměnná". Mezi těmito pojmy nebudeme rozlišovat, budeme je
považovat za vzájemně zaměnitelné.
Poznámka pro jistotu, kterou se nenechte zmást: zápis <p = ... znamená, že formuli
napravo od = budeme označovat symbolem ip. Mohli bychom použít i symbol =, avšak
tento symbol byl ve skriptech používán pro sémantickou ekvivalenci formulí z í>. Tedy
= C $ x $ , zatímco = C E x f , kde E je množina znaků, které používáme pro označování
prvků í>. Navíc relace = je zcela definována sémantikou formulí, zatímco relaci = definujeme
v každém příkladě podle potřeby. Protože značení v tomto směru není ustálené a
1
rozdíly se často zanedbávají, protože nevedou k nejasnostem, budeme i my při opravování
k tomuto značení tolerantní.
Budeme postupovat přesně podle definice funkce Sv, jak byla uvedena na přednášce.
Z definice je vidět, že pro výpočet Sv(p) pro nějakou výrokovou formuli p již musíme znát
hodnoty Sv(r
tp) všech podformulí tp formule p. Budeme tedy postupovat ,,zevnitř" formule
od strukturálně nejjednodušších podformulí (tj. atomických propozic) k podformulím se
složitější strukturou a pro každou takovou podformulí tp určíme hodnotu Su(ip) na základě
již dříve vypočítaných hodnot.
Výpočty odpovídají prohledávání syntaktickému stromu formule do hloubky a zleva
doprava, pokud již víte, co to znamená.
Ve formulích má samozřejmě negace nejvyšší prioritu. Priorita dalších operátorů je
zde nepodstatná, protože struktura formulí je zcela určena uzávorkováním.
a)
SV{C) = false O) z definice v
SV{D) = false (Ü) z definice v
S,,(CVD) = false (iii) z (i) a (ii)
SM) = true (iv) z definice v
SV{B) = true (v) z definice v
SV{A => B) = true (vi) z (iv) a (v)
SV{D A(A^ .B)) = false (vii) z (ii) a (vi)
SM(D
A (A => B))) = true (viii) z (vii)
1
y D) 4 n ( D A (A^ B))) = true (ix) z (iii) a (viii)
b)
SM) = true O) z definice v
SM A) = false (Ü) z (i)
SAB) = true (iii) z definice v
SMB) = false (iv) z (iii)
5 , ( 5 A n f l ) = false (v) z (iii) a (iv)
SMA
=> (BA-ˇB)) = true (vi) z (ii) a (v)
SM^A) = true (vii) z(ii)
^ ( ( n i ^ ^ A n ß ) ) = ^ - r-.A) = true (viii) z (vi) a (vii)
c)
SM)
SMC)
SM)
SMA)
SM)
SMB)
false (i) z definice v
true (Ü) z (i)
true (iii) z definice v
false (iv) z (iii)
true (v) z definice v
false (vi) z (v)
2
SV(-^A <& -.5) = true (vii) z (iv) a (vi)
SV(^A<*^B)) = false (viii) z (vii)
S ^ C ^ ^ A ^ ^ ß ) ) = false (ix) z (ii) a (viii)
SV(D) = false (x) z definice v
SV(D => B) = true (xi) z (x) a (v)
SV(^B => C) = true (xii) z (vi) a (i)
SV{{D ^ B)y (-.5 => C)) = true (xiii) z (xi) a (xii)
SV((-^C => -.(-.A ^ -.)) A ((Ľ => B) V (-.5 ^ C ) ) ) = false (xiv) z (ix) a (xiii)
Příklad 3.
Nechť A, B, C, D jsou atomické propozice. Znegujte následující formule. (Protože znegováním
se myslí i převedení do normálního tvaru, máte za úkol pro formuli <p vypočítat
J7
(-up) pomocí příslušných funkcí T a Q definovaných na přednášce.)
a) <p = (C V D) => -.(> A (A => S))
b) p = (-.C => - ( - A <& -iß)) A ((Ľ => S) V (-.B => C))
c) <p = \/x G No- x > 0 =/- 3y, z G No- y | x A z | x =>- 3u> G No- w > x A z | w A y | w
Řešení
Protože funkce SV : í> --ˇ {true, false} nezobrazuje formule výrokové formule na jiné
formule výrokové logiky, nemohli jsme v předchozím příkladě začít se zápisem Sv(p>)
a pomocí ,,rovnosti" se k výsledku ,,dopočítat". Například význam zápisu true A false,
jakkoliv je intuitivně zřejmý, není formálně definován. Museli jsme proto postupovat
,,zdola nahoru", od strukturálně nejjednodušších podformulí ke složitějším.
Naproti tomu u funkcí T : í> --ˇ í> a Q : í> --ˇ í> to možné je. Přitom í> může
být množina všech formulí výrokové logiky i množina všech formulí predikátové logiky
(funkce Sv není pro predikátovou logiku definována). Jak už je naznačeno v zadání,
můžeme normální tvar negace formule p> určit tak, že začneme s výrazem T(-^p>) a podle
definic funkcí T a Q formuli -up upravovat shora dolů. Aplikaci funkce na složitější formuli
upravíme na aplikací funkcí na strukturálně jednodušší formule.
Stejně jako v předchozím příkladě odpovídají výpočty prohledávání syntaktického
stromu formule do hloubky a zleva doprava. Zde je možné výpočet charakterizovat i
stručněji: vždy se upravuje nejlevější výskyt aplikace funkce T nebo Q.
Pro výpočet je důležitá priorita operátorů. Pro úplnost ji zde uvedeme. Nejvyšší
prioritu má negace a kvantifikátory, následují konjunkce a disjunkce a nakonec s nejnižší
prioritou implikace a ekvivalence. U kvantifikátorů si všimněte rozsahu jejich platnosti.
Použití ,,tečkové konvence" označuje, kde kvantifikovaná formule začíná, ale neoznačuje,
kde končí. Standardně se předpokládá, že kvantifikovanou formuli ukončuje závorka, v níž
se nalézá kvantifikátor, nebo konec formule. K porozumění této konvence by mělo pomoci
vzorové řešení -- určení normálního tvaru formule je výpočet po struktuře formule.
a)
^(-"((C V D ) 4 -.(> A (A => B))))
= Q((C V D ) ^ -.(> A (A => B)))
= J=(C V D) A g(^(D A(A^ B)))
3
{T{C) V T{D)) A (-.(> A(A^ B)))
(C V F{D)) A 0(-.(> A (A ^ ß)))
( C V D ) A Ö ( n ( D A ( A = > 5 ) ) )
(CVD)AF(DA(A^B))
( C V D ) A (:F(>) A :F(A => ß ) )
( C V f l ) A ( D A f ( A ^ ß ) )
(C V Ľ) A (Ľ A (J-(A) => ^ ( ß ) ) )
(C V ß ) A (D A (A => T(B)))
(CVD)A(DA(A=>B))
b)
:F(-.((-.C ^ -,(-,^4 & -,ß)) A ((> => ß ) V (-.ß =*
= 0((-iC => - ( - A ^ -iß)) A ((> => ß ) V (-.ß =;
= ^(-.C => - ( - A ^ -iß)) V g ((D => ß ) V (-.ß =
= Ô(-C) A ö ( - ( - A ^ -nß))) V  ( ( ß ^ ß ) V ("
C))))
C)))
>C))
iß => C))
g{c) A sH-,A ^ -.ß))) v ö((ß ^ ß) v (-.ß => c))
^C A ö(-"(-"A ^ -.ß))) v ö ( ( ß => ß ) V (-.ß => C))
^C A T{-^A <* -iß)) V  ( ( ß => ß ) V (-.ß => C))
nCA
nCA
nCA
nCA
nCA
nCA
nCA
nCA
nCA
nCA
nCA
nCA
nCA
:F(-.A) ^ ^(--ß))) v ((ß => ß) v (-.ß => c))
ö(A) ^ :F(-.ß))) v ö((ß ^ ß) v (-.ß => c))
^A <* :F(-.ß))) V  ( ( ß => ß ) V (-.ß => C))
-.A ^ (ß))) v ö((ß ^ ß) v (-.ß => c))
) v ö ( ( ß ^ ß ) v ( - ß ^ c ) )
) V ( ö ( ß ^ ß ) A Ö ( - ß ^ C ) )
) V ( ( ^ ( ß ) A Ö ( ß ) ) A Ö ( - ß ^ C ) )
) V ( ( ß A Ö ( ß ) ) A Ö ( - ß ^ C ) )
) V((>A-.ß) A0(-.ß=>C))
)V((DA-.ß)A(J-(-.ß)AÖ((7)))
)V((DA-.ß)A(ö(ß)AÖ(C)))
) V ((D A-.ß) A (-.ß A Ö(C)))
) V ( ( D A n 5 ) A ( n 5 A n C ) )
lA<=^
lA<=^
lA<=^
lA<=^
lA<=^
iA^
iA^
iA^
iA^
i ß
i ß
i ß
i ß
i ß
i ß
i ß
i ß
i ß
c) Tento příklad je oproti předchozím složitější nejen tím, že se již nejedná o formuli
výrokové logiky, ale o formuli predikátové logiky, a musíte se tedy srovnat s rozsahem platnosti
kvantifikátorů. Není zde totiž ani explicitně vyznačena priorita a zápis komplikuje
infixová notace predikátů. Proto doplníme několik komentářů.
U konjunkce a disjunkce si můžeme dovolit zápis například A A B A C, aniž bychom
vyznačili rozdělení na binární operace, tj. buď A A (B A C) nebo {A AB) A C. Při
výpočtu normálního tvaru však musíme jedno konkrétní uzávorkování zvolit. V tomto
příkladě jsme předpokládali, že konjunkce je asociativní zleva. Pozor: u implikace na
uzávorkování záleží a musí být proto vždy vyznačeno. Například formule (A =>- B) =>- C
není ekvivalentní formuli A =>- ( ß =>- C), což dobře uvidíte, pokud obě formule znegujete.
4
Ve formuli používáme obecně známé predikáty uspořádání přirozených čísel podle
velikosti a dělitelnosti přirozených čísel. Tyto predikáty obvykle zapisujeme v tzv. infixové
notaci. Kdybychom se chtěli striktně držet definice formulí predikátové logiky, měli
bychom psát >(w,x) místo w > x a \(z,x) místo z \ x.
Při normalizaci formule záměrně ponecháváme zápisy tvaru ->(w > x). Je sice zřejmé,
že bychom místo toho mohli napsat w < x, ale < je jiný predikát než > a definice
funkcí T a Q tuto úpravu neumožňuje. K obecnému, například unárnímu predikátu P
totiž nemusíme mít vždy k dispozici jiný unární predikát Q takový, že ~>P(x) platí právě
tehdy, když platí Q(x).
:F(-.(Va;
= g(Vx
= 3x e
= 3x e
= 3x e
= 3x e
= 3x e
= 3x e
= 3x e
= 3x e
= 3x e
= 3x e
= 3x e
= 3x e
= 3x e
= 3x e
E No- x > 0 =/- 3y, z E No- y \ x A z \ x =>- 3w E No- w>xAz\wAy\ w))
E No- x > 0 =/- 3y, z E No- y \ x A z \ x =>- 3w E No- w > x A z \w Ay \w)
No- Q{x > 0 =/- 3y, z G No- y | x A z | x =>- 3u> G No- w > x A z | w A y | w )
No- ^"(x > 0) A Q (3y, z E N0. y \ x A z \ x ^ 3w E N0. w>xAz\wAy\w)
No- x > 0 A (3y, zG No- y|:rAz|:r=^3w G No- w > : r A z | w A y | w )
No- x > 0 A Vy, z G No- (y |  A z | x =^ 3w G No- w > x Az\w Ay\w)
T(y \x Az\x) A G(3w E No- w > x A z \w Ay \w)
T(y | x) A T(z | x) A Q(3w E NQ. W > X A Z | W A J / | W )
N0. x > 0 A Vy, z G No
N0. x > 0 A Vy, z G No
N0. x > 0 A Vy, z G No
N0. x > 0 A Vy, z G No
N0. x > 0 A Vy, z G No
N0. x > 0 A Vy, z G No
N0. x > 0 A Vy, z G No
N0. x > 0 A Vy, z G No
N0. x > 0 A Vy, z G No
N0. x > 0 A Vy, z G No
x A T(z | x) A G(3w E NQ. w > x A z | w A y | w )
x A z
x A z
x A z
x A z
x A z
x A z
x A z
x A G(3w E No- w > x A z \w Ay \w)
x A \/w E NQ. G(W > X A Z \W Ay \W)
I A V W G N O
I A V W G N O
I A V W G N O
I A V W G N O
I A V W G N O
(?(w > x A z | w) v ö(y I w)
(?(w > x) v (?(.z I w) v G(y | w)
-i(w > x) v (?(.z | w) v ö(y | w)
-i(w > x) v -i(z | w) v ö(y | w)
-i(w > x) V -i(z I w) V -i(y | w)
Příklad 4.
Formalizujte (tj. zapište jako formule výrokové, resp. predikátové logiky) a negujte následující
tvrzení. Pokud se tvrzení týká čísel, vyjádřete vlastnosti pomocí aritmetických
operací. Formule zapisujte v normálním tvaru.
a) Když budu hodný, Ježíšek mi nadělí hezké dárky.
b) Ne každý čaj mi chutná.
c) Rostlina, která u mne přežije rok, je plevel.
d) Když je přes den zataženo a v noci jasno, bude ráno mrznout nebo přijde obleva.
e) Nechť n je sudé přirozené číslo. Potom pro každé přirozené číslo m platí, že když
m je sudé, potom m + n je sudé, a když m je liché, potom m + n je liché.
f) Přirozené číslo p je prvočíslo, jestliže není dělitelné jiným přirozeným číslem kromě
čísla 1 a sebe samého.
g) Když je přirozené číslo a větší než 8, nebo když je dělitelné přirozeným číslem b,
potom a je větší než b a a ˇ b je větší než b.
5
Řešení
V každém příkladě explicitně označíme části textu jako výrokové proměnné, resp.
predikáty a z nich vytvoříme formuli p výrokové, resp. predikátové logiky. Výrokové
proměnné, resp. predikáty budeme volit tak, aby je nebylo možné dále rozložit. Normální
tvar formule i její negace přepíšeme zpět do textové podoby. Na rozdíl od předchozího
příkladu budeme při přepisu do textu výrokové proměnné a predikáty někdy negovat,
aby nebyla textová podoba příliš neohrabaná. K definici atomických proměnných, resp.
predikátů i označení formule p budeme používat symbol =.
Ve formulích predikátové logiky budeme k vyjádření vlastností čísel používat aritmetické
operace a rovnost. Význam demonstrujme na příkladě: pokud ve formuli na
místě predikátu použijeme například výraz x + y = 5, zapisujeme tak nějaký binární
predikát P(x, y), který je splněn právě tehdy, když platí rovnost x + y = 5.
a) Toto je jednoduchý výrok bez kvantifikátorů, vystačíme tedy s výrokovou logikou.
A = budu hodný
B = Ježíšek mi nadělí hezké dárky
(p = A^B
Formule p je již v normálním tvaru, což doložíme výpočtem. Je proto zbytečné ji
přepisovat zpět do textové podoby.
T {A => B)
= F(A) => F{B)
= A^ F{B)
= A^B
Negace:
HA.A =* B))
= Q{A ^ B)
= F(A)Ag(B)
= AAQ(B)
= AA^B
Doslovný přepis negace by byl ,,Budu hodný a Ježíšek mi nenadělí hezké dárky." V češtině
bychom pravděpodobně řekli ,,Budu hodný, ale Ježíšek mi nenadělí hezké dárky," protože
intuitivně cítíme že tato dvě tvrzení jsou v rozporu.
b) V této formuli již se kvantifikátor vyskytuje, vytvoříme tedy formuli predikátové
logiky. Označme T množinu všech čajů (chemické napodobeniny ani navoněné lektvary
tam nepočítáme). Nechť x E T. Uvědomte si, že toto je jiné x, než které se vyskytuje ve
formuli <p. Ve formuli p je vázáno kvantifikátorem.
C(x) = čaj x mi chutná
P = ^x G r. c(x)
Převedení do normálního tvaru:
T{-^x G T. C (x))
= g(Wx G r. c(x))
= 3XET. Q{C{X))
= 3XET. -iC(aľ)
6
V normálním tvaru by tvrzení znělo: ,,Existuje čaj, který mi nechutná."
Negace:
T(-^(-Nx E T. C (x)))
= Q{^x E T. C (x))
= Ť(V'x E T. C (x))
= VXET. T {C {X))
= VXET. C (X)
V textové podobě negace zní: ,,Každý čaj mi chutná."
c) Tento výrok by bylo opět možné zapsat jako jednoduchou výrokovou implikaci.
Ve výroku je však skryta kvantifikace, kterou explicitně vyjádříme přepisem do logiky
predikátové. Označme TZ množinu všech rostlin. Abychom zbránili polemikám o tom, co
rostlina ještě je a co už není, omezme se na rostliny s chlorofylem. Nezelené rostliny normální
člověk nepěstuje. Nechť x E TZ. Toto x je opět různé od x ve formuli <p. Označme
P C K množinu zelených plevelů.
R(x) = rostlina x u mne přežije rok
ip = \/x E TZ. R{x) => x E V
Místo zavedení množiny V a zápisu x E V bychom mohli definovat pro rostliny x E TZ
predikát P(x), který by byl splněn právě tehdy, když by rostlina x byla plevel.
Formule je v normálním tvaru, ověření výpočtem ponecháváme čtenáři.
Negace:
T{-Nx E TZ. R{x) => x E V)
= Q(^x E TZ. R{x) ^XEV)
= 3XETZ. Q{R{X) ^XEV)
= 3XETZ. F{R{X)) A g(x E V)
= 3XETZ. R(X) AQ(XEV)
= 3XETZ. R(X) A^X EV
Do textové podoby je negaci možné přepsat například takto: ,,Existuje rostlina, která u
mne přežije rok a není to plevel."
d) Zde se jedná o složitější formuli výrokové logiky.
Z = přes den je zataženo
J = v noci je jasno
M = ráno bude mrznout
O = přijde obleva
tp = (Z A J) => (M V O)
Formule je v normálním tvaru, ověření výpočtem ponecháváme čtenáři.
Negace:
:F(-.((ZA J) => {My O)))
7
= g((ZAJ)=> (M V O))
= F(ZAJ)AQ(MV0)
= (T(Z) A T(J)) A Q(M V O)
= ( Z A f ( J ) ) A Ö ( M V O )
= (ZA J) AQ(MWO)
= (Z A 3) A(Q(M) AQ(0))
= (ZA J) A (-.M A Q(0))
= (Z A J) A (-.M A -.0)
Do textové podoby bychom negaci p přepsali doslovně takto: ,,Přes den je zataženo a
v noci je jasno a ráno nebude mrznout a nepřijde obleva." Lépe by znělo: ,,Přes den
je zataženo a v noci je jasno a ráno nebude mrznout ani nepřijde obleva." A pokud si
myslíte, že předchozí tvrzení by v zimě mohlo být pravdivé, potom byste asi řekli: ,,Přes
den je zataženo a v noci jasno, ale ráno nebude mrznout ani nepřijde obleva."
e) Zde se zřejmě jedná o formuli predikátové logiky, jejíž přepis by byl velmi snadný,
kdybychom zavedli predikáty pro lichost a sudost přirozeného čísla. My však sudost a
lichost vyjádříme pomocí predikátové logiky, kde jedinými predikáty budou rovnosti aritmetických
výrazů.
Nechť n E No- číslo n je sudé, jestliže 3k E No- n = 2k. Číslo n je liché, jestliže
3k E No- n = 2k + 1. Formuli pak lze zapsat následovně:
tp =(n E No A 3k E N0. n = 2k) ^ V m e N0.
((3/ E N0. m = 21) ^ (3lEN0.m + n = 21)) A
((31 E N0. m = 21 + 1) => (3i EN0.m + n = 2i + 1))
Uvědomte si, že jsme v tomto případě mohli u všech existenciálních kvantifikátorů použít
stejnou proměnnou, například k, l nebo x. Nebo jsme u každého z nich mohli použít
proměnnou jinou. Důvod je ten, že tyto kvantifikované proměnné jsou vázány pouze na
příslušnou rovnost za kvantifikátorem. Mimo ni, mino rozsah platnosti kvantifikátoru, se
jedná o naprosto odlišné proměnné, které jsou shodou okolností jen označené stejným
písmenem. Pokud bychom však potřebovali vyjádřit pomocí rovnosti vztah mezi více
kvantifikovanými proměnnými, museli bychom tyto proměnné označit různě.
Formule je v normálním tvaru. Ověření výpočtem zde uvedeme, protože je z něj
dobře vidět struktura formule a rozsah platnosti jednotlivých kvantifikátorů.
T((n E No A 3k E N0. n = 2k) ^ V m e N0.
((3/ E N0. m = 21) ^ (3lEN0.m + n = 21)) A
((31 E N0. m = 21 + 1) => (3i EN0.m + n = 2i + 1)))
= J=(n E No A 3k E N0. n = 2k) => 3={ým E N0.
((3/ E N0. m = 21) ^ (3lEN0.m + n = 21)) A
((31 E N0. m = 21 + 1) => (3i EN0.m + n = 2i + 1)))
= (T(n E No) A T(3k e N o . n = 2k)) => T^m E N0.
((3/ E N0. m = 21) ^ (3lEN0.m + n = 21)) A
((31 E N0. m = 21 + 1) => (3i EN0.m + n = 2i + 1)))
= (n E No A T(3k E N0. n = 2k)) => 3={ým E N0.
8
((3/ G No. m = 21) => (3/ G N0. m + n = 21)) A
((3/ G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1)))
(n G No A 3fc G N0. :F(ra = 2fc)) => 3={ým G N0.
((3/ G N0. m = 21) => (31 G N0. m + n = 21)) A
((3/ G N0. m = 2/ + 1) => (3i G N0. m + n = 2i + 1)))
(n G No A 3k G N0. n = 2k) ^ T^m G N0.
((3/ G N0. m = 21) => (31 G N0. m + n = 2/)) A
((3/ G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1)))
(n G No A 3fc G N0. n = 2 ž ; ) ^ V m e N0.
:F(((3Z G No. m = 21) ^> (31 eN0. m +n = 21)) A
((3/ G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1)))
(n G No A 3k G N0. n = 2 ž ; ) ^ V m e N0.
T((3l G N0. m = 21) => (31 G N0. m + n = 21)) A
:F((3Z G N0. m = 2/ + 1) => (3i G N0. m + n = 2i + 1))
(n G No A 3k G N0. n = 2 ž ; ) ^ V m e N0.
(:F(3Z G N0. m = 21) => T(3l G N0. m + n = 2/)) A
:F((3Z G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1))
(n G No A 3fc G N0. n = 2 ž ; ) ^ V m e N0.
((3/ G N0. :F(m = 2/)) => :F(3Z G N0. m + n = 2/)) A
:F((3Z G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1))
(n G No A 3k G N0. n = 2fc) => Vm G N0.
((3/ G N0. m = 21) => T(3l G N0. m + n = 21)) A
:F((3Z G N0. m = 2/ + 1) => (3i G N0. m + n = 2i + 1))
(n G No A 3k G N0. n = 2 ž ; ) ^ V m e N0.
((3/ G N0. m = 21) => (3/ G N0. ^(m + n = 2/))) A
:F((3Z G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1))
(n G No A 3fc G N0. n = 2 ž ; ) ^ V m e N0.
((3/ G N0. m = 2/) => (3/ G N0. m + n = 2/)) A
:F((3Z G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1))
(n G No A 3fc G N0. n = 2 ž ; ) ^ V m e N0.
((3/ G N0. m = 2/) => (3/ G N0. m + n = 2/)) A
(:F(3Z G N0. m = 21 + 1) => ^(3i G N0. m + n = 2i + 1))
(n G No A 3fc G N0. n = 2 ž ; ) ^ V m e N0.
((3/ G N0. m = 2/) => (3/ G N0. m + n = 2/)) A
((3/ G N0. T (m = 21 + 1)) => J^(3i G N0. m + n = 2i + 1))
(n G No A 3k G N0. n = 2fc) => Vm G N0.
((3/ G N0. m = 21) => (31 G N0. m + n = 21)) A
((3/ G N0. m = 21 + 1) => ^(3i G N0. m + n = 2i + 1))
(n G No A 3fc G N0. n = 2 ž ; ) ^ V m e N0.
9
((3/ G No. m = 21) => {31 G N0. m + n = 21)) A
((3/ G N0. m = 21 + 1) => (3i G N0. ^(m + n = 2i + 1)))
(n G No A 3fc G N0. n = 2fc) => Vm G N0.
((3/ G N0. m = 21) => {31 G N0. m + n = 2/)) A
((3/ G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1))
Negace:
:F(-"((ra G No A 3fc G N0. n = 2fc) => Vm G N0.
(3/ G N0. m = 21) => {31 G N0. m + n = 2/)) A
(3/ G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1))))
<?((ra G No A 3fc G N0. n = 2fc) ^ V m e N0.
(3/ G N0. m = 21) => {31 G N0. m + n = 2/)) A
(3/ G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1)))
:F(ra G No A 3fc G N0. n = 2fc) A (Vm G N0.
(3/ G N0. m = 21) => {31 G N0. m + n = 2/)) A
(3/ G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1)))
:F(ra G No) A :F(3fc G N0. n = 2fc)) A (Vm G N0.
(3/ G N0. m = 21) => {31 G N0. m + n = 21)) A
(3/ G N0. m = 2/ + 1) => (3i G N0. m + n = 2i + 1)))
n G No A :F(3fc G N0. n = 2k)) A (Vm G N0.
(3/ G N0. m = 21) => {31 G N0. m + n = 2/)) A
(3/ G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1)))
n G No A 3fc G N0. :F(ra = 2fc)) A (Vm G N0.
(3/ G N0. m = 2/) => (3/ G N0. m + n = 2/)) A
(3/ G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1)))
n G No A 3fc G N0. n = 2fc) A (Vm G N0.
(3/ G N0. m = 2/) => (3/ G N0. m + n = 2/)) A
(3/ G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1)))
n G No A 3fc G N0. n = 2fc) A 3m G N0.
(((3/ G N0. m = 2/) => (3/ G N0. m + n = 2/)) A
(3/ G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1)))
n G No A 3fc G N0. n = 2fc) A 3m G N0.
((3/ G N0. m = 2/) => (3/ G N0. m + n = 2/)) V
Q((31 G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1))
n G No A 3fc G N0. n = 2fc) A 3m G N0.
^(3/ G N0. m = 2/) A g(3l G N0. m + n = 21)) V
Q((31 G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1))
n G No A 3k G N0. n = 2k) A 3m G N0.
(3/ G N0. :F(m = 2/)) A g(3l G N0. m + n = 21)) V
10
g((31 G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1))
= ( n e N 0 A 3 f c e N 0 . n = 2fc) A 3m G N0.
((3/ G N0. m = 21) A Q(3l G N0. m + n = 21)) V
((3/ G N0. m = 2/ + 1) => (3i G N0. m + n = 2i + 1))
= (n G No A 3fc G N0. n = 2k) A 3m G N0.
((3/ G N0. m = 21) A (V/ G N0. (m + n = 21))) V
((3/ G N0. m = 2/ + 1) => (3i G N0. m + n = 2i + 1))
= (n G No A 3k G N0. n = 2fc) A 3m G N0.
((3/ G N0. m = 2/) A (V/ G N0. ->(m + n = 2/))) V
((3/ G N0. m = 21 + 1) => (3i G N0. m + n = 2i + 1))
= (n G No A 3k G N0. n = 2k) A 3m G N0.
((3/ G N0. m = 21) A (V/ G N0. ->(m + n = 2/))) V
(T (31 G N0. m = 21 + 1) A (3i G N0. m + n = 2i + 1))
= (n G No A 3k G N0. n = 2fc) A 3m G N0.
((3/ G N0. m = 21) A (V/ G N0. ->(m + n = 2/))) V
((3/ G N0. :F(m = 2/ + 1)) A Q(3i G N0. m + n = 2i + 1))
= (n G No A 3k G N0. n = 2fc) A 3m G N0.
((3/ G N0. m = 2/) A (V/ G N0. ->(m + n = 2/))) V
((3/ G N0. m = 21 + 1) A (3i G N0. m + n = 2i + 1))
= (n G No A 3k G N0. n = 2k) A 3m G N0.
((3/ G N0. m = 21) A (V/ G N0. ->(m + n = 2/))) V
((3/ G N0. m = 21 + 1) A (Vi G N0. (m + n = 2i + 1)))
= (n G No A 3k G N0. n = 2fc) A 3m G N0.
((3/ G N0. m = 21) A (V/ G N0. ->(m + n = 2/))) V
((3/ G N0. m = 2/ + 1) A (Vi G N0. ->(m + n = 2i + 1)))
Pro přepis do textové podoby si uvědomte, jak se znegují podformule pro sudost a lichost:
,,Přirozené číslo n je sudé a existuje přirozené číslo m takové, že m je sudé & m + n není
sudé, nebo m je liché a m + n není liché."
f) Tento příklad je podobný předchozímu. Jedná se vlastně o definici pojmu prvočíslo.
Proto budeme moci formuli chápat tak, že charakterizuje predikát ,,být prvočíslem" v termínech
predikátové logiky. Všimněte si, že v češtině se v definicích používá slovo ,,jestliže"
ve významu ,,tehdy a jen tehdy", ačkoliv v přirozeném jazyce má spíše význam implikace
zprava doleva.
Abychom mohli napsat formuli <p bez relace dělitelnosti, musíme umět vyjádřit
dělitelnost dvou čísel pomocí formule predikátové logiky. Nechť a, b G N. Číslo a dělí
číslo b, jestliže 3c G N. b = ca.
Za zmínku (a povšimnutí) stojí i způsob, jakým vyjádříme, že nějakou vlastnost mají
pouze některá čísla: univerzální kvantifikací vezmeme do úvahy všechna čísla a pomocí
implikace se omezíme pouze na tu skupinu, která nás zajímá.
Nechť n G N.
11
P (n) = přirozené číslo n je prvočíslo
ip = P (n) O (Vm G N. ( m ^ l A m / n )
Převedení do normálního tvaru:
^3k G N. n = km)
J7
(P (n) <$ (Vm G N. ( m ^ l A m ^ ř i ) ^ ->3k G N. n = km))
= J7
(P (n)) O T{ým e N . ( m ^ l A m ^ ( i ) 4 Sk G N. n = km)
P (n
P (n
P (n
P (n
P (n
P (n
P (n
P (n
P (n
=>ˇ T(im G N. ( m ^ l A m ^ ř i ) ^ ->3k G N. n = km)
=>ˇ (Vm G N. J^((m ^ l A m ^ f í ) 4 -i3fc G N. n = fcm))
<^> (Vm G N. J^(m ^ l A m ^ f í ) 4 T {Sk EN. n = km))
& (Vm G N. (.F(TO ^ 1) A .F(TO ^ n)) => .F(-afc G N. n = km))
O (Vm G N. (m ^ 1 A J^(m 7^ n)) => T {Sk EN. n = km))
=>ˇ (Vm G N. ( m ^ l A m ^ ř i ) ^ JF"(--i3fc G N. n = km))
=>ˇ (Vm G N. ( m ^ l A m ^ ř i ) ^ (3fc G N. n = km))
=>ˇ (Vm G N. ( m ^ l A m ^ í i j ^ V k N . (n = km))
=>ˇ (Vm G N. ( m ^ l A m ^ í i j ^ V k N . -n {n = km))
Přepis normálního tvaru do textové podoby by byl shodný s původním tvarem, protože
v normálním tvaru je jinak charakterizována jen nedělitelnost.
Negace této formule je užitečná pouze jako cvičení, fakticky nemá význam negovat
definici.
T{-^{P{ri) O (Vm e N . ( m ^ l A m ^ ( i ) 4 Sk e N . n = km)))
= G(P(n) O (Vm G N. ( f f l ^ l A m ^ ( i ) 4 > Sk e N . n = km))
m ^ l A m ^ í i )
m ^ l A m ^ í i )
(:F(P(ra)) A0(VmeN.
(Q(P(n)) A ^(Vm G N.
(P(n) A (Vm G N. ( m ^ l A m / n )
{Q{P{n)) A ^(Vm G N.
(P(ra) A (3m G N. ((m
{Q{P{n)) A ^(Vm G N.
(P(n) A (3m G N. J^(m
(Q(P(n)) A ^(Vm G N.
(P(n) A (3m G N. {3={m
(Q(P(n)) A ^(Vm G N.
(P(n) A (3m eN. ( m /
(Q(P(n)) A ^(Vm G N.
(P(n) A (3m eN. ( m /
{Q{P{n)) A ^(Vm G N.
(P(n) A (3m EN. {m^
(Q(P(n)) A T^m G N.
(P(ra) A
=>- Sk G N. n = fcm)) V
=>- Sk EN. n = km)
3k G N. n = km)) V
ffl^lAm^íi)^ -i3fc G N. n = km)
^ l A m ^ f í ) 4 -i3fc EN. n = km))) V
ffl^lAm^íi)^ -i3fc G N. n = fcm)
^ l A m ^ í í ) A (^3fc G N. n = km))) V
ffl^lAm^íi)^ -i3fc G N. n = fcm)
Ť^ 1) A 3={m j- n)) A (^3fc EN.n = km))) V
ffl^lAm^íi)^ -i3fc G N. n = fcm)
1 A ^(m ^ n)) A (^3fc G N. n = km))) V
ffl^lAm^íi)^ -i3fc G N. n = fcm)
l A m / n ) A G{Sk E N. n = km))) V
ffl^lAm^íi)^ -i3fc G N. n = km)
l A m / n ) A T{3k EN. n = km))) V
ffl^lAm^íi)^ -i3fc G N. n = fcm)
3m G N. ( m ^ l A m ^ ( i ) A l e N . T {n = km))) V
12
Q {P {n)) A 3={ým G N. ( m ^ l A m / í i ) ^ Sk E N. n
P (n) A (3m E N.
Q (P (n)) A ^(Vm e N . ( m / l A m / u ) ^ Sk E N.
P(ra) A (3m G N.
-iP(n) A .F(VTO G
P(ra) A (3m G N.
-iP(n) A (Vm G N
P(ra) A (3m G N.
-iP(n) A (Vm G N
P(ra) A (3m G N.
-iP(n) A (Vm G N
P(ra) A (3m G N.
-iP(n) A (Vm G N
P(ra) A (3m G N.
-iP(n) A (Vm G N
P(ra) A (3m G N.
-iP(n) A (Vm G N
P(ra) A (3m G N.
-iP(n) A (Vm G N
P(ra) A (3m G N.
-iP(n) A (Vm G N.
m ^ l A m ^ f i ) A ] f c e N . n = km
n
m y^ 1 A m y^ n) A3k E N. n = km
N. ( f f l ^ l A m ^ n ) 4 > -i3fc G N. n
m ^ l A m ^ f i ) A ] f c e N . n = km
T((m ^ l A m / í í ) 4 -i3fc G N. n
m y^ 1 A m y^ n) A3k E N. n = km
T(m ^ l A m / ? í ) 4 T (Sk E N. n
m y 1 Am y n) A3k EN. n = km)) V
T(m ^ 1) A ^ ( m ŕ n)) => T(Sk E N. n
m y 1 Am y n) A3k EN. n = km)) V
m ^ l A T (m ^ n)) => T (Sk E N. n = km)))
m y 1 Am y n) A3k EN. n = km
m / l A m / u ) 4 > J7
(Sk E N. n
m y 1 Am y n) A3k EN. n = km
m / l A m / u ) 4 > Q(3k E N. n =
m y 1 Am y n) A3k EN. n = km
m ^ l A m ^ í i j ^ V k N . Q(n =
m y 1 Am y n) A3k EN. n = km
m ^ l A m ^ í i j ^ V k N . -i(n =
= fcm))
V
= fcm))
V
km))
V
= km)))
V
km)))
km)))
V
= km)))
V
km)))
V
km)))
V
km)))
Slovní přepis negace ^ by mohl znít takto: ,,Nechť n e N . Potom je n prvočíslo a přitom
je dělitelné nějakým číslem různým od sebe sama i čísla 1, nebo n není prvočíslo a není
dělitelné žádným číslem kromě sebe sama a čísla 1." Do
Úvodní větu ,,Nechť n E N." explicitně uvádíme, protože formule <p a tudíž i její
negace obsahuje volnou proměnnou n (proměnná n není kvantifikována). Nemá tedy
smysl hovořit o pravdivosti formule ip jako takové nebo její negace. Má smysl se ptát,
zda formule nebo její negace platí pro nějaké konkrétní n z množiny hodnot, pro něž jsou
definovány predikáty, v nichž se proměnná n vyskytuje. Takovou množinou je například
množina přirozených čísel. Abychom odstranili nejasnosti, explicitněji vymezujeme.
g) Tento slovní zápis ponechává prostor pro pochybnosti. Není úplně zřejmé, jestli je b
volná proměnná, nebo je existenciálne kvantifikovaná. Protože v příslušné části není explicitně
uvedeno ,,existuje 6" ani ,,nějakým 6", budeme b považovat za volnou proměnnou.
Nechť a, b E No.
ip = (a > 8 V 3k E N. a = kb) =>- (a > b A a ˇ b > b)
Formule již je v normálním tvaru, ověření výpočtem ponecháváme čtenáři.
Negace:
:F(-.((a> 8 V3fcG N. a ˇ
= Q((a > 8 V3fc G N. a
= J=(a > 8 V 3k E N. a --
kb) =>- (a> b Aa-b> b)))
-- kb) =>- (a> b Aa-b> b))
kb) AQ(a > b A a ˇ b > b)
13
= {T{a > 8) V T{3k G N. a = kb)) A (a > b A a ˇ b > b)
= (a > 8 V T{3k G N. a = kb)) A Q {a > b A a ˇ b > b)
= (a > 8 V 3k G N. T {a = kb)) A Q {a > b A a ˇ b > b)
= (a > 8 V 3k G N. a = kb) A Q (a > b A a ˇ b > b)
= (a > 8 V 3k G N. a = kb) A (0(a > b) V (?(a ˇ b > b))
= (a > 8 V 3k G N. a = kb) A (-.a > 6 V (?(a ˇ 6 > 6))
= (a > 8 V 3fc G N. a = fcô) A (-.a > 6 V ^a ˇ 6 > 6)
V textové podobě můžeme nagaci zapsat například takto: ,,Současně platí následující dvě
tvrzení. (1) Číslo a je větší než 8, nebo číslo b dělí číslo a. (2) Číslo a není větší než číslo b,
nebo a ˇ b není větší než 6."
Příklad 5.
V následujících příkladech máte za úkol znegovat definiční podmínky různých pojmů.
Definice pojmů zapište jako formule výrokové, resp. predikátové logiky a znegujte je.
a) Nechť n je přirozené číslo. Co znamená, že n není liché?
b) Nechť R je relace. Co znamená, že R není antisymetrická?
c) Nechť / C A x B je parciální funkce. Co znamená, že / není minimální prvek
uspořádané množiny (T, C), kde T je množina všech parciálních funkcí z A do B?
d) Nechť / C A x B je parciální funkce. Co znamená, že / není nejmenší prvek uspořádané
množiny (T, C), kde T je množina všech parciálních funkcí z A do B?
e) Řekneme, že přirozené číslo m je šťastné a veselé, jestliže pro žádné přirozené číslo n
větší než m neplatí, že m dělí n a m + n je liché. Co znamená, že číslo m není šťastné a
veselé?
f) Řekneme, že přirozené číslo k je odvážné, jestliže existují přirozená čísla a, b taková,
že a i b je různé od čísla 1 a zároveň k2
= o?b2
. Co znamená, že číslo k není odvážné?
g) Nechť i ž C M x M j e binární relace na množině M. Řekneme, že relace R je přitažlivá,
jestliže pro každé x,y G M platí: pokud (x,y) G R, potom existuje z E M takové, že
(x, z) E R a (y, z) E R. Co znamená, že relace R C M x M není přitažlivá?
h) Nechť / : M --ˇ M je funkce. Řekneme, že / má trojúhelník, jestliže pro každé x E
E M platí f (x) 7^ x a existují navzájem různá xi,X2,xs E M taková, že f(x\) = X2,
f{x2) = X3 a f(xs) = x\. Co znamená, že funkce / : M --ˇ M nemá trojúhelník?
Příklad 6.
Mějme výrokovou formuli <p = (A =^> B) =^> (B =^> A).
a) Najděte všechny valuace v, pro něž Sv{^) = true. Kolik jich je?
b) Najděte všechny valuace v, pro něž Sv{^) = false. Kolik jich je?
Řešení
Protože pro danou valuaci každá formule výrokové logiky buď platí, nebo neplatí,
budou valuace, pro něž je formule ip splněna, a valuace, pro něž splněna není, tvořit rozklad
na množině všech valuací. Přitom množina všech valuací je {true, false} (množina
všech funkcí z At do {true, false}). Protože množina At je nekonečná, je jistě nekonečná
i množina všech valuací.
Ve formuli ip se však vyskytují pouze dvě výrokové proměnné. Má proto smysl rozdělit
množinu všech valuací podle toho, jaké hodnoty přiřazují výrokovým proměnným A a B.
Rozklad má 4 třídy, každá z nich je nekonečná.
14
false A v (B) = false}
false A i^(B) = true}
true A i^(B) = false}
true A i^(B) = true}
a) Sv{ip) = true platí pro všechny valuace v G AQQ U A\Q U An, což ověříme výpočty.
Valuací je tedy nekonečně mnoho.
Nechť v G AQQ.
00 = {u::At- -> {true, false} v(A)
01 = {v::At- -> {true, false} KA)
10 = {v::At- -> {true, false} "(A)
11 = {v::At- -> {true, false} "(A)
<S,,(A) = false O) z definice v
S,,(5) = false (Ü) z definice v
S,,(A => B) = true (iii) z (i) a (ii)
SV{B => A) = true (iv) z (ii) a (i)
SV((A =>B)^(B => A)) = true (v) z (iii) a (iv)
Nechť v G A\Q.
S,,(A) = true (i) z definice v
SV{B) = false (Ü) z definice v
SV{A => B) = false (iii) z (i) a (ii)
SV{B => A) = true (iv) z (ii) a (i)
SV((A =>B)^(B => A)) = true (v) z (iii) a (iv)
Nechť v G An.
^(A) = true (i) z definice v
^ ( S ) = true (Ü) z definice v
^ ( A =>  ) = true (iii) z (i) a (ii)
SV{B => A) = true (iv) z (ii) a (i)
SV{{A =>B)^(B => A)) = true (v) z (iii) a (iv)
b) Sv{ip) = false platí pro všechny valuace v G AQ\, COŽ ověříme výpočtem. Valuací je
tedy nekonečně mnoho.
Nechť v G AQ\.
SV{A) = false O) z definice v
SV{B) = true (u) z definice v
SV{A => B) = true (iii) z (i) a (ii)
SV{B => A) = false (iv) z (ii) a (i)
SV{{A =>B)^(B => A)) = false (v) z (iii) a (iv)
15
Příklad 7.
Rozhodněte, zda následující formule výrokové logiky jsou splnitelné. Pokud ano, nalezněte
valuaci, která to dosvědčuje.
a) (((A => B) A (B => C)) AA)A^C
b) (D <& (-. V >)) A -.((> A  ) ^ i )
c) (-.-. AA)^ ((-IA => 5 ) A (-.5 => A))
Řešení
Jak víte z přednášky, rozhodnout o splnitelnosti dané formule výrokové logiky je
výpočetně velmi náročné. V podstatě to znamená vyzkoušet všechna možná ohodnocení
výrokových proměnných. Pozor: ne všechny valuace. Valuaci je nekonečně mnoho.
Protože však každá formule obsahuje pouze konečně mnoho výrokových proměnných, je
možné množinu všech valuaci rozložit na konečně mnoho tříd podobně jako v předchozím
příkladě a uvažovat pak celou třídu rozkladu valuaci najednou.
Pokud rozhodujeme o splnitelnosti formulí ručně, je výhodné postupovat shora po
struktuře formule a ptát se, co musí platit pro jednotlivé podformule, aby byla formule
splněna. Tak budeme postupovat i my a postupně budeme klást na valuaci v požadavky,
kterým musí vyhovovat, aby byla formule splněna. Můžete samozřejmě zvolit i
jiný postup, například mechanický výpočet Sv(<p) pro valuace z jednotlivých tříd rozk­
ladu.
a) Aby byla formule splněna, musí být splněny obě podformule, které jsou v konjunkci.
Zejména tedy musí platit v(C) = false. Zbylá podformule je opět konjunkce, z níž plyne,
že musí platit v (A) = true. Zbylá podformule je opět konjunkce, musí být tedy současně
splněny obě implikace A =>- B i B =>- C. Aby bylo splněno A =>- B, musí platit v(B) =
= true, protože v (A) = true. Aby bylo splněno B => C, musí platit v(B) = false, protože
v(C) = false. Žádná valuace nemůže současně splňovat v(B) = true a v(B) = false,
formule není splnitelná.
b) Formule je konjunkcí dvou podformulí. Aby byla splněna levá podformule, stačí,
aby platilo v(D) = true. Na hodnotě v(E) potom nezáleží. Aby byla splněna pravá
podformule, nesmí být splněna implikace uvnitř negace. Toho lze docílit pouze tak, že
bude platit v (A) = false a D A E se vyhodnotí na true, což nastane, pokud bude platit
v{E) = true.
Formule je splnitelná. Je splněna libovolnou valuaci v, která splňuje v (A) = false
a v(D) = v(E) = true. Pozor: Není možné napsat v = {(A,false), (B, true), (C, true)}.
Každá valuace přiřazuje pravdivostní hodnoty všem výrokovým proměnným. I těm, které
se nevyskytují ve formuli, se kterou právě pracujeme.
c) Formule klade dvě podformule do logické ekvivalence. Aby byla splněna, musí obě
podformule buď současně platit, nebo současně neplatit. Zkusme nejprve zjistit, zda mohou
obě podformule současně platit. Levá podformule je konjunkcí. Aby byla splněna,
musí platit v (A) = v(B) = true. Snadno se nyní ukáže, že za těchto podmínek je splněna
i pravá podformule. Pro zopakování zde uvedeme výpočet, který to ověřuje:
S v (A) = true (i) z definice v
SV{-^A) = false (ii) z (i)
SV(B) = true (iii) z definice v
16
SV{-^A => B) = true (iv) z (ii) a (iii)
<Sl/(--i-S) = false (v) z (iii)
Sv{-iB => A) = true (vi) z (v) a (i)
SV((-^A => 5 ) A (-.5 => A)) = true (vii) z (iv) a (vi)
Formule je splnitelná. Je splněna libovolnou valuací v, která splňuje v (A) = v(B) =
= true.
Kdybychom zjistili, že obě podformule nemohou být současně splněny, museli bychom
vyzkoušet, zda může nastat, že nebude splněna ani jedna.
Příklad 8.
Označme V množinu všech valuací. Uvažujme uspořádanou množinu (W,C), kde li =
= {f C At x {true, false} | / je parciální funkce} (jedná se opět o množinu parciálních
funkcí uspořádaných množinovou inkluzí).
a) Dokažte, že platí V C W .
b) Charakterizujte valuace v pojmech uspořádané množiny (li, C) a dokažte, že je podaná
charakterizace správná.
c) V uspořádané množině (li, C) určete všechny maximální dolní závory množiny {v E
G V | SV(B A (C =>- A)) = true}. Jsou to valuace?
d) Co musí splňovat výroková formule tp, aby v uspořádané množině (li, C) měla množina
{/ G li I 3Í/ G V./ C v A Sv(r
tp) = true} infimum? Bude infimum valuace?
Řešení
a) Ano, je to tak zřejmé, jak to vypadá. Každá valuace je totální funkce z At do
{true, false}, je to tedy i parciální funkce z At do {true, false} a proto patří do množiny li.
b) Opět se jedná o analogii toho, co jste už řešili. Valuace jsou z definice právě totální
funkce (tj. každá valuace je totální funkce a každá totální funkce je valuace) z At
do {true, false}. Dokážeme, že totální funkce jsou právě maximální prvky uspořádané
množiny (li, C). Celkem tedy dostaneme, že valuace jsou právě maximální prvky (li, C).
Nechť / : At --ˇ {true, false} je totální funkce. Sporem předpokládejme, že to není
maximální prvek (li,C). Tedy existuje g E li taková, že / C g. Proto musí existovat
A E At takové, že g (A) je definováno a f (A) definováno není. To je spor s tím, že / je
totální funkce.
Nechť f E li je maximální prvek (W,C). Sporem předpokládejme, že není totální.
Tedy existuje A E At, pro které není / definována. Položme g = f U {(A, true)}. Jistě
platí gEliafCg, fy^g. To je ovšem ve sporu s předpokladem, že / je maximální
prvek (li,cy
c) Nejprve popíšeme množinu, značme ji třeba M, jejíž maximální dolní závory určujeme.
Množina M je množina všech valuací, pro něž je formule B A (C =>ˇ A) splněna.
Podobně jako v jednom z předchozích příkladů musíme určit všechny valuace, pro něž je
formule splněna. Platí
M = Ai U A2 U A3
Ai = {u E V I u(A) = false A u(B) = true A u (C) = false}
A2 = {v E V I u(A) = true A u(B) = true A u (C) = false}
A3 = {v E V I u(A) = true A u(B) = true A u (C) = true}
17
Dolní závorou množiny M je každá parciální funkce / : At --ˇ {true, false}, taková,
že pro libovolné v E M platí / C v. Aby to mohlo být splněno, nesmí být funkce /
definována pro A a C. Zároveň nesmí být definována ani pro žádné jiné D E At, D ^ B.
Pro každé D E At, D^A, D^B,D^C totiž jistě existují v\,V2 E M takové, že
v\(D) = true a U2{D) = false. Pokud by potom funkce / byla pro D definovaná, platilo
by / 2 u
i nebo / $Z u2 a funkce / by proto nebyla dolní závorou M.
Celkem jsme tedy dostali, že dolní závora množiny M může být definována pouze
pro B a pokud je, musí navíc platit f(B) = true. Existují proto pouze dvě dolní závory
množiny M: f\ = 0 a f2 = {(-S, true)}. Maximální horní závorou (a dokonce infimem, tj.
největší dolní závorou) je pouze funkce J2 a jistě to není valuace.
d) Věřím, že jste se nenechali zmást složitostí zadání a uvědomili jste si, jak je tento
příklad triviální. Formule může být zcela libovolná. Infimum dané množiny, značme ji
třeba N, vždy existuje a je to 0. Pro libovolnou valuaci u E V, bez ohledu na to, zda
je pro ni nějaká formule spině či nikoliv, totiž platí 0 C v. Proto 0 E N. Protože 0 je
nejmenší prvek (U, C), je to infimum N. A zcela jistě to není valuace.
Příklad 9.
Nechť pro i E N je A{ E At atomická propozice. Pro všechna n E No definujme formule
fn takto:
* ipo = true
* fn+l =fn A 4
(Tedy například ^3 = ((true A Ai) A A2) A A3, přičemž na uzávorkování zřejmě nezáleží.)
a) Pro každé n E N nalezněte valuaci vn takovou, že
n , \ _ í true pro i < n
^  ^ - 1 false jinak
b) Nalezněte valuaci ß takovou, aby pro všechna n E No platilo S^{ipn) = false.
c) Nalezněte valuaci rj takovou, aby pro všechna n E No platilo S^ipn) = true.
Řešení
Jak jste si pravděpodobně všimli, zadání není formálně v pořádku, protože true se
nemůže ve formuli výrokové logiky vyskytovat. Abychom zachovali zamýšlený význam,
a zadání přitom bylo korektní, musíme true nahradit libovolnou tautologií, například
B\/-iB, kde B ^ Ai pro všechna i E N. V dalším tedy budeme předpokládat, že základní
krok induktivní definice má tvar
Lpo = By^B
a) Pro každé n E No požadujme, aby pro valuaci vn platilo
VniAi)
f true pokud i < n
\ false jinak
Indukcí vzhledem k n dokážeme, že potom tyto valuace splňují požadavky ze zadání.
Základní krok: n = 0. Protože Sv(<po) = true platí pro každou valuaci v, platí to
zejména pro valuaci UQ.
18
Indukční krok.Protože pro un+i platí vn+i(An+i) = true, platí i SVn+1{An+\) = true.
Protože un+i(Ai) = un(Ai) = true pro všechna i E No, i < n a z indukčního předpokladu
platí Svn(<ßn) = true, platí i SVn+1(<pn) = true. Celkem dostáváme SUn+1(<^n+i) =
= SVn+1{ipn A An+i) = true, což jsme měli v indukčním kroku dokázat.
b) Hledaná valuace ß neexistuje, protože Sv('^o) = true pro libovolnou valuaci v.
c) Nechť pro valuaci n platí rj(Ai) = true pro všechna i e N. Indukcí vzhledem k n
dokážeme, že potom je to hledaná valuace.
Základní krok: n = 0. Protože Lpo je tautologie, jistě platí ^(^o) = true.
Indukční krok. Protože pro n platí n(An+i) = true, platí i Sv(An+i) = true. Z indukčního
předpokladu dále platí Sv{'^n) = true, takže celkem dostáváme Sv(<^n+i) =
= Sr)(<pn A An+i) = true, což jsme měli v indukčním kroku dokázat.
19