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
(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.
Define the syntax of the propositional calculus. Your answer should include:
- 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.
(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:
- A. Every valuation that satisfies every sentence in G also satisfies
- B. Some valuation both satisfies every sentence in G and also satisfies
- C. Every valuation that satisfies P also satisfies every sentence in G.
- D. Every valuation that satisfies any of the sentences in G also
- E. Every valuation that satisfies P also satisfies at least one of
the sentences in G.
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.
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
D. Show how (vi) can be proven from (i), (ii), (iii) and (v) using backward