The discussion of transistor circuits in Section 6.4 illustrates a common characteristic. Because of the inherent way that transistors work, most circuits invert the signal. That is, a high voltage at the input produces a low voltage at the output and vice versa. As a result, an AND gate typically requires a NOT gate at the output in order to achieve a true AND operation.

We saw in that discussion that it takes fewer transistors to produce AND NOT than a pure AND. The combination is so common, it has been given the name NAND gate. And, of course, the same is true for OR gates, giving us a NOR gate.

NAND

A binary operator; the result is \(\binary{0}\) if and only if both operands are \(\binary{1}\text{,}\) otherwise the result is \(\binary{0}\text{.}\) We will use “\((x \cdot x)'\)” to designate the NAND operation. It is also common to use the ‘\(\uparrow\)’ symbol or simply “NAND.” The hardware symbol for the NAND gate is shown in Figure 6.5.1. The inputs are \(x\) and \(y\text{.}\) The resulting output, \((x \cdot y)'\text{,}\) is shown in the truth table in this figure.

\(x\)

\(y\)

\((x \cdot y)'\)

\(\binary{0}\)

\(\binary{0}\)

\(\binary{1}\)

\(\binary{0}\)

\(\binary{1}\)

\(\binary{1}\)

\(\binary{1}\)

\(\binary{0}\)

\(\binary{1}\)

\(\binary{1}\)

\(\binary{1}\)

\(\binary{0}\)

Figure6.5.1The NAND gate acting on two variables, \(x\) and \(y\text{.}\)

NOR

A binary operator; the result is \(\binary{0}\) if at least one of the two operands are \(\binary{1}\text{,}\) otherwise the result is \(\binary{1}\text{.}\) We will use “\((x + y)'\)” to designate the NOR operation. It is also common to use the ‘\(\downarrow\)’ symbol or simply “NOR.” The hardware symbol for the NOR gate is shown in Figure 6.5.2. The inputs are \(x\) and \(y\text{.}\) The resulting output, \((x + y)'\text{,}\) is shown in the truth table in this figure.

\(x\)

\(y\)

\((x + y)'\)

\(\binary{0}\)

\(\binary{0}\)

\(\binary{1}\)

\(\binary{0}\)

\(\binary{1}\)

\(\binary{0}\)

\(\binary{1}\)

\(\binary{0}\)

\(\binary{0}\)

\(\binary{1}\)

\(\binary{1}\)

\(\binary{0}\)

Figure6.5.2The OR gate acting on two variables, \(x\) and \(y\text{.}\)

The small circle at the output of the NAND and NOR gates signifies “NOT,” just as with the NOT gate (see Figure 5.1.3). Although we have explicitly shown NOT gates when inputs to gates are complemented, it is common to simply use these small circles at the input. For example, Figure 6.5.3 shows an OR gate with both inputs complemented.

\(x\)

\(y\)

\((x' + y')\)

\(\binary{0}\)

\(\binary{0}\)

\(\binary{1}\)

\(\binary{0}\)

\(\binary{1}\)

\(\binary{1}\)

\(\binary{1}\)

\(\binary{0}\)

\(\binary{1}\)

\(\binary{1}\)

\(\binary{1}\)

\(\binary{0}\)

Figure6.5.3An alternate way to draw a NAND gate.

One of the interesting properties about NAND gates is that it is possible to build AND, OR, and NOT gates from them. That is, the NAND gate is sufficient to implement any Boolean function. In this sense, it can be thought of as a universal gate.

First, we construct a NOT gate. To do this, simply connect the signal to both inputs of a NAND gate, as shown in Figure 6.5.4.

Next, we can use DeMorgan's Law (Equation (5.1.17)) to derive an AND gate.
\begin{align}
(x' + y')' &= (x')' \cdot (y')'\label{mrow-126}\tag{6.5.1}\\
&= x \cdot y\label{mrow-127}\tag{6.5.2}
\end{align}
So we need two NAND gates connected as shown in Figure 6.5.5.

Again, using DeMorgan's Law (Equation (5.1.17))
\begin{align}
(x' \cdot y')' &= (x')' + (y')'\label{mrow-128}\tag{6.5.3}\\
&= x + y\label{mrow-129}\tag{6.5.4}
\end{align}
We use three NAND gates connected as shown in Figure 6.5.6 to create an OR gate.

It may seem like we are creating more complexity in order to build circuits from NAND gates. But consider the function
\begin{gather}
F(w,x,y,z) = (w \cdot x) + (y \cdot z)\label{eq-nandandor}\tag{6.5.5}
\end{gather}
Without knowing how logic gates are constructed, it would be reasonable to implement this function with the circuit shown in Figure 6.5.7.

Next, comparing the AND-gate/NOT-gate combinations with Figure 6.5.1, we see that each is simply a NAND gate. Similarly, comparing the NOT-gates/OR-gate combination with Figure 6.5.3, it is also a NAND gate. Thus we can also implement the function in Equation (6.5.5) with three NAND gates as shown in Figure 6.5.9.

From simply viewing the logic circuit diagrams, it may seem that we have not gained anything in this circuit transformation. But we saw in Section 6.4 that a NAND gate requires fewer transistors than an AND gate or OR gate due to the signal inversion properties of transistors. Thus, the NAND gate implementation is a less expensive and faster implementation.

The conversion from an AND/OR/NOT gate design to one that uses only NAND gates is straightforward:

Express the function as a minimal SoP.

Convert the products (AND terms) and the final sum (OR) to NANDs.

Add a NAND gate for any product with only a single literal.

As with software, hardware design is an iterative process. Since there usually is not a unique solution, you often need to develop several designs and analyze each one within the context of the available hardware. The example above shows that two solutions that look the same on paper may be dissimilar in hardware.

In Chapter 8 we will see how these concepts can be used to construct the heart of a computer—the CPU.

Subsection6.5.1Exercises

1

Design a circuit using NAND gates that detects the “below” condition for two 2-bit values. That is, given two 2-bit variables \(x\) and \(y\text{,}\) \(F(x,y) = 1\) when the unsigned integer value of \(x\) is less than the unsigned integer value of \(y\text{.}\)

Give a truth table for the output of the circuit, \(F(x,y)\text{.}\)

Find a minimal sum of products for \(F(x,y)\text{.}\)