Řešení písemné zkoušky z 29.1.

Výroková logika, normální tvary formulí, predikátová logika, věty o úplnosti výrokové a predikátové logiky, prenexní tvary formulí, modely teorií 1. řádu. Meze formální metody, Gödelovy věty.
Oracions
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 30. 1. 2014 16:18
Typ studia: Informatika Mgr.

Řešení písemné zkoušky z 29.1.

Příspěvek od Oracions »

Zadání v příloze.

1.
a) Ano, je splnitelný. Graf je třeba topologicky uspořádat, pak zdrojovým komponentám postupně dávat ohodnocení 0 a jejich opačným 1.
b) Jsou to dva modely, liší se jen hodnotou s.
c) Je jich 2^14, je to počet nadmnožin M(fi).
d) Ano. Každý model menší teorie lze "expandovat" na model větší teorie.

2.
a) To tablo bude nekonečné, stačí popsat, jak byste ho rozšiřovali dál.
b) Nosič bude {c,d,c1,c2,c3,...}, realizace P bude {(c,d),(d,d),(c1,d),(c2,d)...}
c) Například:
c1) Přidat axiom: Všechna x jsou v relaci se vším.
c2) Přidat axiom: Všechna x jsou v relaci s c, žádné x není v relaci s d.
c3) Přidat axiom: Žádné x není v relaci s c, všechna x jsou v relaci s d.
d) Stačí rozvinout R a Q podle jejich definice. Vyjde to: (P(x,c) AND NOT P(d,x)) OR (NOT P(y,d) AND P(c,y))

3.
a) Žádný kvantifikátor se nezmění na opačný. Všechny je zde stačí přesunout dopředu.
b) V první formuli přibude jeden funkční symbol, v druhé přibudou tři funkční symboly, z toho dva konstantní.
c) Lze například realizovat nové funkční symboly takto:
DELTA(u, epsilon) = epsilon (tím zaručíme splněnost prvního axiomu)
U() = 0
EPSILON() = 0.1
X(delta) = delta / 2 (teď mám sgn(U) = 0, sgn(X) <> 0, tedy jejich rozdíl bude 1 nebo -1, v absolutní hodnotě 1, což je více než 0.1.
d) Good luck, have fun. Ale 2 body jsem dostal už za převod do množinové reprezentace, nic víc jsem nestihl.
Přílohy
zktest6.pdf
(112.27 KiB) Staženo 688 x
Odpovědět

Zpět na „AIL062 Výroková a predikátová logika“