## Solutions to Sample Mid-Term

### Problem 1

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

### Problem 2

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:
• 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.

### Problem 3

Trace the workings of the Davis-Putnam algorithm in finding a valuation for the following set of clauses:
• A. P V Q.
• B. P V S.
• C. ~P V Q
• D. ~P V ~Q V R.
• E. ~P V ~Q V ~R.

#### Solution

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

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.
C is a singleton clause. Set Q = TRUE. Eliminate C, delete ~Q from D and E.

New set of clauses:

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

• i. Joe speaks English, but Pierre speaks French.
• 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.)

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.