- 1. An enumeration of the logical symbols.
- 2. A description of the non-logical symbols.
- 3. A syntactic definition of the form of a sentence.

Let G be a set of sentences in the propositional calculus and let P be a sentence. P is a

- A. Every valuation that satisfies every sentence in G also satisfies P.
- B. Some valuation both satisfies every sentence in G and also satisfies P.
- C. Every valuation that satisfies P also satisfies every sentence in G.
- D. Every valuation that satisfies any of the sentences in G also satisfies P.
- E. Every valuation that satisfies P also satisfies at least one of the sentences in G.

** Solution: ** A.

- A. P V Q.
- B. P V S.
- C. ~P V Q
- D. ~P V ~Q V R.
- E. ~P V ~Q V ~R.

New set of clauses (S1):

- A. P V Q.
- C. ~P V Q
- D. ~P V ~Q V R.
- E. ~P V ~Q V ~R.

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. Q
- D. ~Q V R.
- E. ~Q V ~R.

New set of clauses:

- D. R.
- E. ~R.

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. Q.

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

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:

- i. Joe speaks English, but Pierre speaks French.

Answer: s(j,e) ^ s(p,f). - ii. If X and Y both speak L, then X and Y can communicate.

Answer: forall(X,Y,L) s(X,L) ^ s(Y,L) => c(X,Y). - iii. If W can communicate both with X and with Y, then
W can serve as an interpreter between X and Y.

Answer: forall(W,X,Y) c(W,X) ^ c(W,Y) => i(W,X,Y). - iv. For any two languages L and M, there is someone who speaks both
L and M.

forall(L,M) exists(X) s(X,L) ^ s(X,M). - v. Marie can speak both English and French.

s(m,e) ^ s(m,f). - vi. Marie can interpret between Joe and Pierre. i(m,j,p).

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.

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.