Matfyz Wiki
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]
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
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 x0=0
Q7 xS(y) = (xy) +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)