1. Assignment 3:  Boolean Expressions

Objectives

• To build and traverse binary trees.
• To learn about manipulating boolean expressions.

 2 Boolean Expressions

A boolean expression is like an arithmetic expression except the operations are AND, OR, and NOT and the values are TRUE and FALSE. We will use the following notation.

AND        &

OR          |

NOT       !

TRUE      T

FALSE    F

In addition to these operations, we will use parentheses to nest operations. Some example Boolean expression are as follows.

• ! ( ( T  &  T  ) | F  )

• ( ( T  | F  ) &  ( T  | ( F     | !   T  ) ) )

These boolean expressions evaluate to either TRUE or FALSE. For example ! ( ( T & T  ) | F  ) evaluates to FALSE and

( ( T  | F  ) &  ( T  | ( F       | !   T ) ) ) evaluates to TRUE. In this assignment, you will evaluate boolean expressions.

The exact form of the boolean expressions we will work with can be specified with a grammar.

E → ( E & E ) E → ( E | E ) E → ! E

E → T E → F

Each line is called a substitution rule. Each corresponds to replacing an E in a string with the new string on the right side of the arrow. An expression is any string we can get to by starting with E and repeatedly applying the substitution rules until no Es remain.

We will also allow variables in the expressions. A variable will be represented by an integer. That is, we also have a rule (E→ (an integer)).

3. Expanding and Evaluating

The input will be a list of boolean expressions, one per line, where the first line is line 0. These expressions may contain variables, but line i may only contain variables numbered less than i. (This is to avoid infinite recursion.) Variable number k has a value equal to the expression in line k. You will compute an evaluation of the last expression in the list. You will also expand the expression into a single expression containing no variables by replacing the variables (recursively) into the last expression.

Input Example 1

T F

! ( 1  &  0 )

This example has three expressions. The last one evaluates to T. It gets expanded as ! ( F & T ).

Input Example 2

T F F T F

! ( 1  | 0 )

( ( 3  | 4  ) &  0 )

( ( ! 2  &  ! 5  ) | 6 )

This example has eight expressions. The last one evaluates to T. It gets expanded to

( ( ! F  &  ! ! ( F  | T  ) ) | ( ( T  | F  ) &  T    )

4. Removing Negations

De Morgan's Laws give a ways to negate simple Boolean expressions. They assert

!  (  E1   &  E2   )  =  (  !  E1   |  !  E2   ),

and

!  (  E1   |  E2   )  =  (  !  E1   &  !  E2   ).

You will use De Morgan's Laws along with the identities ! T = F, ! F = T, and ! ! E

= E to rewrite the final expanded expression without any NOT operations.

5. Project Specification

Although there are other ways to complete this project, please build a binary tree that repre- sents the boolean expression.

The input will be a list of boolean expressions with numerical variables as previously described. The output will be three lines, listing in order, the evaluation, the expansion, and the expansion without NOT operations.

Input/Output  Example 1

Input:

T F

! ( 1  &  0 )

Output:

Evaluation:       T Expansion:         ! ( F  &  T   )

Without Negation:    ( T  | F)

Input/Output Example 2

Input:

T F

F T F

! ( 1  | 0 )

( ( 3  | 4  ) &  0 )

( ( ! 2  &  ! 5  ) | 6 )

Output:

Evaluation:     T

Expansion:    ( ( ! F  &  ! ! ( F  | T  ) ) | ( ( T  | F  )    &  T  ) Without Negation:                         ( ( T  &  ( F  | T  ) ) | ( ( T  | F  ) &  T    )