## Study sheet for mid-term

The midterm will be given Wednesday, Oct. 15, for the entire class period. The exam is closed book and closed notes. It will cover:
• 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.

```

```

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

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

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