[ENGN2211 Home]

Universality of NAND and NOR

We know that all boolean functions can be expressed in terms of AND, OR and NOT. In fact, all boolean functions can be expressed in terms of either

• NAND gates only, or
• NOR gates only.

To see this, let's show that NAND gates can be used to implement NOT, AND and OR. Algebraically, we have

$$\overline{(A \cdot 1)} = \overline{A}$$

so NAND can implement NOT. Next,

$$\overline{\overline{(A\cdot B)} \cdot 1)} = AB$$

giving AND.

Exercise. Using Boolean algebra, show how to obtain A+B from NAND gates.

The universality of NAND is illustrated in Figure 157.

  

Figure 157: Universality of NAND.

Exercise. Show how NOR gates can be used to implement AND, OR, and NOT.

Example. Implement the logic function

X = AB +CD

using a minimum number of NAND gates only.

We first implement as using AND and OR as shown in Figure 158.

  

Figure 158: AND/OR implementation.

This implementation requires two ICs. Next, we draw bubbles as shown in Figure 159.

 

  

Figure 159: NAND implementation showing mixed logic for easy reading.

The AND level clearly becomes a NAND level. But by De Morgan, the OR gate has become also a NAND gate. Between the two levels, we are using negative logic, and the bubbles are used to denote this. At the input side and also at the output side, we are using positive logic, and the absence of bubbles indicates this. So the circuit of Figure 159 is interpreted in mixed logic. This NAND gate implementation requires only one 74LS00 chip.

  

Figure 160: NAND implementation, positive logic only, harder to read.

The circuit of Figure 159 is identical to Figure 160, where we have explicitly drawn the second level NAND gate in positive logic form. This circuit is interpreted purely in positive logic, and the bubbles denote inversion. However, this circuit is harder to read than Figure 159.

So mixed logic can be helpful for implementation and for interpreting logic circuit diagrams.

[ENGN2211 Home]