zadania05.pdf

Zadania z

Konrad Zdanowski

22 stycznia 2006

1. Podaj form e logiczn a

•Zaden golibroda, nie goli tych, ktorzy gol a si e sami.

•Nikt nie lubi wszystkich tych, ktorzy go lubi a.

•Na pochyle drzewo wszystkie kozy skacz a.

•Wszyskie kangury nosz a w torbie po dwa pilniczki.

•Zadne dwa globostery, nie kolotkuj a si e nawzajem.

•Pewnych ludzi mozna oszukac zawsze, kazdego mozna oszukac cza-

sami, ale nie mozna zawsze oszukiwac wszystkich. [A. Lincoln]

2. Podaj MGU dla nast epuj acych zbiorow par termow (o ile istnieje).

•hg(w, f (x, h(w))), g(h(x), z)i,

hh(x), h(c)i,

hz, f (u, h(h(u)))i.

•hf (x, h(x, g(x))), f (h(z, z), w)i,

hh(z, g(w)), h(g(x), z)i.

•hp(x, f (y, w), z), p(f (y), z, x)i.

•hx + (y×f (z)), f (z) + wi.

•hp(f (x), g(y), z), p(y, z, g(x))i.

3. Rezolucja

•8x9y(8z P (y, z)_¬S(y, x)),8x9y¬P (x, f (y))|=8x9y¬S(y, x),

•|=8x9y(P (x, y) =)P (y, x)),

•8x9y8z(P (x, z)_P (y, z))|=8x9y(P (x, y)_P (y, x)).

4. Rozpisz warunek dla relacji spelniania. Np. M = (U, R) i M |=

8x9y¬P (x, y)[v] wtedy i tylko wtedy, gdy dla dowolnego a2U ist-

nieje b2U takie, ze (a, b) 62R. I podaj czy formula jest spelniona w

modelu.

•M = ({1, 2, 3}, R), R ={(a, b)2U 2 : a + b 3}.

Formula:9x8y¬P (y, x).

•M = ({1, 2, 3}, R), R ={(a, b)2U 2 : ab jest parzyste.}.

Formula:9x8y¬P (y, x).

•M = ({1, 2, 3}, R, F ), R ={(a, b)2U 2 : a + b 3},

F (1) = 2, F (2) = 3, F (3) = 1.

Formula:8x(9yP (y, f (x)) =)9yP (f (y), x)).