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:

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

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

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:

Problem 3

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

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

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.