zkouska 19.9.

Tak co si pamatuju

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))

Hurrá, mám trojku :D !! Největší zvrhlost tohoto semestru mám z krku.

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>

Mini test se mne zdal na to, ze sem toho moc z logiky nevidel v pohode a dal se napsat bez problemu. Druha cast uz pro me znamenala si jen opsat zadani a jit domu :-). Tady ho mate (cislovani prikladu bude nejspis prehazeny):

1. (5 bodu)

   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

2. (10 bodu)

   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.

3. (10 bodu)

   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.

4. (5 bodu)

   V pred. logice dokazte ((Ex)A v (Ex) B) -> (Ex)(A v B)

5. (5 bodu)

   V pred. log. ukazte, ze je-li A* uzaver fle A a fle A' je instanci fle A, potom |- A* -> A'

6. (10 bodu)

   V pred. logice dokazte (Vx)(A -> B) -> ((Ex)A -> (Ex)B)

7. (10 bodu)

   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.

8. (10 bodu)

   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.

9. (15 bodu)

   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.

10. (15 bodu)

    Napiste ax. Peanovy aritmetiky (1. radu) P a dokazte nasl. axiom Robinsonovy aritmetiky Q. x != 0 -> (Ey | (x = S(y))

Sory za vsechny chyby / preklepy atd. nechce se mne to po sobe cist ;-).

Ocenil bych, kdyby nekdo napsal, jak se resi priklad 4 a 6, chtel bych v tom mit jasno. Diky :-).

on tam Stepanek se svymi pomocniky chvili diskutoval nad obtiznosti prvniho testu, ptz jeden byl nejak vyrazne tezsi. Ale mozna se to lidem, kteri meli lehci prvni test, zase vratilo v 2. kole. Ta pisemka nahore je velmi stavnata..

ach jo ach jo... nejsem jediny kdo jeste ceka na znamku, ze ne? clovek by rek ze kdyz nas tam bylo jenom par... :?

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

Ale bojím se, že ne všichni, co to opravují, posílají maily.

Tacoud wrote: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

prislo mi presne to stejny

Angel wrote: 4. (5 bodu)

V pred. logice dokazte
((Ex)A v (Ex) B) -> (Ex)(A v B)

1. řešení (spíše na ověření, že to skutečně platí)
Podle věty o úplnosti

|- ((Ex)A v (Ex) B) -> (Ex)(A v B)

právě když

|= ((Ex)A v (Ex) B) -> (Ex)(A v B)

Mějme strukturu, která je modelem předpokladu. A a B jsou vzájemně zaměnitelné (disjunkce je komutativní), stačí tedy uvažovat, že v tomto modelu existuje prvek x, že |= (Ex)A, a pak tento prvek bude totožný s prvkem hledaným v závěru. Formule je tedy pravdivá, a proto dokazatelná.

2. řešení (elegantní)
Pokud by skutečně platilo

|-? ((Ex)A v (Ex) B) -> (Ex)(A v B)

pak by podle věty o dedukci (viz poznámka dole)

(Ex)A v (Ex) B |-? (Ex)(A v B)

což je podle věty o důkazu rozborem případů ekvivalentní

(Ex)A |-? (Ex)(A v B), (Ex) B |-? (Ex)(A v B)

a podle věty o dedukci

|-? (Ex)A -> (Ex)(A v B), |-? (Ex) B -> (Ex)(A v B)

To už dokážeme snadno. Z výrokové logiky

|- A -> (A v B), |- B -> (A v B)

a z věty o distribuci kvantifikátorů

|- (Ex)A -> (Ex)(A v B), |- (Ex) B -> (Ex)(A v B)

Tím je formule dokázána.

3. řešení (trochu delší)
Podle A3 je to totéž jako

(Vx)(-A & -B) -> (Vx)-A & (Vx)-B

Abych se vyhnul negacím, položím C = -A a D = -B.

(Vx)(C & D) -> (Vx)C & (Vx)D

Podle axiomu specifikace je

|- (Vx)(C & D) -> C & D

Z výrokové logiky

|- C & D -> C, |- C & D -> D

složením pak

|- (Vx)(C & D) -> C, |- (Vx)(C & D) -> D

větou o dedukci

(Vx)(C & D) |-  C, (Vx)(C & D) |- D

pravidlem generalizace

(Vx)(C & D) |-  (Vx)C, (Vx)(C & D) |- (Vx)D

a z výrokové logiky

(Vx)(C & D) |-  (Vx)C & (Vx)D

a větou o dedukci

|- (Vx)(C & D) -> (Vx)C & (Vx)D

což bylo potřeba dokázat.

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.

Angel wrote: 6. (10 bodu)

V pred. logice dokazte
(Vx)(A -> B) -> ((Ex)A -> (Ex)B)

Podle axiomu specifikace

|- (Vx)(A -> B) -> (A -> B)

podle věty o dedukci (ověříme uzavřenost)

(Vx)(A -> B) |- A -> B

podle věty o distribuci kvantifikátorů

(Vx)(A -> B) |- (Ex)A -> (Ex)B

a podle věty o dedukci

|- (Vx)(A -> B) -> (Ex)A -> (Ex)B

Temaris wrote:

Tacoud wrote: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

prislo mi presne to stejny

Mně taky :) Doufám, že Olmer omylem nezmáčkl Send To All... :lol:

tak mam konecne za 3 i zapsane od Stepanka
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?

Lada wrote: "L je jazyk s rovnosti, bez zadnych dalsich specialnich symbolu, definujte teorii T tak, aby kazdy jeji model mel prave 3 prvky (15b)"

Nejdřív zajistím, že má alespoň tři prvky:

(Ex)(Ey)(Ez)(x <> y & x <> z & y <> z)

A pak, že má nejvýše tři prvky:

(Vx)(Vy)(Vz)(Vw)(x = y v x = z v x = w v y = z v y = w v z = w)

aha, takze staci takova blbost na 15 bodu? hmm hmm :-)

ohladne toho druheho prikladu (to s tou negativni formou)

no moje uvazovani vede dvema cestami

1. ja myslim ze je to blbost, pretoze non(A->B) nedak provest rozumne do nejake redukvoane formy tak aby ta negace vlezla dnu

2. da se to prepsat na formu s [and] (A & nonB)

ted co je spravne