zkouska 19.9.
- Lada
- Donátor
- Příspěvky: 165
- Registrován: 9. 1. 2005 10:17
- Typ studia: Informatika Bc.
- Bydliště: Slaný / zácpa na Evropské
zkouska 19.9.
T je sporna mnozina, dokazte ze plati T|=A
dokazte(ExA vExB) -> Ex (A v B)
definujte expanzi / restrikci modelu a ukazte pomoci nej podminku pro to ze T´ je rozsireni T
vyrokova fle A je v negativni normalni formuli (NNF) pokud negace se vyskytuje jen u promennych, dokazte ze z kazde fle A lze vytvorit fli An v NNF takovou, ze je ekvivalentni (podobne jako CNF/DNF)
Axiomy Pearovy aritmetiky a dukaz axiomu Q3
L je jazyk s rovnosti, bez zadnych dalsich specialnich symbolu, definujte teorii T tak, aby kazdy jeji model mel prave 3 prvky
jeste tam byl dukaz nejake formule za 5 nebo 10 bodu a dalsi "kejkle s teorii" myslim ze obtiznost byla srovnatelna s minulou pisemkou...
Co me ale docela prekvapilo byl uvodni maly test, jehoz obtiznost sla taky nahoru - byly tam otazky i na pocet modelu v teoriich, dokazatelnost v predikatove logice s rovnosti...
Hodne uspechu na poslednim terminu;o))
- Tacoud
- Donátor
- Příspěvky: 53
- Registrován: 16. 9. 2005 08:38
- Typ studia: Informatika Bc.
- Bydliště: Mladá Boleslav
- Kontaktovat uživatele:
První test byl opravdu drsnější než ty předchozí. Podle mě ho sestavoval Petr Olmer (http://petr.olmer.cz), protože ty příklady byly hodně podobné těm z cvičení.
Co si pamatuji z otázek velkého testu:
<ul>
<li>Dokažte: (Vx)(A->B)->((Vx)A->(Vx)B)
<li>Dokažte: (Ex)(AvB)<->(Av(Ex)B)
<li>Vyslovte a dokažte větu o dedukci (ta je tam snad vždy)
Dokažte, že existují rozšíření Peanovy aritmetiky, která nejsou izomorfní se standardním modelem Peanovy aritmetiky.
<li>Dokažte, že p & q je "monotonni" k p i q. Formule A je monotonní vzhledem k proměnné x, pokud platí, že když |- C->D, potom je také |-Ax[C]->Ax[D]. (Za tohle bych ruku do ohně nedal, kdyžtak mě opravte...)
<li>Mějme množinu formulí T. Množinu modelů množiny T označme Val(T). S je podmnožina T, Val(S) množina modelů S. Dokažte, že Val(T) je podmnožina Val(S), speciálně když S je prázdná, tak Val(S) obsahuje celé universum všech ohodnocení.
<li>Dokažte, že když T' je konzervativní rozšíření T, potom jsou buď obě sporné nebo obě bezesporné
</ul>
- Angel
- Matfyz(ák|ačka) level III
- Příspěvky: 121
- Registrován: 9. 9. 2005 19:28
- Typ studia: Informatika Mgr.
- Bydliště: Znojmo / Praha
- Kontaktovat uživatele:
Test
1. (5 bodu)
Kód: Vybrat vše
Je-li L jaz. vyr. logiky a T je sporna mnoz. fli jazyka L, ukazte, ze plate
T|=A
pro kazdou fli A jaz. L
Kód: Vybrat vše
Ve vy. logice s jaz. L rikame, ze A je v neg. norm. tvaru jestlize symbol negace ve fli A se vyskytuje jen u vyr. promennych. Ukazte, ze ke kazde fli A lze sestrojit ekv. fli. A v NFF.
Kód: Vybrat vše
Rikame, ze fle ve vy. log. A je monotone rostouci vzhledem k promenne p, jestlize pro lib. fle C, D takove, ze |- C -> D plati |- Ap[C] -> Ap[D], kde Ap[C] vzikne z fle A dosazenim fle C za vsechny promonne p v A.
Ukazte, ze p v q je rostouci k obame promennym.
Kód: Vybrat vše
V pred. logice dokazte
((Ex)A v (Ex) B) -> (Ex)(A v B)
Kód: Vybrat vše
V pred. log. ukazte, ze je-li A* uzaver fle A a fle A' je instanci fle A, potom |- A* -> A'
Kód: Vybrat vše
V pred. logice dokazte
(Vx)(A -> B) -> ((Ex)A -> (Ex)B)
Kód: Vybrat vše
V pred. log. predpokladejme, ze jaz. L' je rosirenim jaz. L. Necht M je nejaka interpretace jaz. L a M' je interpretace jaz. L'. Definujte pojem M je restriktivni interpretace M' na jazyk L. Jsou-li T a T' teorie s jazyky L a L' po rade, ukazte, ze pomoci def. pojmu lze vyslovit nutnou a postacujici podminku pro tvrzeni, ze T' je rorsirenim teorie T.
Kód: Vybrat vše
Jestlize term t neobsahuje promennou x a v pred. logice plate
Ax[t] <-> (Ex)(x = t & A) (1)
Ukazte, ze v standardnim modelu aritmetiky N bez predpokladu o promenne x, tvrzeni (1) neplati.
Kód: Vybrat vše
V pred. logice s jaz. L, ktery neobsahuje zadne funkcni symboly a z predikatu jen predikat rovnosti, definujte teorii T, ktera ma jen tri modely.
Kód: Vybrat vše
Napiste ax. Peanovy aritmetiky (1. radu) P a dokazte nasl. axiom Robinsonovy aritmetiky Q.
x != 0 -> (Ey | (x = S(y))
Ocenil bych, kdyby nekdo napsal, jak se resi priklad 4 a 6, chtel bych v tom mit jasno. Diky .
- Tacoud
- Donátor
- Příspěvky: 53
- Registrován: 16. 9. 2005 08:38
- Typ studia: Informatika Bc.
- Bydliště: Mladá Boleslav
- Kontaktovat uživatele:
Ale bojím se, že ne všichni, co to opravují, posílají maily.Od: "Petr Olmer" <petr.olmer@mff.cuni.cz>
Předmět: Logika
Komu: undisclosed-recipients
Datum: Úterý, 19. září 2006 - 22:31:04
Vazeny pane kolego,
z dnesni zkousky z logiky mate trojku.
Srdecne
Petr Olmer
prislo mi presne to stejnyTacoud píše:No - já vlastně tu známku ještě nemám v SISu, ale přišel mi takovýhle mail:Od: "Petr Olmer" <petr.olmer@mff.cuni.cz>
Předmět: Logika
Komu: undisclosed-recipients
Datum: Úterý, 19. září 2006 - 22:31:04
Vazeny pane kolego,
z dnesni zkousky z logiky mate trojku.
Srdecne
Petr Olmer
Re: Test
1. řešení (spíše na ověření, že to skutečně platí)Angel píše: 4. (5 bodu)Kód: Vybrat vše
V pred. logice dokazte ((Ex)A v (Ex) B) -> (Ex)(A v B)
Podle věty o úplnosti
Kód: Vybrat vše
|- ((Ex)A v (Ex) B) -> (Ex)(A v B)
Kód: Vybrat vše
|= ((Ex)A v (Ex) B) -> (Ex)(A v B)
2. řešení (elegantní)
Pokud by skutečně platilo
Kód: Vybrat vše
|-? ((Ex)A v (Ex) B) -> (Ex)(A v B)
Kód: Vybrat vše
(Ex)A v (Ex) B |-? (Ex)(A v B)
Kód: Vybrat vše
(Ex)A |-? (Ex)(A v B), (Ex) B |-? (Ex)(A v B)
Kód: Vybrat vše
|-? (Ex)A -> (Ex)(A v B), |-? (Ex) B -> (Ex)(A v B)
Kód: Vybrat vše
|- A -> (A v B), |- B -> (A v B)
Kód: Vybrat vše
|- (Ex)A -> (Ex)(A v B), |- (Ex) B -> (Ex)(A v B)
3. řešení (trochu delší)
Podle A3 je to totéž jako
Kód: Vybrat vše
(Vx)(-A & -B) -> (Vx)-A & (Vx)-B
Kód: Vybrat vše
(Vx)(C & D) -> (Vx)C & (Vx)D
Kód: Vybrat vše
|- (Vx)(C & D) -> C & D
Kód: Vybrat vše
|- C & D -> C, |- C & D -> D
Kód: Vybrat vše
|- (Vx)(C & D) -> C, |- (Vx)(C & D) -> D
Kód: Vybrat vše
(Vx)(C & D) |- C, (Vx)(C & D) |- D
Kód: Vybrat vše
(Vx)(C & D) |- (Vx)C, (Vx)(C & D) |- (Vx)D
Kód: Vybrat vše
(Vx)(C & D) |- (Vx)C & (Vx)D
Kód: Vybrat vše
|- (Vx)(C & D) -> (Vx)C & (Vx)D
Poznámka dole: Kvůli použití věty o dedukci samozřejmě předpokládám, že v A ani B není volná jiná proměnná než x. Pokud by snad byla, snadno ji odstraním větou o konstantách.
Re: Test
Podle axiomu specifikaceAngel píše: 6. (10 bodu)Kód: Vybrat vše
V pred. logice dokazte (Vx)(A -> B) -> ((Ex)A -> (Ex)B)
Kód: Vybrat vše
|- (Vx)(A -> B) -> (A -> B)
Kód: Vybrat vše
(Vx)(A -> B) |- A -> B
Kód: Vybrat vše
(Vx)(A -> B) |- (Ex)A -> (Ex)B
Kód: Vybrat vše
|- (Vx)(A -> B) -> (Ex)A -> (Ex)B
- Che
- Donátor
- Příspěvky: 166
- Registrován: 2. 6. 2005 12:29
- Typ studia: Informatika Mgr.
- Login do SIS: przyc4am
- Bydliště: EU
- Kontaktovat uživatele:
Mně taky Doufám, že Olmer omylem nezmáčkl Send To All...Temaris píše:prislo mi presne to stejnyTacoud píše:No - já vlastně tu známku ještě nemám v SISu, ale přišel mi takovýhle mail:Od: "Petr Olmer" <petr.olmer@mff.cuni.cz>
Předmět: Logika
Komu: undisclosed-recipients
Datum: Úterý, 19. září 2006 - 22:31:04
Vazeny pane kolego,
z dnesni zkousky z logiky mate trojku.
Srdecne
Petr Olmer
- Lada
- Donátor
- Příspěvky: 165
- Registrován: 9. 1. 2005 10:17
- Typ studia: Informatika Bc.
- Bydliště: Slaný / zácpa na Evropské
btw koukal jsem se do pisemky a zjistil jsem ze otazku:
"L je jazyk s rovnosti, bez zadnych dalsich specialnich symbolu, definujte teorii T tak, aby kazdy jeji model mel prave 3 prvky (15b)" jsem opravdu nemel dobre... tusite nekdo jak to ma byt spravne?
Nejdřív zajistím, že má alespoň tři prvky:Lada píše: "L je jazyk s rovnosti, bez zadnych dalsich specialnich symbolu, definujte teorii T tak, aby kazdy jeji model mel prave 3 prvky (15b)"
Kód: Vybrat vše
(Ex)(Ey)(Ez)(x <> y & x <> z & y <> z)
Kód: Vybrat vše
(Vx)(Vy)(Vz)(Vw)(x = y v x = z v x = w v y = z v y = w v z = w)