Homework 6: Symbolic Evaluation of Boolean Expressions

Due: Monday Friday, February 23Feburary 26, 20092010

Extra Credit

Overview

Write a Scheme function
reduce
that reduces boolean
expressions (represented in Scheme notation) to
simplified form. For the purposes of this assignment,
boolean expressions are Scheme expressions constructed from:

• the boolean constants true and false ;
• boolean variables (represented by symbols other than true, false, not,
  and, or, implies, and if=) that can be bound to either =true
  or false.
• the unary operator not .
• the binary operators and , or , and implies (denoted by the
  symbols and , or , and implies , respectively), and
• the ternary operator if .

The course staff is providing function parse and unparse (in the file
=6-parser.ss=) that convert boolean expressions in
Scheme notation to a simple inductively defined type called boolExp and vice=-versa. The
coding of parse and unparse is not difficult, but it is tedious (like most parsing) so
the course staff is providing this code rather than asking students to write it.

...

• a boolean constant true and false ;
• a symbol S representing a boolean variable;
• (make-Not X) where X is a boolExp ;
• (make-And X Y) where =X and Y are ={{boolExp=}}s;
• (make-Or X Y) where =X and Y are ={{boolExp=}}s;
• (make-Implies X Y) where =X and Y are =boolExp=s; or
• (make-If X Y Z) where X , Y , and Z are =boolExp=s.

...