A 19_6_2007 Zkusebni pisemna prace ;)
-
- Matfyz(ák|ačka) level I
- Příspěvky: 26
- Registrován: 4. 6. 2006 10:51
- Typ studia: Informatika Bc.
- Bydliště: Blava/Praha
- Kontaktovat uživatele:
A 19_6_2007 Zkusebni pisemna prace ;)
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)
=====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)
$ man woman
No manual entry for woman
No manual entry for woman
- Void
- Matfyz(ák|ačka) level II
- Příspěvky: 54
- Registrován: 17. 1. 2006 16:21
- Typ studia: Informatika Mgr.
hodnoceni
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...
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...
Aurë Entuluva!!
- Eubie
- Matfyz(ák|ačka) level III
- Příspěvky: 295
- Registrován: 8. 10. 2005 15:35
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
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..
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..
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
a inak teda hnusny termin
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...
Sacrificing minions: Is there any problem it can't solve?
http://www.giantitp.com
http://www.giantitp.com
- cathack
- Matfyz(ák|ačka) level I
- Příspěvky: 31
- Registrován: 31. 1. 2006 14:18
- Typ studia: Informatika Bc.
- Login do SIS: kubit5am
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 píše: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"?
Je mozny, ze tenhle termin dopad extremne blbe, tak posunul hranici bodu ...
Sacrificing minions: Is there any problem it can't solve?
http://www.giantitp.com
http://www.giantitp.com
-
- Matfyz(ák|ačka) level I
- Příspěvky: 13
- Registrován: 20. 1. 2006 23:48
- Typ studia: Informatika Bc.
- Bydliště: 17. listopad A1602
- Kontaktovat uživatele:
Re: hodnoceni
Vi nekdo jak dokazat aspon a) ? Sedel jsem nad tim s kamosem matematikem asi pul hodky..Void píše: 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)
- Fairfax
- Matfyz(ák|ačka) level I
- Příspěvky: 28
- Registrován: 17. 1. 2006 19:05
- Typ studia: Matematika Mgr.
- Login do SIS: vodrj5am
- Kontaktovat uživatele:
Dukaz v Peanove aritmetice
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.Inv píše: Vi nekdo jak dokazat aspon a) ? Sedel jsem nad tim s kamosem matematikem asi pul hodky.. Sad
- Fairfax
- Matfyz(ák|ačka) level I
- Příspěvky: 28
- Registrován: 17. 1. 2006 19:05
- Typ studia: Matematika Mgr.
- Login do SIS: vodrj5am
- Kontaktovat uživatele:
Pokracovani
pokus o dukaz 6. b)
http://www.peklo.unas.cz/logika/peano2.pdf
http://www.peklo.unas.cz/logika/peano2.pdf