Zkouska 24.06.2008

Vyrokova logika

1a) Definujte, kdy je formule A semantickym dusledkem mnoziny formuli (tj. teorie) T (1b)
1b) Dokazte, ze semanticky dusledek je kompaktni, tedy ze plati: Je-li T |= A, potom pro nejakou konecnou podmnozinu T' casti T plati T' |= A (4b)
2) Je-li dan jazyk vyrokove logiky s alespon jednou vyrokovou promennou, sestrojte dve maximalni bezesporne mnoziny formuli, ktere jsou disjunktni (5b)
3) Definice: rikame, ze formule A je pozitivni, jestlize je tvorena z vyrokovych promennych jen pomoci spojek konjunkce a disjunkce. Napr. formule (p & (q v r)) v s je pozitivni, zatimco non p nebo p <-> q nejsou pozitivni.
Dokazte, ze negace zadne pozitivni formule neni validni (10b)
4a) Definujte pojen uplne teorie. Je-li dana teorie T, najdete postacujici podminku, aby T bylo mozne rozsirit do uplne teorie (3b)
4b) Dokazte tvrzeni: Je-li T uplna teorie, potom {A | A je uzavrena formule, T |- A} je maximalni bezesporna mnozina (7b)
5a) Definujte pojem konzervativniho rozsireni teorie T s jazykem L (1b)
5b) Vyslovte vetu o konstantach a dokazte, ze pridanim novych konstant k teorii T podle teto vety vznikne konzervativni rozsireni teorie T
6a) V Robinsnove aritmetice dokazte: S(x) + y = S(x+y) (2b)
6b) V Robinsnove aritmetice dokazte, ze soucet je komutativni operace (8b)

Mno... kdo se to mesic ucil a ma presne v hlave srovnany ten konec skript ohledne uplnych a konzervativnich teorii, bezespornych mnozin, etc. tak asi nebylo co resit. Kdo se spolehal na to, ze umi dokazovat aspon neco ve vyrokove a predikatove logice a zneni vet, tak ten mel problem :( Trochu me mrzelo, ze cviceni byly uplne k nicemu, resp. na pisemce clovek nepouzil vubec nic.... Zbyva jen doufat.

Ja jsem zase byl skupina B, tak si zkusim vzpamatovat nektere z prikladu:

1. Dokazte
   a) |- A-> ((A->B)->B)
   b) A |= B prave kdyz |= A->B

2. Necht T a S jsou teorie. Necht pro kazdou formuli A ktera patri do S plati T |- A, a necht plati TuS |- B. Dokazte, ze potom plati T |- B.

3. Stejne jako 3. v predchozim prispevku

4. a) Definujte uplnou teorii
   b) Necht T je bezesporna teorie nad jazykem L. Necht pro libovolny model M teorie T mame mnozinu Thm(M) = {A | A je uzavrena a je pravdiva v M}
   Dokazte ze Thm(M) je uplna teorie ktera je rozsirenim teorie T se stejnym jazykem L.

5. Rikame, ze teorie je uzavrena jestlize vsechny jeji axiomy jsou uzavrene. Je mozne rozsirit kazdou teorii na uzavrenou? Pokud ano, dokazte, jinak uvedte protipriklad.

6. Dokazte v Peanove aritmetice
   a) (Vx)(x+0 = 0+x)
   b) (Vx)(Vy)(Vz)((x+y)+z = x+(y+z))

Psal jsem tam uplne vsechno co me napadlo, jen aby papiry nezustaly prazdne. Asi to moc neuskodi :-) a tak ted doufam, ze ten co to bude opravovat tam najde aspon tech 23 bodu...
Osobne se mi zda, ze moje skupina byla trochu lechci nez ta druha, ale nerad bych o tom mluvil nez se dozvim vysledek...
Tak, dobrou noc, a doufejme, jeste lepsi rano...

Ja uz mam i vysledek :) 2...