By the end of this chapter you should be able to:
- Define functional completeness and show by construction that NAND alone and NOR alone are each functionally complete.
- Convert a two-level AND–OR circuit into NAND–NAND, and a two-level OR–AND circuit into NOR–NOR, and justify each conversion with De Morgan's theorem.
- Apply bubble pushing to a multi-level circuit, and state the two rules that make it valid.
- Identify the single-literal product term that needs an extra inverter after conversion.
- Compare AND–OR, NAND–NAND, OR–AND and NOR–NOR implementations of the same function by gate count, gate inputs, levels of delay and packages.
- Explain from the series-parallel structure of static CMOS why a process favours NAND over NOR.
Every circuit in this course so far has been drawn with AND, OR and NOT gates, because that is what the algebra of Chapter 6 is written in. A silicon process and a component catalogue both push in a different direction. In CMOS the gate that comes out of the transistors naturally is an inverting one — a NAND or a NOR — and the non-inverting AND is that gate with an inverter bolted on, larger and slower than the thing it is made from. In the 74 series you can buy NAND gates with two, three, four or eight inputs, and OR gates with two.
It would be convenient if a design could be expressed entirely in whichever gate the technology gives away cheaply. It can, and this chapter proves it by construction, then shows the conversion rules that make the change of gate type cost nothing at all for a two-level circuit — the form that Chapters 8 and 9 have been producing all along.
1 Why a Single Gate Type Is Worth Having
Chapters 8 and 9 produced minimal expressions written in AND, OR and NOT. Those three operations are what the algebra is built from, and a set of operations from which every Boolean function can be constructed is called functionally complete. The set \(\{\text{AND}, \text{OR}, \text{NOT}\}\) is complete by construction: any function can be written as a sum of minterms, a minterm is an AND of literals, a literal is a variable or its NOT, and the sum is an OR.
Hardware does not care about that argument. What a fabrication process offers is a small number of physical structures that can be repeated across a wafer, and both of the families in Part 3 produce an inverting gate naturally and a non-inverting one only by adding an inverter to it. A CMOS AND gate is a NAND followed by an inverter, and is therefore larger and slower than the NAND it contains. Ordering a circuit from a catalogue tells the same story: the 74-series has NAND gates in every useful width — 7400 with four 2-input gates, 7410 with three 3-input, 7420 with two 4-input, 7430 with one 8-input — while OR appears only as the 7432, four 2-input gates and nothing wider.
So there is a practical question behind the algebraic one. If a design can be expressed entirely in NAND, or entirely in NOR, then it can be built from one part number, one cell in a standard-cell library, one repeated layout on a die. Spare gates in a package become usable for anything. Timing analysis simplifies, because every gate on every path has the same delay. The question this chapter answers is whether that is always possible, and what it costs when it is.
The answer has been acted on at some scale. The Apollo Guidance Computer of the 1960s was built from one circuit type only — a resistor-transistor logic package containing two three-input NOR gates — and about 5600 of them made the whole machine, arithmetic, memory control and all. There was nothing elegant about the choice; a single part could be tested, qualified and screened for reliability far more thoroughly than a catalogue of a dozen could, and a spacecraft is a place where that matters more than gate count. The same reasoning survives in a modern standard-cell library, where a handful of well-characterised cells are preferred to a wide variety of poorly characterised ones.
2 Universality by Construction
A gate is universal if AND, OR and NOT can all be built from copies of it alone; any function can then be built, because those three suffice. The proof for NAND and for NOR is a construction, and each takes three small circuits.
Start with NOT. Tie both inputs of a NAND together and feed them the same signal. By the idempotent law \(A \cdot A = A\),
so one NAND gate is an inverter. AND follows immediately: a NAND is an AND followed by an inversion, so inverting it again restores the AND, \(((AB)')' = AB\), at a cost of two gates. OR takes three, and is the step where De Morgan's theorem from Chapter 6 does the work:
Invert each input with one NAND apiece, then NAND the two results. The output NAND is behaving as an OR gate with inverted inputs, which is what De Morgan's theorem says a NAND is.
The NOR constructions are the exact duals. \((A + A)' = A'\) gives an inverter in one gate; inverting a NOR gives OR in two; and \((A' + B')' = A''\cdot B'' = AB\) gives AND in three.
NOT costs one gate, the same-family operation (AND from NAND, OR from NOR) costs two, and the opposite operation costs three. Since AND, OR and NOT are sufficient for any function, and each can be made from NAND alone or from NOR alone, either gate on its own is a complete logic family. No other two-input gate has this property except these two.
The last sentence is worth testing. AND is not universal, because no combination of AND gates can ever produce a 1 from all-zero inputs, so NOT is unreachable. OR fails for the mirror-image reason. XOR is more interesting: \(A \oplus 1 = A'\) gives an inverter if a constant 1 is available, but every XOR network computes the modulo-2 sum of some subset of its inputs, and no such sum equals \(AB\). XOR is linear over GF(2); AND is not, so XOR is not universal.
Building AND, OR and NOT separately and then wiring them together is the worst way to use a universal gate. The three-literal function \(F = A(B+C)\) would need three NANDs for the OR, two for the AND and nothing else — six gates and four levels of delay. Converting the whole two-level circuit at once, as the next section does, gives the same function in three gates and two levels. Universality tells you a NAND-only implementation exists; the conversion rules tell you how to get a good one.
3 AND–OR to NAND–NAND
A minimal sum of products is a two-level circuit: a rank of AND gates, one per product term, feeding a single OR gate. Converting it to NAND takes one line of algebra. Complement the expression twice, which changes nothing, and apply De Morgan's theorem to the inner complement:
The right-hand side reads: NAND the inputs of each product term, then NAND the results. The circuit that was two AND gates and an OR gate is three NAND gates, with the same two levels and the same delay.
Graphically the same step is bubble pushing. Put a pair of bubbles — two inversions in series, which cancel — on every wire between the AND outputs and the OR inputs. The bubble at the AND output turns it into a NAND. The bubbles at the OR inputs turn it into an OR-with-inverted-inputs, and De Morgan's theorem says that symbol is a NAND. Nothing has been changed and everything has become one gate type.
Chapter 8 minimised \(F(A,B,C,D) = \Sigma m(0,1,2,5,8,9,10)\) to
The AND–OR circuit is three AND gates of 2, 2 and 3 inputs feeding a 3-input OR, with four inverters producing \(A'\), \(B'\), \(C'\) and \(D'\). Replace every gate of the two-level part by a NAND of the same width:
Three 2-, 2- and 3-input NANDs feed a 3-input NAND. Evaluating the netlist over all sixteen input combinations reproduces the original minterm list exactly. The inverters can themselves be NANDs with their inputs tied, so the whole circuit is eight NAND gates and no other component.
Counting packages makes the practical case. The AND–OR version needs a 7408 for the 2-input ANDs, a 7411 for the 3-input AND, a 7404 for the inverters — and then a 3-input OR gate, which the catalogue does not contain, so two gates of a 7432 are cascaded and a third level of delay is added. The NAND version needs a 7400, a 7410 and a 7404: three packages, two levels, nothing improvised.
Every input of the output NAND must arrive already inverted, because the output gate is an OR with inverted inputs. A product term of two or more literals supplies its own inversion, since it comes from a NAND. A term of a single literal does not. For \(F = AB + C\) the correct NAND circuit is \(\big((AB)' \cdot C'\big)'\): the lone \(C\) must be passed through an inverter first. Wiring \(C\) straight into the output NAND produces \((AB)' \cdot C\) complemented, which is \(AB + C'\) — a different function, and one that a quick simulation catches but a quick glance does not.
4 OR–AND to NOR–NOR
The product-of-sums form of Chapter 8 is also two levels: a rank of OR gates, one per sum term, feeding a single AND. The dual argument converts it to NOR:
NOR the inputs of each sum term, then NOR the results. Every OR becomes a NOR and the output AND becomes an AND-with-inverted-inputs, which is the De Morgan form of a NOR.
The product-of-sums minimisation of the same function in Chapter 8 was
so the NOR–NOR implementation is
three 2-input NOR gates feeding a 3-input NOR, plus inverters for \(A'\), \(B'\), \(C'\) and \(D'\). Checked over all sixteen input combinations it gives the same seven minterms as the NAND circuit of the previous section, which is the point: the two implementations are the same function reached by two different minimisations.
| Implementation | Level 1 | Level 2 | Inverters | Gate inputs | 74-series packages |
|---|---|---|---|---|---|
| AND–OR | 3 AND (2, 2, 3) | 1 OR (3) | 4 | 14 | 7408 + 7411 + 7432×2 + 7404 |
| NAND–NAND | 3 NAND (2, 2, 3) | 1 NAND (3) | 4 | 14 | 7400 + 7410 + 7404 |
| OR–AND | 3 OR (2, 2, 2) | 1 AND (3) | 4 | 13 | 7432 + 7411 + 7404 |
| NOR–NOR | 3 NOR (2, 2, 2) | 1 NOR (3) | 4 | 13 | 7402 + 7427 + 7404 |
Read the table by columns rather than by rows. The level count is 2 in every case, so all four circuits have the same propagation delay through the logic proper, and adding the inverters makes it 3 for all of them equally. The gate-input count — the usual first-order measure of area, since a gate's size is set mostly by how many transistors its inputs demand — separates the sum-of-products implementations at 14 from the product-of-sums ones at 13, which is the Chapter 8 result that this particular function has a cheaper POS form showing up again in hardware. What the conversion never does is change the count: NAND–NAND matches AND–OR exactly, and NOR–NOR matches OR–AND exactly. Only the last column moves, and it moves in favour of the universal gate.
Two rules of thumb follow, and they are worth memorising because examiners are fond of them. A minimal sum of products goes to NAND–NAND; a minimal product of sums goes to NOR–NOR. Mixing them up — trying to force an SOP into NOR gates directly — produces a circuit that needs an inverter on every input and every output and is worth nothing.
In each case every gate of the two-level circuit is replaced by the single universal gate of the same width, and the function is unchanged. The number of gates, the number of gate inputs and the number of levels are all identical to the AND–OR or OR–AND circuit, so the conversion is free. Any term consisting of a single literal is the exception: it must be inverted before it reaches the second-level gate.
5 Bubble Pushing and Multi-Level Circuits
The pair-of-bubbles trick is not limited to two levels. Stated generally, bubble pushing is the graphical form of De Morgan's theorem and has two rules:
- A bubble on an output cancels a bubble on the input it drives. Two inversions in series are no inversion, so a bubble may be created or destroyed in pairs on the two ends of a wire.
- A bubble pushed through a gate changes the gate's shape. Moving the bubbles from a gate's inputs to its output turns an AND symbol into an OR symbol and an OR symbol into an AND symbol — the two De Morgan equivalents of the same physical gate.
A NAND therefore has two symbols: the AND shape with a bubble on the output, and the OR shape with bubbles on both inputs. They are the same gate, and choosing the one whose bubbles cancel against its neighbours is what makes a large NAND-only schematic readable. The convention in industrial drawings is to pick the symbol that matches the active level of the signal, so that an active-LOW enable arriving at a bubble reads as "asserted" rather than as "inverted".
Convert \(F = A(B + CD) + BC'\) to NAND gates. The circuit has four levels as written: \(CD\), then \(B + CD\), then the AND with \(A\), then the final OR with \(BC'\).
Work outwards from the output. The final OR of two terms is a NAND whose inputs are the complemented terms, so both \(A(B+CD)\) and \(BC'\) must arrive inverted — that is, each must be produced by a NAND. \(\big(BC'\big)'\) is one NAND fed with \(B\) and \(C'\). \(\big(A(B+CD)\big)'\) is one NAND fed with \(A\) and \(B + CD\), and \(B + CD\) is an OR, so it is a NAND fed with \(B'\) and \((CD)'\), the second of which is another NAND. The netlist is
| Gate | Inputs | Output |
|---|---|---|
| \(g_1\) | \(C, D\) | \((CD)'\) |
| \(g_2\) | \(B, B\) | \(B'\) |
| \(g_3\) | \(B', (CD)'\) | \(B + CD\) |
| \(g_4\) | \(A, g_3\) | \(\big(A(B+CD)\big)'\) |
| \(g_5\) | \(C, C\) | \(C'\) |
| \(g_6\) | \(B, C'\) | \((BC')'\) |
| \(g_7\) | \(g_4, g_6\) | \(F\) |
Seven NAND gates, checked exhaustively against the original expression over all sixteen input combinations. The AND–OR version needs five gates — two ANDs, an OR, an AND and the output OR — plus one inverter for \(C'\), so six components in all. The conversion has cost one extra gate, the inverter \(g_2\) that produces \(B'\), which the AND–OR circuit never needed. If the complemented variables already exist, which they do whenever the inputs come from flip-flops with \(\overline{Q}\) outputs as in Chapter 21, only \(g_1, g_3, g_4, g_6, g_7\) are required: five NAND gates against five AND–OR gates, and the conversion is free again.
Reading such a schematic is a skill of its own. In a NAND-only drawing the bubbles alternate along every path, and a signal that is active-LOW at one point is active-HIGH at the next; the discipline is to label wires with the level at which they are asserted — \(\overline{RD}\), EN#, \(\overline{CS}\) — rather than trying to hold the inversions in your head. Where a bubble on a gate input meets a bubble on the driving output, the pair cancels and the signal can be read straight through, which is exactly the visual cue the convention is designed to give. Chapter 18 uses it throughout, because decoders and memory chips are almost entirely active-LOW devices.
That is the honest summary of multi-level conversion. Two-level conversion is free; multi-level conversion is free only where the required complements are already on the board. It is also why a synthesis tool asks whether a signal's complement is available before it decides how to map a piece of logic.
6 Why a CMOS Process Prefers NAND
NAND and NOR are equally universal and, on paper, equally cheap: the two-level conversions cost the same number of gates. In silicon they are not equal, and the reason is worth understanding now because Chapter 14 builds on it.
A static CMOS gate is a pull-up network of PMOS transistors between the supply and the output and a pull-down network of NMOS transistors between the output and ground, and the two networks are duals. In a NAND the pull-down NMOS transistors are in series and the pull-up PMOS transistors are in parallel. In a NOR it is the other way round: the PMOS transistors are stacked in series.
That difference matters because holes are less mobile than electrons — by a factor of about 2.5 in silicon — so a PMOS transistor must be roughly 2.5 times as wide as an NMOS to carry the same current. Series transistors share the same current, so a stack of \(k\) of them must be widened by a further factor of \(k\) to keep the resistance and therefore the delay unchanged. Stacking is expensive, and the NOR stacks the expensive devices.
Take an NMOS of unit width as the reference and \(\mu_n/\mu_p = 2.5\), so a PMOS matching it is 2.5 units wide. Size both gates for the same worst-case drive as an inverter.
| Gate | Pull-down (NMOS) | Pull-up (PMOS) | Total width |
|---|---|---|---|
| Inverter | 1 × 1 | 1 × 2.5 | 3.5 |
| 2-input NAND | 2 in series, 2 units each | 2 in parallel, 2.5 each | \(2(2) + 2(2.5) = 9.0\) |
| 2-input NOR | 2 in parallel, 1 unit each | 2 in series, 5 units each | \(2(1) + 2(5) = 12.0\) |
The NOR costs 12 units of transistor width against the NAND's 9, a third more silicon for the same logical work, and it carries more capacitance on its internal node as well. At three inputs the gap widens: \(3(3) + 3(2.5) = 16.5\) for the NAND against \(3(1) + 3(7.5) = 25.5\) for the NOR, a factor of 1.55.
Hence the standard-cell libraries that synthesis tools map onto are built around NAND and inverters, wide NOR gates are avoided, and a designer who writes a wide OR in VHDL will find it implemented as NANDs and inverters anyway. The exception is a technology whose electrical asymmetry runs the other way: NMOS logic of the 1970s and some domino and pass-transistor styles favour NOR structures, and in an FPGA the question does not arise at all, because the logic is a look-up table and no gate type is preferred (Chapter 28).
7 Summary and Key Results
| Item | Result | Cost |
|---|---|---|
| NOT from NAND | \((A\cdot A)' = A'\) — inputs tied | 1 gate |
| AND from NAND | \(((AB)')' = AB\) | 2 gates |
| OR from NAND | \((A'\cdot B')' = A + B\) | 3 gates |
| NOT / OR / AND from NOR | \((A+A)'\), \(((A+B)')'\), \((A'+B')'\) | 1, 2 and 3 gates |
| SOP → NAND–NAND | Every AND and the output OR become NANDs | No change in gates, inputs or levels |
| POS → NOR–NOR | Every OR and the output AND become NORs | No change in gates, inputs or levels |
| Single-literal term | Must reach the second-level gate inverted | One inverter |
| CMOS NAND vs NOR | NAND stacks NMOS, NOR stacks the slower PMOS | 2-input NOR is 33 % wider; 3-input, 55 % |
8 Common Mistakes
In \(F = AB + C\) the term \(C\) has no NAND of its own to invert it, so it must pass through an inverter before the output gate. Connecting \(C\) directly gives \(\big((AB)'\cdot C\big)' = AB + C'\), which disagrees with the intended function on six of the eight input combinations and agrees only where \(AB = 1\). The two circuits look identical on a schematic; only the missing inverter distinguishes them.
A bubble is an inversion and cannot be created or destroyed singly. It may be added in pairs at the two ends of a wire, where the two cancel, or moved from the inputs of a gate to its output provided the gate symbol changes shape at the same time — AND becomes OR, OR becomes AND. Sliding a bubble from an input to an output while leaving an AND drawn as an AND is simply an error in De Morgan's theorem.
Universality says a NAND-only implementation exists, not that it is cheapest. For a two-level circuit it costs nothing, but a multi-level conversion can add inverters wherever a complemented variable is needed and not available, as the seven-gate example in this chapter shows against five gates in AND–OR form. Count the gates for the specific function rather than assuming the answer.
9 Chapter Review
1. Build a NOR function using NAND gates only. How many are needed?
\((A+B)'\) is the OR construction followed by an inverter. Two NANDs invert \(A\) and \(B\), a third NANDs the results to give \(A + B\), and a fourth with its inputs tied inverts that: four NAND gates, verified over all four input combinations. The dual holds as well — a NAND takes four NOR gates — which is a reminder that mixing the two universal gates in one design wastes silicon in both directions.
2. Convert \(F = (A+B)(C+D')(B+E)\) to a NOR-only circuit and count the gates.
The expression is already a product of sums, so it maps straight onto NOR–NOR: \(F = \big((A+B)' + (C+D')' + (B+E)'\big)'\). That is three 2-input NOR gates feeding a 3-input NOR, plus one inverter for \(D'\) — which is itself a NOR with its inputs tied. Five NOR gates, two levels of logic after the inverter, and the netlist was checked against the original expression over all thirty-two input combinations.
3. A student implements \(F = AB + C\) as a NAND fed by \(A\) and \(B\), whose output goes with \(C\) into a second NAND. Which input combinations come out wrong?
The circuit computes \(\big((AB)' \cdot C\big)' = AB + C'\). Comparing with \(AB + C\) over the eight combinations, the two disagree wherever \(AB = 0\) and \(C\) distinguishes them: at \(ABC = 000, 010, 100\) the circuit gives 1 instead of 0, and at \(001, 011, 101\) it gives 0 instead of 1. Six of eight rows are wrong; the fix is an inverter on \(C\).
4. Why is XOR not a universal gate, even though \(A \oplus 1 = A'\) provides an inverter?
Every network of XOR gates computes the modulo-2 sum of some subset of its inputs, possibly plus a constant — an affine function over GF(2). AND is not affine: \(AB\) cannot be written as \(a_0 \oplus a_1A \oplus a_2B\) for any choice of constants. Since AND is unreachable and AND is needed for functional completeness, XOR is not universal. NAND and NOR are the only two-input gates that are.
5. Using an NMOS of unit width and \(\mu_n/\mu_p = 2.5\), compare the transistor width of a 3-input NAND with that of a 3-input NOR, and say what follows for cell library design.
The NAND has three NMOS in series, each widened by three to \(3\) units, and three PMOS in parallel at \(2.5\) units each: \(3(3) + 3(2.5) = 16.5\). The NOR has three NMOS in parallel at 1 unit and three PMOS in series, each widened by three to \(7.5\) units: \(3(1) + 3(7.5) = 25.5\), a factor of 1.55 more. Libraries therefore offer wide NANDs and inverters but rarely a NOR of more than two or three inputs, and a wide OR written in HDL is synthesised as NANDs and inverters.