A 19_6_2007 Zkusebni pisemna prace ;)

[neoangin]

Tu je presne zadanie:
=====1.strana=====
AIL062 Vyrokova a predikatova logika
A 19_6_2007 Zkusebni pisemna prace
Znaceni
Vyrokove promenne p,q,r,s,t
Promenne predikatove logiky: x,y,z,...
Funkcni symboly f,g,h,...
Termy jen explicitne vyjadrene napr. f(x), g(x,h(x,y)) atd
Formule A, B, C, D, E...
chceme-li vyjadrit termy ve formuli obsazene, piseme napriklad A(x,z) B(g(y)) C(y,f(x)) atd.
----------------------------------------------------------------------------------
Vyrokova logika
(Trochu teorie modelu pro vyrokovou logiku)
Terminologie: Mejme neprazdnou mnozinu P vyrokovych promennych, predpokladejme, ze je konecna nebo spocetna. Mejme libovolnou podmnozinu A c_ P predpokladame, ze vsechny vyrokove promenne p z A jsou ohodnoceny pravdivostni hodnotou true a vsechny vyrokove promenne q z P-A - jsou ohodnoceny pravdivostni hodnotou false. (Mnozina A je tedy obdobou pravdivostniho ohodnoceni jako funkce prirazujici kazde vyrokove promenne booleovskou hodnotu z mnoziny {true, false}). Mnozinu A nazyvame modelem pro P.

Mnozina formuli vznikne z mnoziny P vyrokovych promennych uzavrenim na logicke spojky ~(negace), & (konjunkce) a \/ disjunkce.

Pravdivostni hodnota formule AA v modelu A je difinovana rekurzivne nasledujicim zpusovem:
* je-li AA nektera z vyrokovych promennych, potom pravdivostni hodnota A je true prave kdyz AA je z A, jinak je pravdivostni hodnota formule AA false
* Je-li AA tvaru ~B a pravdivostni hodnota B je true definujeme pravdivostni hodnotu formule AA jako false, jinak definujeme pravdivostni hodnotu AA jako true.
* Je-li AA tvaru B & C, pravdivostni hodnota A je true, prave kdyz pravdivostni hodnoty B a C jsou true, jinak pravdivoastni hodnotu AA definujeme jako false.
* Podobne, Je-li AA tvaru B \/ C, pravdivostni hodnotu AA definujeme jako false, prave kdyz jsou obe pravdivostni hodnoty formuli B a C false. V ostatnich pripadech je pravdivostni hodnota formule AA true.

Definice. (i) Rikame, ze formule AA je pravdiva v modelu A a piseme A|=AA, jestlize pravdivostni hodnota formule AA v modelu A je true.

(ii) Rikame, ze formule AA je validni a piseme |=AA, je-li AA pravdiva ve vsech modelech pro P. V takovem pripade rikame, ze formule AA je tautologie a piseme |-AA.
Z praktickych duvodu budeme kazdou mnozinu formuli T, S, Ax atd. nazyvat teorie.
=====2.strana======
(iii) Je-li T libovolna teorie (nad mnozinou P), rikame, ze A c_ P je modelem T a piseme A|=T, je-li kazda AA z T pravdiva v modelu A.
(iv) Rikame, ze formule AA je (tautologickym) dusledkem teorie T a piseme T|-AA, jestlize AA je pravdiva v kazdem modelu T.
(v) Rikame, ze teorie T je splnitelna, jestlize ma alespon jeden model. Rikame, ze T je konecne splnitelna, jestlize kazdy konecny fragment T' c_ T ma model.

Pripomenme Vetu o kompaktnosti Vyrokove logiky: Teorie je splnitelna, prave kdyz je konecne splnitelna.
(vi) Rikame, teorie T je uzavrena, jestlize kazdy jeji dusledek je prvkem T.
(vii) Teorie T je sporna jestlize pro libovolnou formuli AA plati T|-AA. Jinak rikame, ze T je bezesporna teorie.

Pripomenme zde nasledujici tvrzeni:
Veta. Teorie T je splnitelna, prave kdyz je bezesporna.
(viii) Rikame, ze mnozina formuli Ax je mnozinou axiomu pro teorii T, jestlize T a Ax maji stejnou mnozinu dusledku.
Rikame, ze teorie T je (konecne) axiomatizovatelna, jestlize ma (konecnou) mnozinu axiomu.
-----------------------------------------------------------------
[Pozor, odvoditelnost je definovana semanticky, viz (ii) a (iv) z definice]

1. a) Ax je mnozinou axiomu pro teorii T, prave kdyz Ax a T maji stejne modely. (2 body)
b) Ax je mnozinou axiomu teorie T, prave kdyz pro kazdou formuli A plati:
Ax|-A prave kdyz T|-A. (3 body)

======3.strana=====
2. Teorie T je sporna, prave kdyz pro nejakou vyrokovou promennou p plati:
T|-p a T|-~p. (1 bod)
b) Je-li T maximalni bezespormna mnozina formuli, potom plati:
T|-A implikuje A z T (4 body)
Jinymi slovy, T je uzavrena teorie.

======4. strana=====
3. Nexht T a S jsou dve teorie takove, ze mnozina vsech modelu teorie S je doplnkem mnoziny vsech modelu teorie T.
Potom obe teorie T i S jsou konecne axiomatizovatelne.

======5.strana======
Predikatova logika

4. Necht T je trorie prvniho radu s jazykem L.
a) definujte rozsireni a konzervativni rozsireni teorie T. (1 bod)
b) nech T' je rozsireni teorie T o nove konstanty (podle Vety o konstantach). Je to konzervativni rozsireni? Kdy je T' bezesporna teorie? (9 bodu)

======6.strana======
5. a) Definujte pojem Skolemovy varianty formule. (2 body)
b) Vyslovte Skolemovou Vetu a dokazte ji. (8 bodu)

======7.strana======
6. Mejme jazyk aritmetiky (0,1,S,+,*,mensi nebo rovno) a axiomy
Q1 S(x) != 0
Q2 S(x) = S(y) -> x=y
Q3 x!=0 -> (ex. y)(S(y) = x)
Q4 x+ 0 = x
Q5 x + S(y) = S(x+y)
Q6 x*0=0
Q7 x*S(y) = (x*y) +x
Q8 x<=y <ex> [(vsechna x) (A(x) -> A (S(x))) -> (vsechna x) A]
a) dokazte x+0 = 0+x (2 body)
b) dokazte, ze soucet je komutativni operace. (8 bodu)

[Void]

Musim ještě dodat, že hodnocení má prý být následující:

alespoň 22 bodů = 3;
?? - 43 bodů = 2;
44 - 50 bodů = 1

Což, společně s podle mně o dost těžším zadáním, než minule, sráží moje šance na úspěch někam zatraceně nízko...

[Eubie]

Jo, opravdu nechápu, v čem je logika toho dávat písemky s postupujícím časem těžší. Triviální předtermín, teď tohle. Asi je to "logické".

Pokud má někdo hint, jak na ten příklad s teoriema T a S, a kde ve slidech nebo skriptech je poslední příklad, budu mu vděčný.

+ pokud sem nekdo da zadani Bcka, tak to je uplny vysmech, jak bylo lehke proti Acku. (10b) za AvB I- A,B nebo co to tam bylo..

[atombomb]

A, tiez moja skupina... pred par hodinami(konkretne na skuske) by ma este zaujalo akyze to bol indukcny krok na riesenie 6b), ale teraz mi uz je to srdecne jedno, az do nejakeho septembroveho opravaku(ktory zaiste bude treba, ledaze by sa aj stepanek vynasnazil a nasiel tych par bodov v kope sena).
a inak teda hnusny termin

[Eubie]

Máte už někdo zapsanou známku? Já nikoliv a byl jsem Ačko na vrchu.

[Eubie]

Plus, dochází někomu význam toho, co udělal Štěpánek se symboly I- a I= ? Například tautologický důsledek A množiny flí T je T I- A (dle Štepánka) - není to překled těch, co sem opisovali zadání, opravdu to tam tak bylo. V skriptech str. 16 je to ale T I= A. Matení "nepřítele"?

[Munch]

Byl jsem B a uz mam vysledek. Dostal jsem trojku, i kdyz sem tomu moc neveril (byl jsem uz zapsanej na dalsi termin). Tak nak pochybuju, ze jsem mel tech 22 bodu, protoze sem to fakt po...

[cathack]

Plus, dochází někomu význam toho, co udělal Štěpánek se symboly I- a I= ? Například tautologický důsledek A množiny flí T je T I- A (dle Štepánka) - není to překled těch, co sem opisovali zadání, opravdu to tam tak bylo. V skriptech str. 16 je to ale T I= A. Matení "nepřítele"?

To byla pouze logika k prvnímu příkladu, jiná, než jakou jsme probírali. Modelový případ, na kterém chtěl vidět, jestli umíme něco dokázat i v jiné logice. Asi.

[Eubie]

Ahoj! Myslim, že prof. Štěpánek si z nás dělal s tím bodováním buď legraci, abysme měli bobky, nebo nám přičítal i body, které tam nebyly:D Stejně jako kdosi předemnou jsem čekal čtyřku, dostal jsem ale dvojku:D

[cathack]

Stejně tak. Čekal jsem čtyři, dostal za dva. Jsem rád, že to mám za sebou!
A přeji štěstí těm, které to teprve čeká!

[Munch]

Je mozny, ze tenhle termin dopad extremne blbe, tak posunul hranici bodu ...

[Inv]

6. Mejme jazyk aritmetiky (0,1,S,+,*,mensi nebo rovno) a axiomy
Q1 S(x) != 0
Q2 S(x) = S(y) -> x=y
Q3 x!=0 -> (ex. y)(S(y) = x)
Q4 x+ 0 = x
Q5 x + S(y) = S(x+y)
Q6 x*0=0
Q7 x*S(y) = (x*y) +x
Q8 x<=y <ex> [(vsechna x) (A(x) -> A (S(x))) -> (vsechna x) A]
a) dokazte x+0 = 0+x (2 body)
b) dokazte, ze soucet je komutativni operace. (8 bodu)

Vi nekdo jak dokazat aspon a) ? Sedel jsem nad tim s kamosem matematikem asi pul hodky..

[Fairfax]

Vi nekdo jak dokazat aspon a) ? Sedel jsem nad tim s kamosem matematikem asi pul hodky.. Sad

Ne to opravdu nevim, ale pokusil jsem se nalezt odpoved. Na zaklade toho co pise pan Vítězslav Švejdar v knize: Logika neúplnost složitost a nutnost se mi povedlo cosi vymyslet (viz.: http://www.peklo.unas.cz/logika/peano.pdf). Nemam zadnou moznost overit si spravnost sveho postupu takze doufam, ze to neni uplny blabol. Kdo se na zkousku chysta, ten z toho mozna pochyti nejakou inspiraci a ti co uz ji maji za sebou (a tim padem rozumi problematice lepe nez ja) tohle forum stejne uz nectou.

[Fairfax]

pokus o dukaz 6. b)
http://www.peklo.unas.cz/logika/peano2.pdf

[InvInv]

Dikes, ja myslim, ze je to super. Bez axiomu indukce, jak jsme to zkouseli, to nejak dokazat neslo Slidy jsem nikdy predtim necetl ani na prednasce nebyl a nevedel jsem, co ma znamenat "<ex>". Rekl bych, ze to mas uplne spravne. Dik