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, 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)) => #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))