# zkouska 19.9.

<{ForumPost(poster="Lada", timestamp=2006-09-20 00:26:04)}>
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))
<{/ForumPost}>

<{ForumPost(poster="Tacoud", timestamp=2006-09-20 13:29:49)}>
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](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>
<{/ForumPost}>

<{ForumPost(poster="Angel", timestamp=2006-09-21 12:25:43)}>
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 :-).
<{/ForumPost}>

<{ForumPost(poster="Hugo", timestamp=2006-09-21 15:30:15)}>
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..
<{/ForumPost}>

<{ForumPost(poster="Lada", timestamp=2006-09-21 21:02:59)}>
ach jo ach jo... nejsem jediny kdo jeste ceka na znamku, ze ne? clovek by rek ze kdyz nas tam bylo jenom par...  :?
<{/ForumPost}>

<{ForumPost(poster="Tacoud", timestamp=2006-09-21 21:54:08)}>
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](mailto: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.
<{/ForumPost}>

<{ForumPost(poster="Temaris", timestamp=2006-09-21 22:42:58)}>

 > 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](mailto: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
<{/ForumPost}>

<{ForumPost(poster="jamais", timestamp=2006-09-21 22:48:05)}>

 > 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.
<{/ForumPost}>

<{ForumPost(poster="jamais", timestamp=2006-09-21 23:13:28)}>

 > 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


<{/ForumPost}>

<{ForumPost(poster="Che", timestamp=2006-09-22 00:38:58)}>

 > 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](mailto: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:
<{/ForumPost}>

<{ForumPost(poster="Lada", timestamp=2006-09-22 15:08:43)}>
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?
<{/ForumPost}>

<{ForumPost(poster="jamais", timestamp=2006-09-22 17:42:37)}>

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


<{/ForumPost}>

<{ForumPost(poster="Angel", timestamp=2006-09-22 18:49:46)}>
aha, takze staci takova blbost na 15 bodu? hmm hmm :-)
<{/ForumPost}>

<{ForumPost(poster="vegetta", timestamp=2006-09-24 19:26:19)}>
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
<{/ForumPost}>