zk. 27.6.

mk
Matfyz(ák|ačka) level I
Příspěvky: 22
Registrován: 15. 6. 2006 10:20

zk. 27.6.

Příspěvek od mk »

Dnesna skuska bola podobna tej z dna 19.6.2007. Na prvych dvoch stranach sme mali opat napisane nieco o modeloch vo VL a zakladne vety o nich, ktore sme mali vyuzit v prvych troch prikladoch. Odporucam si ten text prestudovat.

Zakladna myslienka je jednoducha. Model nebude funkcia, ktora vyrokovym premennym priraduje true/false, ale bude to podmoznina mnoziny premennych. Potom vyrokova premenna je pravdiva, ak patri do modelu, nepravdiva inak. Pravdivostne ohodnotenie formuly sa pocita indukciou podla zlozitosti formule. Vcelku intuitivne.

Nasleduju priklady, ktore boli na skuske. Prikladam aj moje riesenia, ale za ziadne z nich nerucim. Obzvlast pozor na ulohu c.4, to som tam asi napisal nezmysel.


1 ----------------------------
a) Nech A je model taky, ze A={p,q}. Su nasledovne formule pravdive v modeli A? p, r, (¬¬¬(r) ∨ r), p⇔r, a pod. (2b)

Riesenie: A⊨p, nakolko p je prvkom A. Ostatne podobne.

b)Dokazte, ze A⊨B prave vtedy, ked |- A->B. (3b)
Riesenie:
Nevedel som, ci mozeme pouzit vetu o dedukcii, tak som to radsej dokazal cez modely.
'⇒' Ukazeme, ze pre kazdy model M plati M⊨A⇒B.
Ak M je lubovolny model, potom bud M⊭A alebo M⊨A. Ak nastane prva moznost, potom sme hotovi. Ak nastane druha moznost, tak z predpokladu plynie, ze B je tiez pravdiva v M. V oboch pripadoch teda M⊨A⇒B.
Druhy smer: Nech M je model A->B. Potom plati, ze ak formula A je pravdiva v M, tak aj B je pravdiva v M. To vsak znamena, ze B je tautologicky dosledok A. Symbolicky zapisane: A⊨B.


2 ---------------------------
Uloha: Nech T a S su teorie. Nech kazdy axiom S je vetou T. Dokazte, ze ak existuje formula B taka, ze T∪S⊢B, potom aj S⊢B. Pozn. 'u' je operator zjednotenia mnozin (5b)


Riesenie:
Po 2. neuspesnych pokusoch o dokaz mi napadlo, ze to vlastne nemusi byt pravda. Nech napr. T={(∃x)x=0} a S je prazdna. Potom tu vsetky predpoklady vety splnene, avsak (∃x)x=0 urcite nie je vetou prazdnej teorie.

3 ----------------------------
Uloha: Je pravda, ze kazdu teoriu mozno rozsirit do uzavretej teorie? Ak nie, najdite protipriklad (10b)


Riesenie:
Teoria je uzavreta, ak kazdy veta teorie je sucasne aj jej axiom. Inak povedane, ak sa da formula A dokazat z T, potom musi A patrit T.
Napadlo mi, ze to mozno bude pravda. Uvazme teoriu Con(T).
(.) Con(T) je rozsirenie T, pretoze kazda veta T je aj vetou Con(T).
(..) Con(T) je uzavreta, pretoze ak A je vetou Con(T), potom aj patri do Con(T).
Oba dokazy (.) aj (..) som robil pomocou uvedomenia si, co znamena, ze formula patri do Con(T) resp. co znamena, ze je vetou Con(T).

4 ------------------------------
Uloha: Nech T je teoria s jazykom L a M je jej model. Definujme Thm(M)={A | A je uzavreta a pravdiva v M}. Dokazte, ze Thm(M) je uplna teoria (10b)

Riesenie:
Pojmy uzavreta formula a uplna teoria mi evokovali Lindenbaumovu vetu, ktora hovori, ze kazdu teoriu mozme rozsirit do uplnej teorie s rovnakym jazykom. Oznacme tuto teoriu T'. Z dokazu Lindenbaumovej vety plynie, ze T' je bezesporna a teda podla Vety o uplnosti ma aj model. S Lemmy o reduktoch vieme, ze ak sme pri rozsirovani teorie zachovali jazyk, tak model pre rozsirenu teoriu je tiez modelom povodnej teorie. Odtial dostavame, ze model T' je tiez model T. T' obsahuje teda okrem povodnych axiomov T este vsetky uzavrete formule pravdive v M. Z T' som skusil vynechat povodne axiomy T a pomocou Vety o uzavere som prehlasil, ze dostavame ekvivalentnu teoriu k teorii T'. Novu teoriu oznacme T''. Potom M je model T''. Pokusil som sa ukazat, ze Thm(M) = T''.
Kazdopadne sa mi toto riesenie nepaci a pravdepodobne je niekde chyba. V ukazanom postupe prehlasim, ze T' ma model a ten je rovny M. Avsak poradie je opacne. Najprv zvolime M ako model teorie T a potom by bolo treba ukazat, ze M je aj modelom T'. Mozno je to cele na h***o.

5 -------------------------------
bohuzial si nepamatam, sorry

6 -------------------------------
Uloha:Dokazte, ze Peanova aritmetika je rozsirenim Robinsonovej aritmetiky. (10b)

Riesenie: Mali sme dane axiomy Peanovej aritmetiky I. radu spolu so axiomom indukcie. Uloha bola dokazat, ze Peanova aritmetika je rozsirenim Robinsonovej. Co v preklade znamena dokazat formulu x≠0 => (∃x)S(y)=x. Ja som ulohu riesil tak, ako je to uvedene na niektorom z predchadzajucih diskusii pomocou axiomu indukcie.


Inak pisomka to podla mna bola dost husta. Ak vsak nerozumiete nejakemu pojmu, kludne sa treba spytat prof. Stepanka. Ja som nevedel, co je to uzavreta teoria, tak mi povedal definiciu a este mi aj napisal priklad, ze z teorie {p∧¬p} vieme dokazat kazdu formulu, avsak ani jedna z nich (okrem tej jednej) do teorie nepatri. Preto {p∧¬p} nie je uzavreta.

O bodovani sa nezmienil. Vysledky maju byt najneskor v piatok alebo v pondelok.
Uživatelský avatar
omikron
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 31. 1. 2005 14:04
Typ studia: Informatika Bc.

Re: zk. 27.6.

Příspěvek od omikron »

mk píše: 5 -------------------------------
bohuzial si nepamatam, sorry

5 ( vlastne 3. priklad este z vyrokovej logiky) -------------------------------
Uloha: Dokazte, ze ziadna pozitivna formula nie je validna. (10b)
Kde pozitivna formula je formula tvaru: ((p & ( q v t )) v s)
tj. formula obsahujuca iba konjunkciu, disjunkciu a premenne bez negacie.

Riesenie: Dokazoval som induktivne pomocou zlozitosti formule.


Inak suhlasim s tym, ze to bolo dost drsne, ale mam to! Sice za dobre, ale predsa. :lol:
mk
Matfyz(ák|ačka) level I
Příspěvky: 22
Registrován: 15. 6. 2006 10:20

Příspěvek od mk »

Tak moje riesenia nie su pravdepodobne najspravnejsie. Napokon vsak stacili na dvojku.
Odpovědět

Zpět na „2006“