# Zkouška 5.6.2007 [B] <{ForumPost(poster="stinny", timestamp=2007-06-05 11:02:57)}> 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í. <{/ForumPost}> <{ForumPost(poster="doser", timestamp=2007-06-05 12:25:05)}> písemky budou opravený do pátku <{/ForumPost}> <{ForumPost(poster="GreedyX", timestamp=2007-06-05 12:25:20)}> 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) <{/ForumPost}> <{ForumPost(poster="stinny", timestamp=2007-06-05 12:41:11)}> > 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 :( <{/ForumPost}> <{ForumPost(poster="GreedyX", timestamp=2007-06-05 12:53:55)}> body sedí <{/ForumPost}> <{ForumPost(poster="Anonymous", timestamp=2007-06-07 13:52:51)}> Máte už někdo výsledek? Těch písemek bylo méně než 30, oprava nemůže trvat tak dlouho... <{/ForumPost}> <{ForumPost(poster="oasisfan", timestamp=2007-06-08 11:37:05)}> kamos uz vraj ma, on bol Acko,ja som bol Bcko,a stale nic :( <{/ForumPost}> <{ForumPost(poster="doser", timestamp=2007-06-08 12:51:21)}> jo už výsledek mám, byl sem B bohužel ne pozitivní... udělal to někdo? <{/ForumPost}> <{ForumPost(poster="stinny", timestamp=2007-06-08 15:43:51)}> Mam megatesne za 1 :D A co jsem tam videl Stepankovi pres rameno, je jeste minimalne jedna jednicka ... <{/ForumPost}> <{ForumPost(poster="ps", timestamp=2007-06-08 16:00:40)}> > 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 :-) <{/ForumPost}> <{ForumPost(poster="GreedyX", timestamp=2007-06-08 16:40:24)}> Výsledek písemky mi Štěpánek pošle mailem, nebo to rovnou napíše do SISu? <{/ForumPost}> <{ForumPost(poster="ps", timestamp=2007-06-08 17:02:38)}> > 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. <{/ForumPost}> <{ForumPost(poster="oasisfan", timestamp=2007-06-12 10:10:05)}> mate uz kazdy znamku z toho teminu?? lebo ja stale nie... a uz by som to celkom rad vedel, aj keby to bola 4 :( <{/ForumPost}> <{ForumPost(poster="hydrant", timestamp=2007-06-12 11:02:06)}> tym co nemaju zapocet zapise znamku do sisu az po zapocte <{/ForumPost}> <{ForumPost(poster="oasisfan", timestamp=2007-06-12 12:36:24)}> no len to, ze ja som zapocet mal uz tyzden pred skuskou.... tak fakt neviem,ze v com to vezi. Asi ho kusok zaspamujem... <{/ForumPost}> <{ForumPost(poster="mk", timestamp=2007-06-26 21:17:48)}> 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). <{/ForumPost}>