Your assignment is to write a LISP program that converts a predicate calculus expression into conjunctive normal form and attempts to simplify it. I will provide some test cases for you to use.

General discussion

Conjunctive normal form (CNF) is a way of writing expressions in the first-order predicate calculus. It uses only the logical operators and, or, and not. It does not use implies or any of the other logical operators.

An expression in CNF is a conjunction (and) of disjunctions (or). The disjuncts may be individual variables or Boolean constants (true or false), and may be negated (with not). More complex expressions are not allowed. That is, if an expression is in CNF,

1. not may only be applied to single variables or constants.
2. Variables and constants (possibly negated) may be ored together into disjuncts.
3. Disjuncts may be anded together (predicate calculus uses parentheses around each disjunct).
4. No deeper nesting is allowed.

For example, the following are in CNF:

• (a or b) and (b or not c or d) and (not a or not e)
• (a or true) and (b or not false or d)
• (a or b) and c and not d and (a or not e)
• a and b and c
• a or false or c
• not a
• not a and (b or c)

The following are not in CNF:

• (a and b) or (c and d) -- Cannot use or at a higher level than and.
• (a or b) and not(c or d) -- Can only apply not to single terms.
• (a or (b or c)) -- Too many levels of parentheses.

Any expression in the predicate calculus can be converted to CNF by applying the following rules.

1. Replace P implies Q with not P or Q
2. Use deMorgan's laws to move negations inward:
   1. Replace not(P and Q) with not P or not Q
   2. Replace not(P or Q) with not P and not Q
3. Distribute or over and. For example,
       Replace P or (Q and R) with (P or Q) and (P or R).
       Replace (P and Q) or (R and S) with (P or R) and (P or S) and (Q or R) and (Q or S).
4. Apply these rules as many times as necessary until the expression is in CNF.

Finally, simplify the resulting expression. Here are some simplifications you can use (you may think of some others):

• P and P --> P
• P or P --> P
• not not P --> P
• false and anything --> false
• true or anything --> true
• false or P --> P
• true and P --> P
• P or not P --> true
• P and not P --> false

Doing it in LISP

Use the names TRUE and FALSE as your constants, and the following operators:

• (AND ...) -- takes any number of arguments
• (OR ...) -- takes any number of arguments
• (NOT ___ ) -- takes exactly one argument
• (IMPLIES ___ ___ ) -- takes exactly two arguments

For example,
     (a or true) and (b or not false or d)
would be written in LISP as
     '(AND (OR A TRUE) (OR B (NOT FALSE) D))

You will be using the above constants and operators as data. LISP defines the constants T and NIL and the functions AND, OR, and NOT, and you will probably be using them, but don't get the LISP functions confused with the data that you are processing.

Here are some additional simplifications that are unlikely to occur in the expressions you are given, but may be helpful in writing the base cases in recursive functions:

(OR P) --> P	(or of a single value is just that value)
(OR) --> FALSE	(or with no arguments is false)
(AND P) --> P	(and of a single value is just that value)
(AND) --> TRUE	(and with no arguments is true)

There is a sample LISP program that you can look at for ideas. It is more complicated than your program needs to be, because it uses a "database" of rules. I want you to encode your rules directly in your LISP program ("hardwire" them)--this is less general, and your program will probably be longer, but it will be easier to write. Do not use a database of rules.

General suggestions for programming in LISP:

• It's much easier (and much more efficient) to work at the front of a list rather than at the back.
  
  
• Big functions are much harder to write than little functions. A LISP program typically consists of lots of little functions, rather than a few big functions. Whenever you can break one function into two simpler functions, it is almost always better to do so.
  
  
• Lots of functions means lots of function names. Think carefully about what you name each function, so that you don't get confused later on.
  
  
• Use a decent editor that helps with matching parentheses:
  • jEdit: put cursor anywhere within a group, hit control-[ repeatedly to extend the match.
  • PFE: put cursor anywhere within a group, hit control-shift-W repeatedly to extend the match.
  • TextPad: put cursor on or next to a parenthesis, hit control-M. (I don't know of a way to extend the match.)
    
    
• As always, good indentation helps.

Due date: July 19.
Turn in a floppy containing: Source code and the results of test runs. Include a readme.txt file only if you have something you need to tell the grader.