CS 486 Applied Logic Assignment #4
Spring 1997 Due Date: Thurs., 2/20/97

Reading: Please read Smullyan Chapter IV for Tuesday and Chapter V §1, 2.
Estimated Time: less than 6 hours

1. Boolean Rings
   1. A Boolean ring is a ring (with unit) such that for all . Show that any Boolean ring is commutative, i.e. for all .

      Define as , as , and as .

      Take 0 as true and 1 as false .

      Show that with these definitions the class of propositons, Prop, is a Boolean ring. Use the truth definiton to prove properties of the logical connectives and constants.

   2. Show that in any Boolean ring.
   3. Translate these formulas into algebraic expressions over the Boolean ring and show that they reduce to .
      1. 
      2. 
      3. 
      4. The ``Golden Rule''
         (where is + of the Boolean ring)
2. Solve Exercise 2 in Smullyan p.50
3. Solve Exercise 3 in Smullyan p.50
4. Solve Exercise 3 in Smullyan p.52
5. A basic Horn clause is a formula of the form where each of is a propositional variable or its negation and is a variable, e.g. is a basic Horn clause.

   Let Prog be a conjunction of basic Horn clauses. Show that there is a polynomial time algorithm in the length of Prog to decide whether it is satisfiable.

6. Prove the first two examples of the exercise in Smullyan p.56.

• About this document ...