# Zkouška 5.6.2007 [A]

<{ForumPost(poster="neoangin", timestamp=2007-06-05 12:21:27)}>
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.
<{/ForumPost}>

<{ForumPost(poster="hydrant", timestamp=2007-06-09 15:01:54)}>
mna by velmi zaujimala 4 uloha. nemate nahodou aspon odkaz na skripta alebo slidy? ja som to tam akosi nenasiel :(
<{/ForumPost}>

<{ForumPost(poster="luckless", timestamp=2007-06-09 16:08:20)}>
Zdravim, muzete nekdo popsat jak to probiha kolik je na to casu atd,dik:)
<{/ForumPost}>

<{ForumPost(poster="hydrant", timestamp=2007-06-09 18:24:28)}>
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  :?
<{/ForumPost}>

<{ForumPost(poster="Angwin", timestamp=2007-06-14 01:03:17)}>
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?
<{/ForumPost}>

<{ForumPost(poster="stinny", timestamp=2007-06-14 09:37:58)}>

 > Angwin wrote: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.
<{/ForumPost}>

<{ForumPost(poster="hydrant", timestamp=2007-06-14 11:10:06)}>

 > stinny wrote:Asi je tam chyba v zadani.

Podla mna je to spravne, bol som tato skupina a skutocne druhy priklad nebola tautologia...
<{/ForumPost}>

<{ForumPost(poster="Fairfax", timestamp=2007-06-16 20:02:23)}>

 > neoangin wrote: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...
<{/ForumPost}>

<{ForumPost(poster="Michy", timestamp=2007-06-25 18:58:54)}>

 > 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á.
<{/ForumPost}>

<{ForumPost(poster="Inv", timestamp=2007-06-25 23:19:48)}>

 > neoangin wrote: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.
<{/ForumPost}>