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, x and y may be arbitrary boolean expressions. Here are some sample calls to the function simplify:
(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))