Ř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.

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

Příspěvekod Oracions » 30. 1. 2014 16:33

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) 355 krát
Oracions
Matfyz(ák|ačka) level I
 
Příspěvky: 12
Registrován: 30. 1. 2014 16:18
Typ studia: Informatika Mgr.
Login do SIS: 99218475

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

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník