Comp 212 Programming Assignment #1
Boolean Simplifier

Due 99.October.28 at 11:59 PM (Thursday night)

Introduction

The purpose of this assignment is to build a system of cooperating objects to simplify boolean expressions.  Such a program has application in digital logic.  The process of simplifying a boolean expression consists of the following steps.

1. Convert the boolean expression to a semi-normal form.   The definition of semi-normal form will be given in a subsequent section of this document..
2. Normalize the resulting semi-normal form.  The definition of normal form will be given in a subsequent section of this document..
3. Reduce the normalized form.  The definition of reduction will be given in a subsequent section of this document..
4. Deconvert the reduced form into the standard form.  The definition of deconversion will be given in a subsequent section of this document..

In this assignment, you are to write appropriate classes to carry out steps 1, 2, 3, and 4.  As a starting point, you must use the class design provided in the solution to questions 2 and 3 of homework 3.  Unless instructed otherwise, you are free to extend and modify this design as long as you do not change the names and the semantics of the given classes and their public methods.  At a later time, we will provide you with one or more classes that we will use to test your program.   These classes are capable of reading files containing an arbitrary number of boolean expressions and create appropriate boolean expressions objects specified in the aforementioned class design.  This is why you must not change the names and public methods of the classes that are given to you, unless instructed otherwise.  You will pay a 20% grade penalty if you do not follow this particular constraint.

Here is a sample input file.

(> z (| y z))

(> (| (! a) b) (> a b))

(& (| x y)(& (| x (! y))(& (| (! x) y)(| (! x) (! y)))))

Your program will be graded using a much larger and more demanding data file.

Conversion to Semi-Normal Form

A Semi-Normal Form is defined recursively as follows.

• A Variable object is in semi-normal form.
• A Constant object is in semi-normal form.
• A SNIf(test, conseq, alt) object is in semi-normal form, if test, conseq, and alt are in semi-normal form.

Variable and Constant objects are said to be atomic.

Examples.

1. Variable ("x") is in semi-normal form.
2. Constant (false) is in semi-normal form.
3. SNIf(SNIf(true, "y", "z"), "x", "w") is in semi-normal form.
4. SNIf(If(true, "y", "z"), "x", "w") is not in semi-normal form.  Why?

Define an interface called ISNForm, to represent objects in semi-normal form and an interface called ISNFVisitor, to represent visitors to ISNForm. Modify Variable and Constant to implement ISNForm.  Variable and Constant are thus simultaneously a ABooleanExp and a ISNForm.   This is an example of multiple inheritance.  Review chapter 4 of JPL for more details on multiple inheritance.  Define class SNIf to implement ISNForm as specified in the UML diagram below.  The method SNIf.equals (Object obj) is used to compare a SNIf with other objects for equality.   Checking for equality is needed in performs reduction and deconversion.  Since it makes sense to only compare objects of the same type, you may use instanceof to do type checking in this method.

Define a class called SNFConverter as an IBEVisitor to convert a ABooleanExp to an ISNForm.

Conversion to Normal Form

A Normal Form is defined recursively as follows.

• Atomic objects (i.e. Variable and  Constant objects) are in normal form.
• A SNIf(test, conseq, alt) object is in normal form, if test is atomic, and conseq and alt are in normal form, .

Examples.

1. Variable("x") is in normal form.
2. Constant(false) is in normal form.
3. SNIf(true, "x", "w") is in normal form.
4. SNIf(SNIf(true, "y", "z"), "x", "w") is not in normal form (why?).

Before we describe the normalization algorithm, we first describe a "helper" algorithm called "head normalization".  Head normalization is a ISNFVisitor whose host is either atomic (i.e. a Variable or a Constant), or a SNIf(test, conseq, alt)where all three components test, conseq, alt are in normal form.  Head normalization takes such a host and transforms it into an equivalent normalized ISNForm.  The algorithm for head normalization is based on the  logical formula: (? (?tt tc ta) c a ) == (? tt (? tc c a) (? ta c a))(can you see why?), and can be carried out recursively as follows.

• Case host is atomic: return the host.
• Case host is a SNIf(t, c, a) where t, c, a are in normal form:
  • Subcase t is atomic: return host;
  • Subcase t is a SNIf(tt, tc, ta) where tt is atomic and tc and ta are in normal form (why?): conseqNorm = head normalize SNIf(tc, c, a), altNorm = head normalize SNIf(ta, c, a), return SNIf(tt, conseqNorm, altNorm).

Normalization is a ISNFVisitor which makes use of the head normalization process.  We are now ready to describe the normalization algorithm.

• Case host is atomic: return the host.
• Case host is a SNIf (test, conseq, alt): testNorm = normalize test, conseqNorm = normalize conseq, altNorm = normalize alt , head normalize SNIf (testNorm, conseqNorm, altNorm).

Define an ISNFVisitor called Normalizer that takes a ISNForm host and transforms it into an equivalent ISNForm in normal form.  Define a ISNFVisitor called HeadNormalizer as an inner class of Normalizer to implement head normalization.  Make HeadNormalizer an inner class of Normalizer to ensure that head normalization is invoked with the appropriate input type.

The Flyweight Pattern

The process of "reducing"  and "deconverting" ISNForm objects involves comparing them for equality.  The specified method SNIf.equals (Object obj) is used for such a purpose.  The way Constant is designed, the built-in operator == will correctly compute equality for Constant objects, and as a result, the inherited equals method also computes correctly.  In order to compare Variable objects for equality using the built-in operator == (and consequently the inherited equals method),  we need a unique Variable object for each distinct variable name.  For example, there should be only one instance of a Variable object corresponding to the variable name "xyz".   This can be achieved by applying the "flyweight" pattern to the manufacturing of Variable objects.  In this pattern, Variable objects are said to be flyweights.  Modify the class Variable as shown in the following diagram.  The flyweight pattern will be covered in the lab.

In the above diagram,

• Variable._symbolTable and Variable.makeVariable (String name) are static.  Variable.makeVariable (String name)is called a "factory" method, and Variable is said to be a factory that manufactures its own instances.   Since the constructor Variable (String name) is private, no external clients can instantiate a Variable object.  The only way to obtain a Variable object is to call the static method Variable.makeVariable (String name.
• QFList and IAlgo constitute the quasi-functional list framework studied in class.  QFList serves as a "symbol table" where the pairs (name, Variable(name)) are stored.
• Class NameVarPair serves no other purpose than pairing a name with its corresponding Variable object..  As such, its fields are public and it has no methods

Reduction

Reduction is the process of  performing "symbolic evaluation" to transform SNForm objects to "simplest" form . Reduction is a ISNFVisitor which performs symbolic evaluation on its host by applying the following translation rules until no further reduction is possible:

(1)  (? T x y)  ->  x
(2)  (? F x y)  ->  y
(3)  (? V y y)  ->  y 
(4)  (? V T F)  ->  V 
(5)  (? V y z)  ->  (? V y[V=T] z[V=F]) 

The uppercase placeholder V stands for any Variable (as opposed to any constant or formula). The notation y[X=T] means y with all occurrences of the variable X replaced by the expression T.

If more than one rule matches the expression being evaluated, apply the rule that is nearest to the top of the list.

The symbolic evaluation process reduces every expression to "simplest" form, which is T for tautologies and F for contradictions. In principle, it can be accomplished by repeatedly applying the reduction rules shown above until no further change is possible. But there are much more efficient ways to accomplish the same process.

A simple but very effective algorithm is the following.

1. Design a class called NFEnvironment as an environment to bind pairs of Variables and their associated Constants.  It has two public methods:
   • SNForm lookup (Variable var) which returns the Constant associated with var if it exists, otherwise returns var itself;
   • void insert (Variable var, Constant val) which stores the pair (var, val) in this NFEnvironment.

   You can implement  NFEnvironment by composing it with a QFList.  This is an example of the "adapter pattern".

   

2. Do not actually perform the substitutions specified in the final rule. Build an environment (NFEnvironment object) recording the Constant value of the symbol for the consequent (or alternative) subexpression and evaluate the subexpression relative to this environment. In the course of symbolically evaluating the subexpression, look up the value of a Variable whenever you encounter it.
   
3. A Constant obviously reduces to itself.
   
4. A Variable reduces to its binding in the environment or to itself if it is unbound.
   
5. Do not try to reduce the subformulas of a SNIf object first before matching it against the available reduction rules with one critical exception: if the test expression is a Variable, you must look it up in the environment to see if it reduces to a Constant.
   
6. Try to match the rules in the order specified, taking into account the form of the "test" expression. If the test expression is a Constant, either rule (1) or (2) applies. If it is a Variable, rule (3) or (4) may apply. If rule 4 applies, no further simplification is possible. If rule 3 applies, the consequent subformula x must be reduced.
   
7. If none of the first four rules applies in reducing a SNIf object, the final rule always applies. To apply the final rule, recursively reduce the consequent and alternative subformulas x and y and then perform a final check to see if rules (3) and (4) can be used to perform one last simplification step.

Design an ISNFVisitor called Reducer that takes a ISNForm host and transforms it into an equivalent ISNForm in simplest form using the above algorithm.

Deconversion

Design an ISNFVisitor called DeConverter that translates ISNForm objects back to conventional boolean expression form (no if-then-else constructions are allowed) using the following rules:

(? a T F) --> a
(? a F T) --> (! a)
(? a b F) --> (& a b)
(? a F b) --> (& (! a) b)
(? a T b) --> (| a b)
(? a b T) --> (> a b)

where rules earlier in the list takes precedence over rules later in the list. Note that the rules must be applied recursively to translate the component expressions a and b.

Recommended Programming Strategy

When tackling a challenging programming problem, it is a good idea to solve a simplified version of the problem first. In this case, you might try writing a Reducer visitor class that implements all of the reduction rules except (5). You can later add the processing required to support rule (5) by passing a NFEnvironment as the input to each Reducer visitor.

Submission

Procedure for electronic submission will be announced later.  Stay tuned!