Zkouška 5.6.2007 [B]
Zkouška 5.6.2007 [B]
Zdravím,
právě jsem se vrátil z experimentálního termínu. Zadání:
1.
a) Rozhodněte, zda formule [ ( A v A ) v ( A & nA ) ] <-> A je tautologie. ( 1 bod )
b) Pokud ano, dokažte ji (bez použití věty o úplnosti). ( 4 body )
2.
a) Rozhodněte, zda formule [ (A -> B) & ( B -> C ) ] -> ( A -> C ) je tautologie ( 1 bod )
b) Pokud ano, dokažte ji (bez použití věty o úplnosti). ( 4 body )
3. Dokažte lemma o důkazu rozborem případů. ( 10 bodů )
4.
a) Zformulujte větu o dedukci ( v PL ). ( 2 body )
b) Dokažte ji. ( 8 bodů )
5. Nechť Con( T ) = { A | T |- A }
a) Definujte úplnou teorii. ( 1 bod )
b) Za jakých podmínek může Con( T ) obsahovat úplnou teorii? ( 9 bodů )
6. Nechť True( T ) = { A | T |= A }. Nechť T, S jsou teorie nad jazykem L, S je rozšíření T.
a) Dokažte, že T je podmnožinou True( S ). ( 4 body )
b) Dokažte, že T je ekvivalentní S, právě když True( T ) = True( S ). ( 6 bodů )
Hodnocení se neví, kdy budou písemky opravené taky ne. Prosím ostatní, aby opravili případné chyby v zadání.
právě jsem se vrátil z experimentálního termínu. Zadání:
1.
a) Rozhodněte, zda formule [ ( A v A ) v ( A & nA ) ] <-> A je tautologie. ( 1 bod )
b) Pokud ano, dokažte ji (bez použití věty o úplnosti). ( 4 body )
2.
a) Rozhodněte, zda formule [ (A -> B) & ( B -> C ) ] -> ( A -> C ) je tautologie ( 1 bod )
b) Pokud ano, dokažte ji (bez použití věty o úplnosti). ( 4 body )
3. Dokažte lemma o důkazu rozborem případů. ( 10 bodů )
4.
a) Zformulujte větu o dedukci ( v PL ). ( 2 body )
b) Dokažte ji. ( 8 bodů )
5. Nechť Con( T ) = { A | T |- A }
a) Definujte úplnou teorii. ( 1 bod )
b) Za jakých podmínek může Con( T ) obsahovat úplnou teorii? ( 9 bodů )
6. Nechť True( T ) = { A | T |= A }. Nechť T, S jsou teorie nad jazykem L, S je rozšíření T.
a) Dokažte, že T je podmnožinou True( S ). ( 4 body )
b) Dokažte, že T je ekvivalentní S, právě když True( T ) = True( S ). ( 6 bodů )
Hodnocení se neví, kdy budou písemky opravené taky ne. Prosím ostatní, aby opravili případné chyby v zadání.
Naposledy upravil(a) stinny dne 5. 6. 2007 15:17, celkem upraveno 3 x.
Thx za doplnění. Bodové ohodnocení je jinak správně?GreedyX píše:U pětky ještě bylo napsáno, že se jedná o teorii 1. řádu
5 a) Byla definice úplné teorie.
Řekněme, že Con(T) obsahuje úplnou teorii S, tedy S je podmnožinou Con(T).GreedyX píše:5 b)
Potom Con(S) je podmnožinou Con(Con(T)), tedy
Con(S) je podmnožinou Con(T).
S je úplná, tedy pro každou uzavřenou formuli A je buď S |- A nebo S |- nA. Tedy { A, nA } průnik Con(S) je neprázdná množina, z čehož { A, nA } průnik Con(T) je neprázdná množina.
No a pak jsou dvě možnosti. Buď existuje uzavřená fle B tak, že T |- B a T |- nB, potom je T sporná, nebo ne, a tak je T úplná. Nutná podmínka toho, aby Con(T) obsahovalo úplnou teorii tedy je, že T je úplná nebo sporná.
Pro každou fli A z T platí T |= A. Tedy A je platná v každém modelu M teorie T. Protože S je rozšíření T, tak každý model S lze redukovat na model T. S i T jsou nad stejným jazykem, takže M je model S => M je model T. Protože A je platná v každém modelu T a každý model S je zároveň modelem T, je i S |= A.GreedyX píše:6 a)
Tohle jsem nedal, uvědomil jsem si to, až když jsem se potom podíval do skript. Podle mně by to mělo být něco takovéhle:GreedyX píše:6 b)
S je rozšíření T, jsou nad stejným jazykem. A je fle jazyka L. Potom platí následující řetěz ekvivalencí:
S je ekvivaletní T <=> S je konzervativní rozšíření T <=> každý model T lze expandovat do modelu S a každý model S lze expandovat do modelu T <=> pro všechny realizace M ( M je model S <=> M je model T ) <=> pro všechny modely M teorie T ( T,M |= A <=> S,M |= A ) <=> pro všechny fle A ( T |= A <=> S |= A ) <=> True(T) = True(S).
Jedná se o myšlenkový pochod z tramvaje, takže je to možná špatně nebo někde nepřesně, každopádně mě štve, že jsem si neuvědomil, že můžu použít definici konzervativního rozšíření a nenapsal tam aspoň tohle
-
- Matfyz(ák|ačka) level I
- Příspěvky: 8
- Registrován: 15. 6. 2006 18:36
- Typ studia: Informatika Bc.
Kde zjistím výsledek?
Výsledek písemky mi Štěpánek pošle mailem, nebo to rovnou napíše do SISu?
Je těžké být debilem, konkurence je příliš velká...
-
- Matfyz(ák|ačka) level III
- Příspěvky: 137
- Registrován: 1. 6. 2006 08:47
- Typ studia: Informatika Mgr.
- Bydliště: Praha 4
- Kontaktovat uživatele:
Re: Kde zjistím výsledek?
Píše to rovnou do SISu. A do indexu tuším během dalších termínů zkoušek nebo po dohodě jindy.GreedyX píše:Výsledek písemky mi Štěpánek pošle mailem, nebo to rovnou napíše do SISu?