[ENGN3213 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 19.

  

Figure 19: 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 20.

  

Figure 20: AND/OR implementation.

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

 

  

Figure 21: 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 21 is interpreted in mixed logic. This NAND gate implementation requires only one 74LS00 chip.

  

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

The circuit of Figure 21 is identical to Figure 22, 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 21.

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

[ENGN3213 Home]