- Propositional Logic: R+N chapter 7 sections 7.1-7.4; the part of section 7.6 dealing with DPLL; and the handouts on propositional logic and the Davis-Putnam procedure.
- Predicate Calculus: R+N chapter 8; sections 9.1, 9.3, and 9.4; and the handout Inference in Datalog.

I will only ask about material that has been covered in lecture.
I will * not * ask about: (a) the situation calculus; (b) probability
theory;
(c) the material on advanced SAT engines that Prof. Barrett discussed;
(d) the cognitive science readings.

We will review for the midterm in class on Monday, Oct. 13.

You may be quite sure that the actual midterm will contain problems requiring you to work through an example of Davis-Putnam; to represent some sentences in the predicate calculus; and to work through some example(s) of forward or backward chaining.

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

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

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.
- iii. If W can communicate both with X and with Y, then W can serve as an interpreter between X and Y.
- iv. For any two languages L and M, there is someone who speaks both L and M.
- v. Marie can speak both English and French.
- vi. Marie can interpret between Joe and Pierre.

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

C. Explain why sentence (iv) cannot be expressed in Datalog.

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

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