April 29,
1998

Due in quiz sections May 7, 1998

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)) => #tHints: think recursively! In what order should you apply the simplifications?

(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

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)))))

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))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.

(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)))

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))