This is Due on Wednesday Night at midnight (Or Thursday if you got on extension.)

1 Explain what you did for the Wise-men problem in Homework 2.  What did you learn about theorem proving using resolution?

2 What is the relationship between Minsky's Frames and the frame problem?  Define both.

3 What were Minsky's criticisms of the logical approach?  Which have not been answered, and which were? Were the answers correct?

4 What is the complexity of propositional satisfiability?  First order satisfiability? Validity in monadic second order logic?  Validity in second order logic?

5 How could unification be extended to second order unification?  I.e. If you allow variables for functions, how can be unify two terms?

6 What is Deontic Logic?  What restrictions on frames corresponds to deontic logic?  What algorithm can be used to determine what restriction on frames corresponds to a particular modal logic? (Or invent an algorithm that does it)

7 Is description logic as expressive as first order logic?  Suggest a description logic that is as expressive as first order logic? Give an extension of description logic that is more expressive than first order logic?  Show how this extension can be modeled in another logic (Modal, Second order, etc.)

8 What fragment of first order logic does relational algebra translate to?  Is relational algebra complete for this fragment?  Could it be completed by adding extra equations?  

9 What is the relationship between multi-modal logics and description logics?  Are they equally expressive?  Give examples that separate them?

10 Axiomatize as much of Schubert's Steamroller as you can in description logic?

11 Are there sentences that are much quicker to prove in Gentzen systems than in resolution based systems? (Hint iff). Are there any advantages to Gentzen based systems, as compared with resolution?  What are the advantages of resolution?

12 Axiomatize the Yale Shooting problem in situation calculus, including frame axioms.  Give a proof that Fred dies after loading, waiting, and shooting.

13 Is Allen's event calculus complete?  How would you change Allen's 13 relations if you allow circular time, (time loops)?

14 What was Lewis's proposal for minimal entailment?  Can his proposal work for partial orders?  Define counterfactual.  

15 Is preferential entailment more expressive than circumscription?  Give a proof of equality of the equality of expressive power or a counter-example?

16 What is the expressive power of propositional circumscription?

17 What is cumulativity? If circumscription cumulative?  Is default logic cumulative?  Give examples.

18 How does Grove's semantics for Belief revision differ from Lewis's semantics for conditionals?  Define both.

19 What is Montague Lifting?  What is it purpose?  Write "I thought your yacht was longer than it is"  in logic.  What is the difficulty with representing this sentence?