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

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.

Attachments:

• zktest6.pdf