From a Boolean Expression to a Logic Circuit


Let’s examine the following Boolean expression:

A brief inspection shows that this expression is composed of two terms, AB and CDE, with a domain of five variables. The first term is formed by ANDing A with B, and the second term is formed by ANDing C, D, and E. The two terms are then ORed to form the output X. These operations are indicated in the structure of the expression as follows: 

Note that in this particular expression, the AND operations forming the two individual terms, AB and CDE, must be performed before the terms can be ORed.

To implement this Boolean expression, a 2-input AND gate is required to form the term AB, and a 3-input AND gate is needed to form the term CDE. A 2-input OR gate is then required to combine the two AND terms. The resulting logic circuit is shown in Figure 1. As another example, let’s implement the following expression:

Combinational Logic Analysis:

FIGURE 1: Logic circuit for X=5 AB+CDE.

A breakdown of this expression shows that the terms AB and (CD + EF) are ANDed. The term CD+ EF is formed by first ANDing C and D and ANDing E and F, and then ORing these two terms. This structure is indicated in relation to the expression as follows:

Before you can implement the final expression, you must create the sum term CD + EF; but before you can get this term; you must create the product terms CD and EF; but before you can get the term CD, you must create D. So, as you can see, the logic operations must be done in the proper order.

The logic gates required to implement X = AB(CD + EF) are as follows:

1. One inverter to form D

2. Two 2-input AND gates to form CD and EF

3. One 2-input OR gate to form CD + EF

4. One 3-input AND gate to form X

The logic circuit for this expression is shown in Figure 2. Notice that there is a maximum of four gates and an inverter between an input and output in this circuit (from input D to output). Often the total propagation delay time through a logic circuit is a major consideration. Propagation delays are additive, so the more gates or inverters between input and output, the greater the propagation delay time.

Unless an intermediate term, such as CD + EF in Figure 2, is required as an output for some other purpose, it is usually best to reduce a circuit to its SOP form in order to reduce the overall propagation delay time. The expression is converted to SOP as follows, and the resulting circuit is shown in Figure 3.

FIGURE 2: Logic circuits for X = AB(CD + EF) 

FIGURE 3: Logic circuits for X = ABCD + ABEF