Zkouška 5.6.2007 [A]

[neoangin]

AIL062 Vyrokova a predikatova logika
Pisemka A

Vyrokova logika
1. Uvazujme formuli [(A⇒B) ∧ (B⇒C)] ⇒ (A⇒C)]
a) Je to tautologie? (1 bod)
b) Pokud ano, sestrojte dukaz pomoci axiomu, odvozovacich pravidel a vet vyrokove logiky, ktere k reseni problemu mohou byt uzitecne. (4 body)
2. Uvazujme formuli [((A⇒B)⇒C)] ⇔ [(B⇒(A⇒C))]
a) Je to tautologie? (1 bod)
b) Pokud ano, sestrojte dukaz pomoci axiomu, odvozovacich pravidel a vet vyrokove logiky, ktere k reseni problemu mohou byt uzitecne. (4 body)
3. Dokazte nasledujici vetu:
Veta. Pro libovolnou mnozinu formuli T a libovolne formule A, B plati (T |− A⇒B) ⇔ (T, A |− B) (10 bodu)

Predikatova logika
Necht L je jazyk prvniho radu s rovnosti, T je teorie s jazykem L (mnozina libovolnych formuli jazyka L), necht A, B, C jsou libovolne formule jazyka L.
4. Definujeme-li mnozinu formuli Con(T) = {A| T|−T}
a) Je to uplna teorie? (2 body)
b) Muze obsahovat uplnou teorii? Kdy? (8 bodu)
5. Mejme libovolnou teorii T a libovolnou formuli A v jazyce L, ukazte ktere z nasledujicich tvrzeni plati a dokazte ho:
a) T |− A prave kdyz T ∪ {¬A} je sporna teorie.
b) T |− A prave kdyz T ∪ {¬uzaver(A)} je sporna teorie. (10 bodu)
6. Necht M je model teorie T v jazyce L a M' je jeho expanze.
a) Ukazte, ze restrikce M'|L je take modelem teorie T (4 body)
b) Ukazte, ze mnozina formuli jazyka L
Thm(M) = {A| A je uzavrena formule a M |= A}
tvori uplnou teorii (6 bodu)

Kto vie spravne odpovede, nech ich sem napise.

[hydrant]

mna by velmi zaujimala 4 uloha. nemate nahodou aspon odkaz na skripta alebo slidy? ja som to tam akosi nenasiel

[luckless]

Zdravim, muzete nekdo popsat jak to probiha kolik je na to casu atd,dik:)

[hydrant]

prisiel som o tri minuty skor ako mala zacat skuska. Skoro vsetci tam uz sedeli a Stepanek vysvetloval pravidla... (neviem co presne, zmeskal som, ale asi nic smrtelne dolezite).

skuska trvala 2 hodiny. potom si odovzdal a isiel domov... ja osobne s dost blbym pocitom

[Angwin]

Prosim vyvratte nebo potvrdte, ze vyrok ve 2. uloze neni tautologie. Pri ohodnoceni A=B=0 mi vychazi 0⇔1 coz neni splneno.
To vypada ze 4 body za 2b) jsou zadarmo, nebo jsem uplne slepy?

[stinny]

Prosim vyvratte nebo potvrdte, ze vyrok ve 2. uloze neni tautologie. Pri ohodnoceni A=B=0 mi vychazi 0⇔1 coz neni splneno.
To vypada ze 4 body za 2b) jsou zadarmo, nebo jsem uplne slepy?

Asi je tam chyba v zadani, imho by tam melo byt [(A⇒(B⇒C)] ⇔ [(B⇒(A⇒C))], ale nevim, byl jsem B, a tam byly obe formule tautologie.

[hydrant]

Asi je tam chyba v zadani.

Podla mna je to spravne, bol som tato skupina a skutocne druhy priklad nebola tautologia...

[Fairfax]

4. Definujeme-li mnozinu formuli Con(T) = {A| T|−T}

nemelo by to byt spis Con(T) = {A| T|−A} ?

jinak podle me:
a) je Con(T) uplna ?

tzn. je bezesporna ?
a splnuje podminku, ze pro kazdou A plati bud
Con(T)|− A nebo Con(T) |− ¬A ?

odpoved: ne - nevime nic o teorii T takze neni vylouceno ze je sporna, coz by vedlo k tomu ze i Con(T) by byla sporna

b) Muze obsahovat uplnou teorii? Kdy ?

odpoved: nejspis ano - pokud by T mela model
byla dle Vety o uplnosti bezesporna... a z toho uz by to snad dokazat slo, jenze nevim poradne jak...

[Michy]

odpoved: nejspis ano - pokud by T mela model
byla dle Vety o uplnosti bezesporna... a z toho uz by to snad dokazat slo, jenze nevim poradne jak...

Podle mě nešlo. Úplnou teorii bude Con(T) obsahovat pokud T bude sporná (pak je Con(T) nadmnožina libovolné teorie v jazyce L a tedy i nějaké úplné) a nebo pokud už sama T bude úplná. Ale sama podle mě nestačí bezespornost nestačí, protože pokud v teorii nekladu žádné nároky na nějaký predikát P, pak nelze dokázat ani(∀x)P(x) ani (∃x)¬P(x) - k libovolné z nich se snadno najde model, ve kterém není daná formule pravdivá a z věty o úplnosti tedy nemůže být ani jedna z nich dokazatelná.

[Inv]

AIL062 Vyrokova a predikatova logika
1. Uvazujme formuli [(A⇒B) ∧ (B⇒C)] ⇒ (A⇒C)]
a) Je to tautologie? (1 bod)
b) Pokud ano, sestrojte dukaz pomoci axiomu, odvozovacich pravidel a vet vyrokove logiky, ktere k reseni problemu mohou byt uzitecne. (4 body)

Je tohle dukaz?:

|− ((A ⇒ B) ∧ (B ⇒ C)) ⇒ (A ⇒ C)
A ⇒ B, B ⇒ C |− A ⇒ C (protoze X∧Y |− X a X∧Y |− Y)
C |− C (VD, 2x MP)

Maji se dukazy delat tak, ze vyjdete od dane formule a dojdete pomoci MP k necemu platnemu? Rekl bych ze ne, ale na cvikach sme to tak delali a je tak udelany i priklad ve slidech.
v1 - v7 ale dokazuje tak, ze vyjde od neceho zahadneho a pomoci MP dojde k zadane formuli, coz je pro me nadlidsky ukol..
Dokazoval bych tak, ze bych pouzil zpusob ze cvik a pak napsal "ctete odzdola nahoru". Tim by se ale v dukazu nepouzival MP, ale "anti-MP", tedy treba C |− C , dalsi krok B, B ⇒ C |− C, coz je divne.