Zkouška 5.6.2007 [A]
-
- Matfyz(ák|ačka) level I
- Příspěvky: 26
- Registrován: 4. 6. 2006 10:51
- Typ studia: Informatika Bc.
- Bydliště: Blava/Praha
- Kontaktovat uživatele:
Zkouška 5.6.2007 [A]
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.
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.
$ man woman
No manual entry for woman
No manual entry for woman
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.Angwin píše: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?
- Fairfax
- Matfyz(ák|ačka) level I
- Příspěvky: 28
- Registrován: 17. 1. 2006 19:05
- Typ studia: Matematika Mgr.
- Login do SIS: vodrj5am
- Kontaktovat uživatele:
Re: Zkouška 5.6.2007 [A]
nemelo by to byt spis Con(T) = {A| T|−A} ?neoangin píše:4. Definujeme-li mnozinu formuli Con(T) = {A| T|−T}
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...
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á.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...
-
- Matfyz(ák|ačka) level I
- Příspěvky: 13
- Registrován: 20. 1. 2006 23:48
- Typ studia: Informatika Bc.
- Bydliště: 17. listopad A1602
- Kontaktovat uživatele:
Re: Zkouška 5.6.2007 [A]
Je tohle dukaz?:neoangin píše: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)
|− ((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.