Solutions to Sample Mid-Term

Problem 1

Define the syntax of the propositional calculus. Your answer should include:

Solution

See Class notes on propositional logic

Problem 2

(Multiple choice: 1 correct answer)
Let G be a set of sentences in the propositional calculus and let P be a sentence. P is a consequence of G if and only if:

Solution: A.

Problem 3

Trace the workings of the Davis-Putnam algorithm in finding a valuation for the following set of clauses:

Solution

S is a pure literal so set S=TRUE and eliminate B.

New set of clauses (S1):

There are no pure literals and no singleton clauses.
Try setting P = TRUE.
Eliminate A. Remove ~P from C,D,E.

New set of clauses:

C is a singleton clause. Set Q = TRUE. Eliminate C, delete ~Q from D and E.

New set of clauses:

D is a singleton clause. Set R = TRUE. Eliminate D, delete ~R from E.
E is now the empty clause, so fail.

Return to S1, set P = FALSE. Eliminate C,D,E, delete P from A.

New set of clauses (S1):

A is a singleton clause. Set Q = TRUE. All clauses are satisfied. R may be assigned arbitrarily.

Answer: P=FALSE, Q=TRUE, R is arbitrary, S=TRUE.

Problem 4:

Consider a domain where the individuals are people and languages. Let Z be the first-order language with the following primitives:
s(X,L) --- Person X speaks language L. 
c(X,Y) --- Persons X and Y can communicate.
i(W,X,Y) --- Person W can serve as an interpreter between persons X and Y.
j,p,m,e,f --- Constants: Joe, Pierre, Marie, English, and French respectively.

A. Express the following statements in Z:

B. Show how sentences (i), (ii), (iii), (v), and (vi) can be expressed in Datalog. (Hint: Sentences (i) and (v) each turn into two facts in Datalog.)

Answer: 1. s(j,e).
2. s(p,f).
3. s(X,L) ^ s(Y,L) => c(X,Y).
4. c(W,X) ^ c(W,Y) => i(W,X,Y).
5. s(m,e).
6. s(m,f).
7. i(m,j,p).

C. Explain why sentence (iv) cannot be expressed in Datalog.
Answer: Because Datalog cannot express an existential quantifier.

D. Show how (vi) can be proven from (i), (ii), (iii) and (v) using forward chaining.

Answer: This was a poorly worded and poorly designed problem. I had not spoken in class about using forward chaining to prove a chosen result, just about running the forward chaining algorithm to derive all possible results. And in this case, forward chaining generates all kinds of uninteresting results, as we will see below. So what I will do here is give the forward chaining proof of (7) and then list all the other facts that can be derived by forward chaining, without including the proofs.

8. c(m,j). Combining (3) with (5) and (1), substituting X=m, Y=j, L=e.
9. c(m,p). Combining (3) with (6) and (2), substituting X=m, Y=p, L=f.
10. i(m,j,p). Combining (4) with (8) and (9), substituting W=m, X=j, Y=p.

Other facts that can be derived via forward chaining:
c(j,m).
c(j,j).
c(p,m).
c(p,p).
c(m,m).
i(m,j,j).
i(m,j,m).
i(m,m,j).
i(m,m,m).
i(m,m,p).
i(m,p,j).
i(m,p,m).
i(m,p,p).
i(j,j,j).
i(j,j,m).
i(j,m,j).
i(j,m,m).
i(p,m,m).
i(p,m,p).
i(p,p,m).
i(p,p,p).

E. Show how (vi) can be proven from (i), (ii), (iii) and (v) using backward chaining.

Answer:

Goal G0: i(m,j,p).  Match with (4) binding W1=m, X1=j, Y1=p.
   Subgoals G1: c(m,j). G2: c(m,p).
  
   Goal G1: c(m,j). Match with (3) binding X2=m, Y2=j.
      Subgoals G3: s(m,L2). G4: s(j,L2)

      Goal G3: s(m,L2). Match with (5) binding L2=e.
      G3 succeeds.

      Goal G4: s(j,e).  Match with (1).
      G4 succeeds.
   G1 succeeds.

   Goal G2: c(m,p). Match with (3) binding X3=m, Y3=p.
      Subgoals: G5: s(m,L3).  G6: s(p,L3).

      Goal G5: s(m,L3). Match with (5) binding L3=e.
      G5 succeeds.

      Subgoal: G6: s(p,e).  No match. G6 fails.

      Return to G5.
      Goal G5: s(m,L3). Match with (6) binding L3=f.
      G5 succeeds.

      Subgoal: G6: s(p,f). Match with (2).
      G6 succeeds.
  G2 succeeds.
G0 succeeds.