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 No-
b)  Určete symetrický uzávěr relace {(x,y) \ xy = 0} C No x No-
c)  Určete tranzitivní uzávěr relace {(x,y) \ xy = 0} C No x No-
d)  Určete reflexivní, symetrický a tranzitivní uzávěr relace {(x,y) \ xy = 0} C No x No-
e)  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} CMxR, 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 Exf, 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(rtp) 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)
1y D) 4n(DA	(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,(5Anfl)			= false	(v)	z (iii) a (iv)
SMA=> (BA-	■B))		= true	(vi)	z (ii) a (v)
SM^A)			= true	(vii)	z(ii)
^((ni^^Anß))	=^ -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 zne-gová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>xAz|wAy|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 VD)4 -.(£> A (A => B)))) = Q((C VD)^ -.(£> 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 ^ ß)))
(CVD)AÖ(n(DA(A=>5)))
(CVD)AF(DA(A^B))
(CVD)A (:F(£>) A :F(A => ß))
(CVfl)A(DAf(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 (-.ß =
=  O^(-C) A ö(-(-A ^ -nß))) V £((ß ^ ß) V ("
C))))
C))) >C))
iß => C))
g{c) a s h-, 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((DAn5)A(n5AnC))
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. in-fixové 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>xAz|wAy|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>:rAz|wAy|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>xAz|wAj/|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>xAz|wAy|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)
iAVwgNo iAVwgNo iAVwgNo iAVwgNo iAVwgNo
(?(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)) = T'(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 PCK 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) = (ZAf(J))AÖ(MVO) = (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) ^Vme 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) ^Vme 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 eNo.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ž;)^Vme 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ž;)^Vme 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ž;)^Vme 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ž;)^Vme 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ž;)^Vme 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ž;)^Vme 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ž;)^Vme 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ž;)^Vme 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ž;)^Vme 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) ^Vme 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))
= (neN0A3fceN0.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^lAm/n)
Převedení do normálního tvaru:
^3k G N. n = km)
J7 (P (n) <$ (Vm G N. (m^lAm^ři)^ ->3k G N. n = km)) = J7 (P (n)) O T{ým eN.(m^lAm^(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^lAm^ři)^ ->3k G N. n = km)
«=>• (Vm G N. J^((m ^lAm^fí)4 -i3fc G N. n = fcm))
<^> (Vm G N. J^(m ^lAm^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^lAm^ři)^ JF"(—i3fc G N. n = km))
«=>• (Vm G N. (m^lAm^ři)^ £(3fc G N. n = km))
«=>• (Vm G N. (m^lAm^íij^VkN. £(n = km))
«=>• (Vm G N. (m^lAm^íij^VkN. -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 eN.(m^lAm^(i)4 Sk eN.n= km))) = G(P(n) O (Vm G N. (ffl^lAm^(i)4> Sk eN.n = km))
m^lAm^íi) m^lAm^íi)
(:F(P(ra)) A0(VmeN.
(Q(P(n)) A ^(Vm G N.
(P(n) A £(Vm G N. (m^lAm/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) ^lAm^fí)4 -i3fc EN. n = km))) V ffl^lAm^íi)^ -i3fc G N. n = fcm) ^lAm^íí)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) lAm/n)A G{Sk E N. n = km))) V ffl^lAm^íi)^ -i3fc G N. n = km) lAm/n)A T{3k eN. n = km))) V ffl^lAm^íi)^ -i3fc G N. n = fcm)
3m G N. (m^lAm^(i)AleN. T {n = km))) V
12
Q {P {n)) A 3={ým G N. (m^lAm/íi)^ Sk E N. n
P (n) A (3m E N.
Q (P (n)) A ^(Vm eN.(m/lAm/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^lAm^fi)A]fceN. n = km
n
m y^ 1 A m y^ n) A3k E N. n = km N. (ffl^lAm^n)4> -i3fc G N. n m^lAm^fi)A]fceN. n = km
T((m ^lAm/íí)4 -i3fc G N. n m y^ 1 A m y^ n) A3k E N. n = km
T(m ^lAm/?í)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^lA T (m ^ n)) => T (Sk E N. n = km)))
m y£ 1 Am y£ n) A3k EN. n = km
m/lAm/u)4> J7 (Sk E N. n m y£ 1 Am y£ n) A3k EN. n = km
m/lAm/u)4> Q(3k E N. n = m y£ 1 Am y£ n) A3k EN. n = km
m^lAm^íij^VkN. Q (n = m y£ 1 Am y£ n) A3k EN. n = km
m^lAm^íij^VkN. -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ť neN. 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žCMxMje 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 rozkladu.
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í VCW.
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(rtp) = 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 ui 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 f n takto:
•   ipo = true
•   fn+l =fn A4
(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