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í.

písemky budou opravený do pátku

U pětky ještě bylo napsáno, že se jedná o teorii 1. řádu
5 a) Byla definice úplné teorie.

BTW
Nevíte někdo, jak se řeší
5 b)
a
6 a) b)

GreedyX wrote:U pětky ještě bylo napsáno, že se jedná o teorii 1. řádu
5 a) Byla definice úplné teorie.

Thx za doplnění. Bodové ohodnocení je jinak správně?

GreedyX wrote:5 b)

Řekněme, že Con(T) obsahuje úplnou teorii S, tedy S je podmnožinou Con(T).
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á.

GreedyX wrote:6 a)

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 wrote:6 b)

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:
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 :(

body sedí

Máte už někdo výsledek? Těch písemek bylo méně než 30, oprava nemůže trvat tak dlouho...

kamos uz vraj ma, on bol Acko,ja som bol Bcko,a stale nic :(

jo už výsledek mám, byl sem B
bohužel ne pozitivní... udělal to někdo?

Mam megatesne za 1 :D A co jsem tam videl Stepankovi pres rameno, je jeste minimalne jedna jednicka ...

stinny wrote:Mam megatesne za 1 :D A co jsem tam videl Stepankovi pres rameno, je jeste minimalne jedna jednicka ...

Já se přiznávám k jedničce. A neptejte se mě, jak se to stalo. Sám nevím :-)

Výsledek písemky mi Štěpánek pošle mailem, nebo to rovnou napíše do SISu?

GreedyX wrote:Výsledek písemky mi Štěpánek pošle mailem, nebo to rovnou napíše do SISu?

Píše to rovnou do SISu. A do indexu tuším během dalších termínů zkoušek nebo po dohodě jindy.

mate uz kazdy znamku z toho teminu?? lebo ja stale nie... a uz by som to celkom rad vedel, aj keby to bola 4 :(

tym co nemaju zapocet zapise znamku do sisu az po zapocte

no len to, ze ja som zapocet mal uz tyzden pred skuskou.... tak fakt neviem,ze v com to vezi. Asi ho kusok zaspamujem...

Moj dokaz:

T je podmozina True(S):
Nech fle A je specialny axiom teorie T. Kedze S je rozsirenie T, tak A je vetou teorie T. Podla vety o uplnosti dostavame, ze A je semantickym dosledkom teorie S a teda aj patri do mnoziny True(S).

T a S su ekvivalentne prave vtedy ak True(S)=True(T)
Podla definicie je T ekvivalentne s S, ak pre kazdu formulu A plati, ze A je vetou S prave vtedy, ked A je vetou T. Veta o uplnosti tvrdi, ze A je vetou T (resp. S) prave vtedy, ked je aj semantickym dosledkom T (resp. S). Symbolicky napisane:
T⊢A ⇔ S⊢A (definicia ekvivalencie)
T⊢A ⇔ T⊨A (veta o uplnosti)
S⊢A ⇔ S⊨A (veta o uplnosti)
Dokopy teda S⊨A ⇔ T⊨A pre kazdu flu A, co plati prave vtedy, ak True(S)=True(T).