Predikátová logika - cvičení
V celém textu budeme používat následující konvence: Nosič realizace Ai budeme značit M (podobně například nosič realizace AÍ2 bude M2 apod.). Symbol = budeme používat nejen jako formální symbol z jazyka s rovností, ale i jako metasymbol označující stejná individua (význam by měl být jasný z kontextu). Dále budeme používat metasymbol který bude zastupovat frázi "právě tehdy, když".
1    Základy predikátové logiky
1.1 Příklad:
Mějme jazyk C = {■} s rovností, kde ■ je binární funkční symbol a realizaci Ai jazyka C. Dejte příklad uzavřené formule ip predikátového počtu jazyka C takové, že Ai \= ip právě tehdy, když
1. (M,-M) je pologrupa
2. (M, -m) je monoid
3. (M,-M) je grupa
Řešení:
1. ip = \/x\/y\/z((x ■ y) ■ z = x ■ (y ■ z))
2. Označme ipp formuli z 1. Pak ip = ipp A 3x\/y(x - y = y/\y-x = y)
3. ip = ipp A 3x(\/y(x - y = y/\y-x = y)/\ \/z3u(z ■ u = x A u ■ z = x))
1.2 Příklad:
Rozhodněte, zda platí následující tvrzení: Mějme nějaký jazyk C, realizaci Ai jazyka C a formuli ip predikátového počtu jazyka C. Pak
M. \= (p právě tehdy, když M. \/= -xp
Řešení:
Implikace "zleva doprava" platí. Dokážeme tedy následující tvrzení: Tvrzení:   Jestliže M. \= (p, pak M. y= -xp.
1
Důkaz: Předpokládejme, že Ai \= p. Pak (z definice) pro každé ohodnocení e platí Ai \= p[e\. Nosič Ai je neprázdný (z definice realizace) a tedy existuje alespoň jedno ohodnocení e takové, že Ai \= p[e\. Pak ale Ai y= -"f[e\ a tedy M ^= -<ip.
Implikace "zprava doleva" neplatí. Dokážeme tedy:
Tvrzení: Existují jazyk £, realizace Ai jazyka C a formule p predikátového počtu jazyka C takové, že Ai zároveň Ai ^= —np.
Důkaz: Položme C = {P} kde P je unární predikátový symbol. Realizaci Ai definujme následovně: nosič M = {a, b} a Pm = {a} (Pm Je unární relace). Konečně položme p = P (x).
Nyní nechť e je ohodnocení takové, že e{x) = a. Pak Ai \= P{x)\e\, protože e{x) = a G Pm a tedy Ai y= -iP(x)[e]. Z toho plyne, že Ai y= ~^P(x).
Dále nechť e je ohodnocení takové, že e{x) = b. Pak Ai y= P{x)\e\ a tedy Ai y= P{x).
Celkem tedy Ai y= ->P(x) a zároveň Ai y= P(x), což bylo dokázat. 1.3 Příklad:
Dokažte, že platí následující tvrzení: Mějme jazyk C, realizaci Ai jazyka C a uzavřenou formuli p predikátového počtu jazyka C. Pak
Ai \= p právě tehdy, když Ai \/= -xp
Řešení:
Nejprve dokážeme následující tvrzení. Tvrzení:
1. Je-li í term jazyka C a e±, e2 jsou ohodnocení taková, že e±(x) = e^ix) platí pro každou proměnnou x vyskytující se v í, pak í[ei] = t[e^.
2. Je-li p formule predikátového počtu jazyka C, pak pro libovolná ohodnocení ei, e2 taková, že ei(x) = e^íx) pro každou proměnnou x, která je volná ve p, platí Ai \= p[e{\ právě tehdy, když Ai \= <p[e2\-
Důkaz:
1. Tvrzení dokážeme metaindukcí vzhledem k délce vytvořující posloupnosti pro í (tj. strukturální indukcí).
2
• Je-li t = x proměnná, pak
t[ei] = x[ei] = ei(x) = e2(x) = x[e2] = t[e2]
• Je-li t = /(íi,... ,tn) kde / je n-ární funkční symbol jazyka C a ti,...,tn jsou termy, pak
*[el] =        • • • ,tn)[ei] = /M(íl[ei], • • • ,tn[ei]) = /mOiN], • • • ,ín[e2]) = f(t1,.. .,tn)[e2] = t[e2]
kde druhá rovnost plyne z indukčního předpokladu.
2. Tvrzení dokážeme metaindukcí vzhledem k délce vytvořující posloupnosti pro ip.
• Je-li ip = P(ti,..., tn) kde P je n-ární predikátový symbol a ti,...,tn jsou termy, pak
A^h*]   ^   (íl[ei],...,ín[ei]) E PM ^   0l[e2],...,tn[e2j) e PM
kde druhá ekvivalence plyne z 1. a z toho, že ve ip jsou všechny proměnné volné.
• Je-li C jazyk s rovností a ip = t± = t2 kde ti,t2 jsou termy, pak podobně jako v předchozím bodě máme
M\=(p[e{\ ^ íi[ei] = í2[ei] ^ íl[e2] = í2[e2] ^   MH </?[e2]
• Je-li </? = —<i(;, pak
X |= </?[ei]   <=>   X ^ V[el] ^   X ^ ^[e2]
kde druhá ekvivalence plyne z indukčního předpokladu a z toho, že libovolná proměnná je volná v ip tehdy a jen tehdy, když je volná ve ip.
• Je-li ip = ipi —> ip2l pak
M \= ip[ei] <=> buď M \= ip2[ei] nebo M ^= ^i[ei] <=> buď M \= ip2[e2] nebo M ^= ipi[e2] ^   M\= <p[e2]
kde druhá ekvivalence plyne z indukčního předpokladu a z toho, že libovolná proměnná je volná v ipi nebo v ip2 tehdy a jen tehdy, když je volná ve ip.
3
• Je-li ip = yytp, pak
Ai \= <p[ei] <=> pro každé a e M platí Ai \= ijj[ei(y/a)] <=> pro každé a G M platí Ai \= ip[e2(y/a)] <=>   M \= <p[e2]
kde druhou ekvivalenci lze zdůvodnit takto: Z definice plyne, že pokud je libovolná proměnná x volná v ip, pak buď x]ey nebo a; je volná ve ip. Z toho plyne, že pro libovolnou proměnnou x, která je volná v ip a pro libovolné a E M platí, že ei(y/a)(x) = e2(y/a)(x). Požadovaná ekvivalence potom plyne z indukčního přepokladu.
Nyní dokážeme tvrzení ze zadání příkladu.
Důkaz:   =>: Tento směr byl v obecnější podobě dokázán v Příkladu 1.2. <=: Předpokládejme, že Ai y= <p. Potom existuje ohodnocení e takové, že Ai  ^= ip[e]. Protože žádná proměnná není volná ve ip, dostaneme z předchozího tvrzení, že Ai ^= <p[ef] a tedy Ai \= —np[e'] pro libovolné ohodnocení e'. Z definice nyní plyne, že Ai \= ^p>.
1.4 Příklad:
Mějme jazyk C = {<} s rovností, kde < je binární predikátový symbol. Uvažme tři realizace A/", Z, Q jazyka C s nosiči N, Z, Q (množiny přirozených, celých a racionálních čísel), které interpretují symbol < jako standardní ostré uspořádání na příslušné množině čísel. Dejte příklad uzavřené formule ip predikátového počtu jazyka C takové, že
1. Af\=<p,Z)£<p,Q)£<p
2. Af)£<p,Z \=<p,Q)£<p
3. Af)£<p,Z }£<p,Q\=<p
Řešení:
1. ip = 3x\/y(x = y y x < y)
2. ip = \/x3y(y < x A Vz(z <y\/x<z\/z = y\/z = x))
3. ip = \/x\/y(x < y —> 3z(x < z A z < y)) 1
1také lze použít formuli -iipi A ^ip2 kde tpi je formule z 1. a ip2 je formule z 2.
4
Úlohy:
Mějme jazyk C = {■} s rovností, kde ■ je binárni funkční symbol. Uvažme tři realizace Z, Q, 7Z s nosiči Z, Q, M (množiny celých, racionálních a reálnych čísel), které intepretují symbol ■ jako standardní násobení čísel. Dejte příklad uzavřené formule ip predikátového počtu jazyka C takové, že
f. zy= ip,Q\= ip
1.5 Příklad:
Nechť ip je formule predikátového počtu jazyka C taková, že x je jediná volná proměnná ve ip. Rozhodněte, zda pro libovolnou realizaci Ai jazyka C a libovolnou proměnnou y substituovatelnou za x ve ip platí Ai \= p> —> ip(x/y).
Řešení:
Odpověď: Tvrzení neplatí! Zdůvodnění: Nechť C = {P} kde P je unární predikátový symbol. Definujme realizaci Ai takto:
• M = {a,b}
• Pm = {a}
Nyní uvažme ohodnocení e takové, že e(x) = a a e(y) = b a formuli ip = P(x). Zřejmě M. \/= {P{x) —> P(x)(x/y))[e], protože e{x) = a G Pm a e{y) =b(£ PM.
Poznámka:   M. \= <p —> By(p(x/y) platí pro libovolnou realizaci jazyka C.
2 Teorie 2.1 Příklad:
Mějme jazyk C = {S} s rovností, kde S je unární funkční symbol. Dejte příklad splnitelné konečné teorie T s jazykem C takové, že všechny její modely mají nekonečný nosič.
Řešení:
Uvažme T = \yx^y(S(x) = S(y) —> x = y),3yVx^(S(x) = y)}.
Nejprve ukážeme, že teorie T nemá konečný model. Nechť Ai je model teorie T. Potom S m Je injektivní funkce definovaná na M, která není surjek-tivní. Taková funkce ovšem nemůže existovat na konečném souboru, a proto M musí být nekonečný soubor.
Nyní ukážeme, že T je splnitelná. Definujme realizaci Ai jazyka C takto:
5
• M = No (přirozená čísla s nulou)
• SmÍ™) = n + 1 pro n G No
Je zřejmé, že Ai \= T.
2.2 Příklad:
Nechť (p = yx^(S(x) = x) a nechť T je teorie z Příkladu 2.1. Rozhodněte, zda platí T \= ip.
Řešení:
Odpověď: Neplatí! Zdůvodnění: Definujme realizaci Ai jazyka C takto:
• M = N0
• SM(0) = 0 a S m (i) = i + 1 pro i > 1
Realizace Ai je zřejmě modelem T a zároveň Ai ^= (p.
2.3 Příklad:
Je teorie T z Příkladu 2.2 bezesporná? Je T úplná? Řešení:
Z věty o korektnosti plyne, že každá splnitelná teorie je bezesporná. Opravdu, ve sporné teorii jsou dokazatelné i formule tvaru ip A —up, což znamená, že formule tvaru ipA^ip jsou sémantickým důsledkem sporné teorie (a proto sporná teorie nemůže mít model). Z toho plyne, že T je bezesporná.
Teorie T není úplná. Uvažme formuli ip = Vx—i(S(x) = x) z Příkladu 2.2. Ukázali jsme, že T ^= ip. Na druhou stranu —up = 3x(S(x) = x) a model teorie T z Příkladu 2.1 ukazují, že T ^= —up. Z věty of korektnosti plyne, že T \f ip a T \f —op a tedy, že T není úplná teorie.
3   Kanonická struktura
Pro celou sekci 3 fixujme jazyk C = {P, 0,/} kde P je unární predikátový symbol, 0 je nulární funkční symbol a / je unární funkční symbol.
3.1 Příklad:
Popište kanonickou strukturu teorie T\ = {P(0)} s jazykem C.
6
Řešení:
Kanonická struktura teorie T\ je realizace Ai\ jazyka C taková, že
• Mi = {/l(0) | i > 0} (kde /°(0) = 0)
• /m1(/1(0))=/(/1(0)) = /1+1(0)
• oMl = o
• PMl = {0}
Jediná věc, která není zřejmá z definice kanonické struktury je Pm± = {0}-Musíme ukázat, že T h P(0), a že T \f P(/1 (0)) pro i > 1.
• Zřejmě T h P(0).
• Nechť i > 1. Stačí ukázat, že T ^= P(/l(0)). Požadovaný výsledek pak plyne z věty o korektnosti. Nechť Ai je realizace jazyka £ definovaná následovně:
- M = {a,b}
- f m {a) = b a /m (b) = b
- 0M = a
- Pm = {a}
Zřejmě A4 \= T, protože a G Pm, a zřejmě také M. y= P(/l(0)), protože ľM{a) = b£PM. Celkem tedy T ^ P(/l(0)).
3.2 Příklad:
Popište kanonickou strukturu teorie T2 = {P(x)} s jazykem C. Řešení:
Kanonická struktura M.2 teorie T2 se liší od struktury M.\ z Příkladu 3.1 pouze v interpretaci predikátového symbolu P. Dokážeme, že Pm2 = {/l(0) I i > 0}.
Dle definice kanonické struktury musíme ukázat, že T h P(/l(0)) pro i > 0. Důkaz může vypadat takto:
T h P (x) P (x) e T
T h VxP(x) GEN
T h Va;P(a;) -> P(a;)(a;//l(0)) P4
T h P{x/p{Q)) MP
3.3 Příklad:
Popište kanonickou strukturu teorie t3 = {3xP(x)} s jazykem £.
7
Řešení:
Kanonická struktura A4% teorie T3 se liší od struktur M.\ a M.2 z předchozích příkladů pouze v interpretaci predikátového symbolu P. Dokážeme, že Pm3 = 0.
Ukážeme, že T y= P(/l(0)) pro i > 0. Požadovaný výsledek pak plyne z věty o korektnosti. Nechť Ai je realizace jazyka £ definovaná následovně:
• M = {a,b}
• f m {a) = a a /m(č>) = b
• 0m = b
• Pm = {a}
Zřejmě M. \= T, protože a G Pm, a zřejmě také M. y= P(/l(0)), protože flM(0M) =bČPM- Celkem tedy T ^ P(/l(0)).
Poznámka:   Všimněte si, že kanonická struktura A4% není modelem T3.
4   Existence teorií 4.1 Příklad:
Nechť T je konečná teorie s jazykem C. Dokažte, že existuje konečná teorie T' s jazykem C taková, že M. \=T' právě tehdy, když M. y= T pro libovolnou realizaci Ai jazyka C.
Řešení:
Nejprve předpokládejme, že T = {<pi, ■ ■ ■, (pn} kde ipi,..., ipn jsou uzavřené formule. Uvažme T' = {VILi _,</?í}- Pro libovolnou realizaci Ai jazyka C platí
M. \= VíLi _,</?í   ^   .M |= Vľ=l _,</?í[e] Pro každé ohodnocení e
<=>        |= -i</7í[e] Pro nějaké i a pro každé ohodnocení e <=>        |=       pro nějaké i <=>        ^= </?í pro nějaké i ^ M^T
kde druhá ekvivalence plyne z uzavřenosti formulí ipi,.. . ,ipn a Tvrzení z Příkladu 1.3 (7W |= —[e] pro nějaké i a nějaké e a tudíž pro všechna e, protože —upi je uzavřená) a čtvrtá ekvivalence je přímo tvrzení dokázané v Příkladu 1.3.
V obecném případě nemusí být formule z T uzavřené. Tuto situaci řeší následující jednoduché tvrzení.
8
Tvrzení: Nechť (p je formule predikátového počtu jazyka C a nechť a; je proměnná. Potom pro libovolnou realizaci Ai jazyka C platí Ai \= yxip právě tehdy, když Ai \= (f.
Důkaz:
Ai \= yxip   <=> Ai \= yxip[e] pro každé ohodnocení e
<=> Ai \= (p[e(x/a)] pro každé ohodnocení e a pro každé a E M
<=> Ai \= (p[e\ pro každé ohodnocení e
<=> M \= ip
4.2 Příklad:
Nechť C je jazyk s rovností. Rozhodněte, zda platí následující tvrzení:
1. Existuje teorie T s jazykem C taková, že Ai \= T právě tehdy, když nosič Ai je konečný.
2. Existuje teorie T s jazykem C taková, že Ai \= T právě tehdy, když nosič Ai je nekonečný.
3. Existuje konečná teorie T s jazykem C taková, že Ai \= T právě tehdy, když nosič Ai je nekonečný.
Řešení:
1. Odpověď: Ne! Zdůvodnění: Z přenášky víme, že platí následující tvrzení: Pokud pro každé n existuje model teorie T mohutnosti alespoň n, pak existuje i nekonečný model teorie T.
2. Odpověď: Ano! Zdůvodnění: Uvažme
T = {pt | <pi = Vxi ■ ■ ■ Va;l3y(A*=1-.(a;J =y)),i> 1}
Zřejmě platí, že Ai \= fi právě tehdy, když nosič Ai obsahuje více než i prvků.
3. Odpověď: Ne! Zdůvodnění: Předpokládejme, že T je taková teorie. Pak dle Příkladu 4.1 existuje konečná teorie T' taková, že Ai \= T' právě tehdy, když Ai ^= T pro libovolnou realizaci Ai jazyka C. Avšak, modely teorie T' jsou právě realizace jazyka C s konečným nosičem, což je spor s 1.
4.3 Příklad:
Nechť C = {R} je jazyk s rovností, kde R je binární predikátový symbol. Dokažte, že neexistuje teorie T taková, že pro každou realizaci Ai jazyka C platí Ai \= T právě tehdy, když (M, Rm) je silně souvislý orientovaný graf.
9
Řešení:
Předpokládejme, že taková teorie T existuje. Uvažme novou teorii T' = T U \yxÝyiiy2(R(x,yi) A R(x,y2) —> yi = 2/2)}- Pro každé n > 1 má teorie T model M. mohutnosti n s nosičem M = {l,...,n} a í?m = {(1, 2), (2,3),... , (n — l,n),(n,l)}. Z toho plyne, že existuje i nekonečný model Aioo teorie T'. Ukážeme, že to není možné.
Nechť c,d £ jsou navzájem různá individua. Protože (M^, Rm^) je silně souvislý graf, existují individua ciq, ... , a^,..., a/c+r £ -^00 taková, že ao = afc+r = c, a,k = d a, (aj,aj+i) G -Rmoo Pro 0 < i < /c + i. Soubor Mqo je nekonečný, a proto existuje e G takové, že e 7^ a, pro 0 < i < /c + í. Avšak e je také dosažitelné z c, tj. existují individua bo,... ,br E navzájem různá taková, že e = br, c = bo a (63, G -Rmoo Pro 0 < i < r. Uvažme nej větší j takové, že b j = aj. Pak j < k + í (z různosti bo,... , br), bj+i ^ aj+i, (a,j,aj+i) e RMoo a (a,j,bj+i) e i?Moo což je spor s tím, že je modelem teorie T'.
10