Math 470 Spring ’05

HW #9 Solutions

Section 2.11

1. a) {y/b, w/b, x/g(a), v/g(a), w/c} All expressions become P(g(a), f(b), c).

b) {x/g(v), y/a, w/f(b). v/b} All expressions become Q(h(g(v), a), f(b)).

2. a) cannot unify a and c (neither is a variable)

b) cannot unify a and f(x) (neither is a variable)

3. Let s = {y/x} and l = {x/y).

Then xsl = y and xls = x.

Section 2.12

1. a) s1 = {x/y} s2 = {y/f(z)}. Result is {P(f(z),f(z))}.

b) s1 = {z/a} s2 = {y/a} s3 = {u/f(a)}. Result is {P(a,a,f(a)}

c) not unifiable. s1 = {x/y} or {y/x}. Either way, we cannot unify the second arguments.

d) The mgu is {x/a, y/g(a), z/a, u/g(a), v/g(a)}

e) Not unifiable. First we replace y by g(x) but then we cannot unify g(x) and f(u).

2. a) The mgu is { y/f(a), w/a, u/a, z/a).

b) Not unifiable . First w is replaced by a, but then we cannot unify a and b in the third argument.

Section 2.13

1. a) If we replace y by u and z by f(u) the resolvent is P(x,u). By renaming variables, this can be further resolved to the empty clause.

b) If we replace y by f(x) , the resolvent is {P(x,x), Q(f(x), z)}

c) We can change variables in the second clause to u, v (instead of x, z) and then substitute x for both u and v unify ØP(x,x) in the first clause with P(u,v) in the second.

The result is {P(x,y), Q(x, f(x), z), ØQ(f(x), x, x}.

No further resolution is possible.

3. Let D(x) = x is a dragon; S(x) = x sleeps in its cave; T(x) = x is tired; H(x) = x is hungry; F(x) = x hunts in the forest. Then we get

i) $x D(x) - Skolemize to D(a)

ii) "x (D(x) -> (S(x) v F(x). Get clause: ØD(x) v S(x) v F(x)

iii) "x( ( D(x) -> (H(x) -.> ØS(x))) Clause: ØD(x) v ØH(x) v ØS(x)

iv) "x (D(x) -> (T(x) -> Ø F(x))) Clause : ØD(x) v ØT(x) v ØF(x)

Resolving clause i) with each of the others (substituting a for x) gives

v) S(a) v F(a)

vi) ØH(a) v ØS(a)

vii) ØT(a) v ØF(a)

a) Resolving v) and vi) gives ØH(a) v F(a), equivalently H(a) -> F(a), so the dragon hunts in the forest when it is hungry.

b) Resolving v) and vii) gives ØT(a) v S(a), equivalently T(a) -> S(a), so the dragon sleeps in its cave when it is tired.

4. a) Let H(x) = x is a hero; F(x) = x is a failure, A(x,y) = x admires y. Then

i) "x"y (H(y) -> A(x,y)). Clause: ØH(y) v A(x,y)

ii) "x"y (F(x -> A(x,y)). Clause: ØF(x) v A(x,y)

iii) "x (ØH(x) -> F(x)). Clause: H(x) v F(x)

Resolution on ii) and iii) gives

iv) H(x) v A(x,y). Then substituting x for y and resolving on i) and iv)

v) A(x, x)

This shows that everyone admires himself (whether a hero or a failure).

5. Steps i) to v) as given.

vi) {ØQ(h(b) , w)} resolution on ii) and v) with v-> w

vii) {P(a, u, f(h(u))), H(u,a)} resolution on iv) and vi) with w -> b

viii) {P(a, u, f(h(u)))} resolution on v) and vii) with v -> u

ix) {H(x,a)} resolution on iii) and viii) with u->b, w ->b

x) empty clause resolution on v) and ix) with v -> x