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 )