# NAND

*The universal gate*

A NAND gate outputs 0 only when both of its inputs are 1, and 1 in every other case. It is called universal because every other logic gate can be built from NAND gates alone.

Group: Gates
URL: https://digiwleea.wleeaf.dev/learn/nand/

Time to run the recipe from [designing gates](https://digiwleea.wleeaf.dev/learn/designing-gates/) on a two-input gate. You will read the truth table, place the NMOS pull-down for the `0` rows, and mirror it with the PMOS pull-up. Same [CMOS](https://digiwleea.wleeaf.dev/learn/cmos/) skeleton as the inverter, just two transistors in each network instead of one.

**NAND** stands for NOT-AND: it does an AND and then inverts the result. Its output is `0` only when both inputs are `1`, and `1` in every other case.

| A | B | F |
| --- | --- | --- |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

_The single 0 sits in the row where both inputs are 1._

> **KEY:** NAND is **universal**: wire up enough NANDs and you can reproduce NOT, AND, OR, XOR, and from there any logic at all. That is why chips lean on it, and why this course builds nearly everything else from the NAND you make here.

> **TIP:** An analogy for the behavior: picture a machine with two **safety interlocks** and a warning lamp. The lamp stays on (`1`) as long as *anything* is unsafe, and only goes dark (`0`) when **both** interlocks are engaged at once. "Off only when both are on" is exactly NAND, and it is why NAND reads as "not (both)."

## Designing it from the truth table

Recall the rule: an NMOS conducts when its gate is `1`, a PMOS when its gate is `0`, and the pull-up and pull-down networks are always exact opposites, so exactly one is connected at a time. So read off when the output must be `0` versus `1`:

1. The output is `0` only when `A` and `B` are **both** `1`. To pull down only in that case, put the two NMOS **in series** (stacked): current reaches `GND` only when both gates are `1`. Series = AND.
2. The output is `1` whenever `A` **or** `B` is `0`. To pull up in either of those cases, put the two PMOS **in parallel**: either one conducting (gate `0`) connects the output to `VCC`. Parallel = OR.
3. Wire one input to one PMOS gate and one NMOS gate; wire the other input to the remaining pair. Series-down, parallel-up: that is a NAND.

```
F = NOT (A AND B)
```

_Circuit diagram: Two PMOS in parallel pulling up, two NMOS in series pulling down. A and B each drive one of each. Open it in the lab and confirm only A=B=1 pulls the output low._

> **TIP:** Notice the pattern you can reuse for any gate: **series transistors = AND-like** (all must conduct), **parallel transistors = OR-like** (any can conduct). [NOR](https://digiwleea.wleeaf.dev/learn/nor/) is this same circuit with the two networks swapped. Hold onto that and you can derive every gate in this course by hand.

**Q (Try it):** Build NAND in the lab and sweep all four input rows. Then think structurally: which is in **series**, the two NMOS or the two PMOS? Why does that give a `0` only when both inputs are `1`?

**A:** The two **NMOS** are in series (stacked). Current reaches `GND` only when *both* NMOS conduct, which needs both gates at `1`, so the output is pulled low only in the `A = B = 1` row. The two PMOS are in parallel, so any input being `0` pulls the output high. Series down, parallel up: that is NAND.

> **KEY:** Keep this part close. The very next gate ([AND](https://digiwleea.wleeaf.dev/learn/and/)) is just this one with a [NOT](https://digiwleea.wleeaf.dev/learn/not/) on its output, and the ALU that does your CPU's arithmetic is, underneath, a wall of gates exactly like this.

## Building any circuit from NAND alone

Earlier we called NAND **universal**. Here is the mechanical way to make good on that promise, and why chip designers bother. In CMOS a NAND is **four transistors**. A plain [AND](https://digiwleea.wleeaf.dev/learn/and/) is a NAND with a [NOT](https://digiwleea.wleeaf.dev/learn/not/) bolted on its output, so **six** transistors, and now the signal crawls through two stages instead of one. Building a whole circuit out of NAND (and its mirror [NOR](https://digiwleea.wleeaf.dev/learn/nor/)) is therefore both smaller and faster than building it from AND and OR. Two tricks make it possible: pull a NOT out of a NAND, and rewrite an ordinary AND-OR circuit as all NANDs.

## A NOT from a NAND

Give a NAND the **same wire on both inputs** and it becomes an inverter. Feeding `A` to both inputs, the gate computes `A NAND A`, which is `NOT (A AND A)`. Since `A AND A` is just `A`, that is `NOT A`. Tying one input **high** works too: `A NAND 1` is `NOT (A AND 1)`, and `A AND 1` is `A`, so again `NOT A`.

| A | A NAND A |
| --- | --- |
| 0 | 1 |
| 1 | 0 |

_Both inputs share one wire, so the gate only ever sees A NAND A, which is exactly NOT A._

## From an AND-OR circuit to all NANDs

Any function written as a **sum of products** (see [truth tables](https://digiwleea.wleeaf.dev/learn/truth-tables/), or [Karnaugh maps](https://digiwleea.wleeaf.dev/learn/karnaugh/) for the minimal one) is a two-level circuit: one AND gate per product term, all feeding a single OR gate. To turn that AND-OR shape into pure NAND you push **inversion bubbles** around, using one fact and one law.

A **bubble** on a wire means invert. Put **two** bubbles on the same wire and they cancel: inverting twice returns the original signal (`NOT (NOT x)` is `x`). So you may drop a cancelling pair of bubbles onto any wire without changing what the circuit computes. That freedom is the whole trick.

1. Start from the two-level AND-OR circuit: the AND gates on the left, their outputs feeding one OR gate on the right.
2. On each wire between an AND output and the OR input, add a **pair** of bubbles, one at the AND's output and one at the OR's input. Two bubbles per wire cancel, so the function is untouched.
3. Absorb each output bubble into its AND gate. An AND gate with a bubble on its output **is** a NAND. The whole first level is now NAND gates.
4. Absorb the input bubbles into the OR gate. An OR gate with a bubble on every input equals a NAND, because [De Morgan's law](https://digiwleea.wleeaf.dev/learn/boolean-algebra/) says `(NOT p) OR (NOT q)` is `NOT (p AND q)`, which is exactly what a NAND computes. The second level is now a NAND too.
5. Nothing is left but NANDs, and the output still computes the original sum of products. In short: **replace every AND and the final OR with a NAND, and change nothing else.**

## Worked example

Take a two-term function (`A'` means `NOT A`):

```
F = (A AND B) OR ((NOT A) AND C)
```

As an AND-OR circuit it is two AND gates, one for `A AND B` and one for `(NOT A) AND C`, feeding one OR gate. Now apply the rule: swap each AND and the OR for a NAND. The first product becomes `G1 = A NAND B`. The second needs `NOT A` first, which is a NAND with its inputs tied (`A NAND A`), then `G2 = (NOT A) NAND C`. The OR becomes the final gate `F = G1 NAND G2`. Four NANDs, nothing else:

```
F = (A NAND B) NAND ((A NAND A) NAND C)
```

| A | B | C | A' | G1 | G2 | F |
| --- | --- | --- | --- | --- | --- | --- |
| 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 |

_A' is A NAND A; G1 and G2 are the first-level NANDs; F is the second-level NAND. Every F cell matches A·B + A'·C, so the all-NAND circuit computes the original sum of products. (This function is the 2-to-1 multiplexer: F follows C when A is 0, and B when A is 1.)_

> **WARN:** Doing this by hand, three slips are common. Bubbles must go on in **cancelling pairs**: one stray bubble (an odd count on a wire) inverts the function. The trick assumes a clean two-level **sum of products**, AND gates feeding one OR; a deeper tangle of levels needs bubble-pushing stage by stage, not one blind swap. And `NOT A` is not free: it costs a NAND of its own, so count it when you tally gates (a bare single-literal term like `C` likewise needs its own inverting NAND so the bubbles balance).

**Q (Try it):** Convert `F = A·B + C·D` into a NAND-only circuit, then check the row `A=B=1, C=D=0`.

**A:** Swap both ANDs and the OR for NANDs: `G1 = A NAND B`, `G2 = C NAND D`, `F = G1 NAND G2`. For `A=B=1, C=D=0`: `G1 = NAND(1,1) = 0`, `G2 = NAND(0,0) = 1`, `F = NAND(0,1) = 1`, which matches `A·B + C·D = 1 + 0 = 1`. By De Morgan the circuit equals `A·B + C·D` on every row.

**Spot the fault** (Float (Z)): A=1, B=Z, OUT=X. Look at B.

Input `B` was never wired, so its gate floats at `Z` rather than a real `0` or `1`. A floating CMOS input leaves both the pull-up and pull-down partly on, so the output is indeterminate (`X`), not a clean logic level. Every gate input must be driven by something; tie an unused input to a fixed `0` or `1` rather than leaving it open.

### FAQ

**Q:** What is a NAND gate?

**A:** A NAND (NOT-AND) gate outputs `0` only when both of its inputs are `1`, and `1` in every other case. It does an [AND](https://digiwleea.wleeaf.dev/learn/and/) and then inverts the result.

**Q:** Why is NAND called a universal gate?

**A:** Because every other logic gate can be built from NAND gates alone: NAND alone reproduces [NOT](https://digiwleea.wleeaf.dev/learn/not/), [AND](https://digiwleea.wleeaf.dev/learn/and/), [OR](https://digiwleea.wleeaf.dev/learn/or/), and [XOR](https://digiwleea.wleeaf.dev/learn/xor/), and from those any logic function at all. That is why real chips lean on it.

**Q:** How do you build a NAND gate from transistors?

**A:** Put two NMOS transistors **in series** as the pull-down (output goes `0` only when both inputs are `1`) and two PMOS transistors **in parallel** as the pull-up (output goes `1` whenever either input is `0`). Series-down, parallel-up is a CMOS NAND, just four transistors.

**Q:** What is the difference between NAND and NOR?

**A:** They are topological mirrors. NAND outputs `0` only when **both** inputs are `1` (parallel PMOS up, series NMOS down); [NOR](https://digiwleea.wleeaf.dev/learn/nor/) outputs `1` only when **both** inputs are `0` (series PMOS up, parallel NMOS down). Both are universal.

**Q:** How do you make a NOT gate from a NAND gate?

**A:** Tie both inputs of the NAND to the same wire. The gate then computes `A NAND A`, which is `NOT (A AND A)`, and since `A AND A` equals `A`, the output is `NOT A`. Tying one input high works too: `A NAND 1` is also `NOT A`.

**Q:** How do you convert an AND-OR circuit into NAND gates?

**A:** Write the function as a sum of products (AND gates feeding one OR gate), then replace every AND gate and the final OR gate with a NAND gate and change nothing else. Adding a cancelling pair of inversion bubbles on each wire between the two levels leaves the function unchanged, and [De Morgan's law](https://digiwleea.wleeaf.dev/learn/boolean-algebra/) turns the bubbled OR into a NAND, so the result is an all-NAND circuit computing the same function.