June 28, 1999

Due at start of lecture, Wednesday July 7, 1999

Write a scheme function "simplify" that simplifies boolean
expressions. It should accept a boolean expression in Scheme,
consisting of the constants `#t` and `#f`, symbols
(representing variables), and expressions constructed using the
functions "and", "or", and "not". For the basic problem you can assume
that "and" and "or" have exactly two arguments. The simplify function
should return a new expression (i.e. a Scheme s-expression) that is the
simplified form.

To do this, "simplify" converts any occurrence of an expression below to its shorter equivalent (the order of arguments in binary operators may be swapped):

(and x x) => xIn the rules above,

(and x #t) => x

(and x #f) => #f

(and x (not x)) => #f

(and x (or x y)) => x

(or x x) => x

(or x #f) => x

(or x #t) => #t

(or x (not x)) => #t

(or x (and x y)) => x

(not (not x)) => x

(not #f) => #t

(not #t) => #f

(simplify '(or #t #f)) => #t

(simplify '(or x (not y))) => (or x (not y))

(simplify '(and x #t)) => x

(simplify '(and (or x y) (or x y))) => (or x y)

(simplify '(or x (and (or x x) y))) => x

(simplify '(or (and x x) (and x x))) => x

Hints: think recursively! In what order should you apply the simplifications?

**Full credit will be given only to solutions that use proper
abstraction. Also you should not use any functions with side effects.**

Show that your code correctly handles the examples above as well as
these expressions:

(or (not #t) (or (not x) x))

(or (and #f x) (and (not z) z))

(or (and (or #t x) (or x x)) (not (or (and (not y) x) (not y))))

(and (and (or #f (and x x)) (and z (or z x))) (or (not w) w))

(not (and (or x (not y)) (not (and (not #f) (or x y)))))

Suppose the "or" and "and" operators take zero or more arguments (and not just two) with the obvious meaning.

Write a scheme function "normalize" that converts a boolean expression into
*disjunctive normal form,* that is,
a boolean expression with one "or" whose
arguments are "and"s. Each argument of the "and"s should be
either a variable or an expression "`(not var)`".
(The formula is two levels deep, one level for the "or" and the other level for the "and"s.)

For example, the formula `(or (and x y z) (and (not w)))` is in this form.

You will find the distributive and DeMorgan laws useful for this transformation:

[distributive laws]

(and x (or y z)) = (or (and x y) (and x z))

(or x (and y z)) = (and (or x y) (or x z))

[DeMorgan laws]

(not (or x y)) = (and (not x) (not y))

(not (and x y)) = (or (not x) (not y))

For example,

(and v (or w (and x (or y z)))) =

(and v (or w (or (and x y) (and x z)))) =

(and v (or w (and x y) (and x z))) =

(or (and v w) (and v (and x y)) (and v (and x z))) =

(or (and v w) (and v x y) (and v x z))

Demonstrate your code on the example above as well as the following:

(and (or x y) (or (not x) z) (or y z))

(and (or a (not b) c) (or a (not b)) (or a (not c) (not d)))

(and (or (and x y z) (not (or (and y z) (and (or x) z)))) (or (and q z) (not w)))

(not (or (or (and (or (and x) (not w)) (or q w)) (and a (or b c) c)) (or x w)))

You might want to include additional examples to show that your code
is working. Also, explain your algorithm completely. **The code alone
will not earn credit.**

To simplify the output slightly, an expression of the form `(and
expr)` should be replaced by just `expr`, and similarly for
`(or expr)`. Thus for example, you should output

(or x y)instead of

(or (and x) (and y))