Zkouška 5.6.2007 [A]
Napsal: 5. 6. 2007 12:21
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.