6.5 Boolean Algebra & Circuits

Given that a Boolean function can be used to represent any Boolean type quantity, then it must be possible to take a digital circuit and express it as a Boolean function. Representing a digital circuit as a Boolean function allows the circuit designer to simplify the circuit using the rules of Boolean algebra. The advantage of this approach is that it provides a mathematical means of obtaining the optimal circuit for a given function, leading to reduction in manufacturing and implementation costs.

The key to successful circuit simplification is essentially a three step process.

1.   Represent the circuit as a Boolean function.

2.   Simplify the Boolean function using the rules of Boolean algebra.

3.   Create the simplified circuit using the simplified Boolean function.

To create the Boolean function, label each output and each input of the gate using Boolean algebraic notation. The Boolean algebraic expression will increase in complexity when moving from the input to the output. This is to be expected. In this process AND gates will produce a Boolean product and OR gates will produce a Boolean sum. Other gates like XOR, NAND, and NOR need to be represented using AND, OR and NOT for this approach. Consider the process using the circuit in figure 6.9.

Based on the analysis shown in fig 6.9, it is seen that the end result expressed as a Boolean function should be F = x + y(x + y). Once the function is established then it could be simplified by using the rules of Boolean algebra, and the result recreated as a circuit.

To recreate a circuit from a Boolean expression, the reverse process needs to be applied. If the function F = y(x + y)(x + y) needs to be setup as a circuit, then the process is started with the number of inputs needed. In this case 2 inputs are needed, x andy. Using the same idea as in math, consider the contents within the brackets first. In this case the two OR operations are considered first. So the Boolean function could be represented as a circuit shown in figure 6.10

Now that a circuit can be represented as a Boolean expression and a Boolean expression can be represented as a circuit, simplification of circuits can be achieved by simplifying the Boolean expressions. To show how the whole process works, consider the circuit in figure 6.11. The truth table for the circuit is shown on the right to demonstrate the validity of the simplification process.

The circuit could now be expressed as a Boolean function using the process discussed earlier, resulting in:

F = x + y(x + y)

The validity of this expression could be determined by creating a truth table for the function and then comparing it with the truth table for the circuit. The truth table for the function is

The two truth tables, table 6.5 and the truth table in fig 6.11, are identical; therefore the function does represent the circuit.

The advantage of representing the circuit as a Boolean function is that it makes it easier to simplify the circuit, by simplifying the Boolean function. In this case, the function could be simplified as follows.

This simplification is easily arrived at using the rules of Boolean algebra, and the validity can be verified by using the truth table. Notice that column 3 and column 5 in the above truth table are identical. Therefore, the circuit in figure 6.11 could be simplified by using a single OR gate instead of the 3 gate arrangement of the initial circuit. When working with circuits it is difficult to see the simplifications that can be made, but when the circuit is expressed as a Boolean function then simplification becomes a relatively systematic task. This method of simplifying circuits using a Boolean function becomes a useful tool when the complexity of the circuit increases.

The number of inputs in the digital circuits does not change the process of simplification. For example consider the following case with 3 inputs x, y, and z.

The circuit could be converted into a Boolean function as F = x +(xy+z). This function could be simplified as follows.

This result indicates that instead of using 3 gates the function of the circuit could be accomplished using a single OR gate. This can be verified by using the truth table. x ORz will give the same output pattern as that of the last column.

Based on the discussions in this section it is easy to see the usefulness of Boolean algebra in the simplification process of circuit design. Boolean algebra provides a systematic mathematical approach to the simplification of digital circuits.

6.5 Practice Questions 1.     How does Boolean algebra help in digital circuit design? 2.     Describe the steps that are required to simplify a digital circuit? 3.     Create circuits using gates for the following Boolean expressions, and determine the output pattern of the circuit.         a.  x + x’y                          b.  (x + xy)’          c.  x’y              d. (y’ + x’)’ 4.     How can the validity of a simplification be verified? 5.     For the two input circuits shown below

        a. Represent the output as a Boolean function

        b. Simplify the Boolean function

        c. Express the simplified function as a digital circuit

6.    For the two input circuits shown below

        a. Represent the output as a Boolean function

        b. Simplify the Boolean function

        c. Express the simplified function as a digital circuit.