Assigned: Mar. 5

Due: Mar. 26.

Let us say that a set S isnormalif S is not an element of S. Then there cannot exist a set of all normal sets.More formally,

There cannot exist a set S0 such that, for every set S, S is an element of S0 if and only if S is not an element of S.

Consider a first-order language L where the entities are sets containing the single predicate e(X,Y), meaning that X is an element of Y. State the above proposition in L and prove it using resolution. (Note: no axioms are needed.)

** Answer: **
The statement is

~ [exists(S0) all(S) e(S,S0) < = > ~e(S,S)].Negating and Skolemizing gives two clauses:

A. e(S,s0) V e(S,S) B. ~e(S,s0) V ~e(S,S)(s0 is a Skolem constant.) The proof is then as follows:

C. e(s0,s0). (Factoring A with substitution S=s0). D. ~e(s0,s0). (Factoring B with substitution S=s0). E. null. (Resolving A with B.)

1. forall(X,Y) a(X,Y) < = > p(X,Y) V [exists(Z) a(X,Z) ^ a(Z,Y)].Suppose that, in addition, we have the following axioms describing a family tree:

2. p(e,c).

3. p(c,w).

- A. Skolemize (1) above. Identify which of the resultant clauses are Horn clauses. Let H be the theory containing these Horn clause together with (2) and (3).
- B. Prove the statement "a(e,w)" from H using backward chaining.
- C. Prove the statement "a(e,w)" from H using forward chaining.

** Answer: **

A. Skolemizing (1) gives four clauses:

4. ~a(X,Z) V ~a(Z,Y) V a(X,Y). 5. ~p(X,Y) V a(X,Y) 6. ~a(X,Y) V p(X,Y) V a(X,sk1(X,Y)) 7. ~a(X,Y) V p(X,Y) V a(sk1(X,Y),Y)Clauses 4,5 are Horn; clauses 6,7 are not.

B. One backward chaining proof would be:

G0: ~a(e,w). (Negated goal) G1: ~a(e,Z) V ~a(Z,w). (G0+4). G2: ~p(e,Z) V ~a(Z,w). (G1+5). G3: ~a(c,w). (G2+2). G4: ~p(c,w). (G3+5). G5: Null (G4+3).

C. One forward chaining proof would be:

8. a(e,c) (2+5) 9. a(c,w) (3+5) 10. ~a(c,Z) V a(e,Z) (8+4) 11. a(e,w). (9+10) 12. Null (11+G0)

4. ~ exists(Z) p(w,Z).Let G be the statement "~ exists(Z) a(w,Z)." One might think that G is a consequence of H1. After all, if ancestor is the transitive closure of parent, and W is not anyone's parent then surely W is not anyone's ancestor. However, G is not a consequence of H1. Prove that G is not a consequence of H1 by constructing a model in which H1 is true and G is false. That is, you should list a set of parent and ancestor relations that satisfies H1 but not G. (Hint: this can be done using only the individuals e, w, and c.)

The moral is that first-order recursive definitions don't actually say everything that you would like them to say.

** Answer: **
There are many possible answers. One would be the following model.

p(e,c) p(c,w) a(e,c) a(e,w) a(c,w) a(w,w).This satisfies axiom 1; the condition a(X,Y) < = exists(Z) a(X,Z) ^ a(Z,Y) is satisfied for X=Y=w where Z is also equal to w. However it obviously violates G.