6.4 Boolean Function  Simplification

A mathematical function, for example y=x², accepts a number and produces a new number based on the operator rules that are present in the expression. In the case of y=x² the operation is multiplication. Similarly, if a variable is defined as Boolean, then there exists the possibility of defining a Boolean function using Boolean variables and Boolean operators. The result of the Boolean function will also be Boolean, which means that the result of the Boolean function can have one of two possible states. For example, F = xy +y and F = xy +yz +x’z, would be examples of Boolean functions, but in both case F will also be Boolean.

This is similar to the normal algebraic idea of a function, but with multiple variables. A Boolean function with a single variable is of little or no use because the number of outcome possibilities for a single variable function is only two. The advantage of defining a process as a function is that it allows for simplification using the rules of Boolean operator.

Mathematical functions and algebraic expressions can have different forms that are mathematically equivalent. In mathematics such an expression is usually simplified to its simplest form to make specific computation easier. For example,

F(x)       = x² + 3x + 4x² + 2x

              = 5x² + 5x

              = 5x(x + 1)

The advantage of representing the function in a simplified form is that it speeds up the process of computation. Consider calculating F(5) using the initial expression and the simplified expression.

F(5)       = (5)(5) + 3(5) + 4(5)(5) + 2(5) = 150              Original expression

F(5)       = (5)(5)(5 + 1) = 150                                            Simplified expression

Using the original expression, the calculation required 8 operations to get the final result of 150. The simplified expression required 3 operations to get the final result of 150. Both produced the same result but the simplified expression required less work to obtain the same final result, thus making it much faster.

Like the above mathematical simplification, Boolean functions and expressions can also be simplified using the rules of Boolean operators discussed earlier. Like normal algebra, the first step to simplification is a good understanding of the Boolean operator rules. The Boolean operator rules are applied with the goal of reducing the number of terms. In Boolean algebra each variable or its complement is called a literal, so the goal in simplification is to minimize the number of literals in the final expression. For example, consider the following simplification of a Boolean function.

In this case the Boolean function in its original form required 7 operations, but in its simplified form it requires only 1 operation. If this function was implemented using gates, then 7 gates would be needed to perform the function using the original expression. On the other hand, if the simplified expression was used, then a single gate can be used to perform the same function. The reduced number of gates in the simplified expression reduces the cost of implementation by reducing the number of components required. The simplified implementation also provides an operational speed advantage. For each gate to perform its operation it takes a small but finite amount of time, therefore the processing time taken by a 7 gate system would be greater than the time taken by a single gate system.

The equivalence of the original form of the function to the simplified form can be verified by using a truth table. For example consider the following simplification.

The validity of the simplification can be verified using the truth table shown.

Notice that column 3 and 7 are identical. Therefore, xy + x(y+x) +y = x + y. This truth table result is to be expected because if each rule has been proven to work individually, then they should work in sequence one after the other.

The simplification of a Boolean function is of interest in hardware design because it reduces the cost of implementation and increases the speed. Each logical operation will ultimately require the use of a gate for its implementation. Therefore, the simplest Boolean form will give the minimum number of gates needed for implementation. If the number of gates used can be kept to a minimum then the cost of the implementation will also be kept to a minimum. The first step in simplification is to express the desired circuit as a Boolean expression. Once this done, then the Boolean expression could be simplified by using the rules of Boolean algebra. The simplified expression is then implemented as the final or production circuit.

6.4 Practice Questions 1.     Simplify the following two variable Boolean expressions where possible.         a. (x + y) . y                                     b. (x + y) . x         c. (x . y) + x                                     d. (x + y) + y      2.     Simplify the following three variable Boolean expressions where possible.         a. (x + y) . yz’                                  b. (x’ + yz) . zx                  c. (z . y) + (x + z)                            d. (x + z) (x + y) 3.     Using truth table show that x y’ + x’y is equivalent to the XOR operator.