Foundations — Universal gates (NAND - NOR completeness)

Before you can appreciate why NAND is "universal", you must own every little symbol the parent note throws at you. We build them from nothing, in order, each one resting on the one before.

0. What is a "signal"? (the atom of everything)

Everything in digital logic is made of one thing: a wire that is either ON or OFF. We write these two states as numbers:

Why the topic needs it: the whole idea of "build every Boolean function" only makes sense because there are finitely many things a wire can be. Two states in, two states possible out — that finiteness is what lets us list every possibility in a table (next section).

1. Variables: $A$, $B$ — names for wires

A variable like $A$ or $B$ is just a name for one of these on/off wires. When we write $A$, picture a physical wire that right now is either 0 or 1.

Why the topic needs it: to say "build $F=A+B$" we need names for the input wires and the output wire so we can describe the rule connecting them.

2. The truth table: listing every possibility

Because each input is only 0 or 1, two inputs $A,B$ have exactly four possible combinations: $00,01,10,11$. A truth table writes down what the output does for every one of those rows — leaving nothing out.

Why the topic needs it: "functionally complete" literally means can produce any truth table. See Truth Tables for the full method. Every construction in the parent note is verified by checking its truth table matches the target.

3. The three basic rules: NOT, AND, OR

These are the three "classic" gates. Each is defined by a picture and a truth table.

Why the topic needs it: $\{\text{AND, OR, NOT}\}$ is the known complete set. The whole proof strategy is "if my one gate can rebuild these three, it inherits their completeness."

4. The overbar $\overline{}$ — the NOT symbol

The bar is just NOT written compactly. $\overline{A}$ = flip $A$. But it can sit over a whole expression:

Why the topic needs it: NAND and NOR are defined using an outer bar. And "invert the result of a NAND to get AND" is literally applying and removing a bar.

5. NAND and NOR — inverted AND / OR

Now we can read the two star symbols of the whole chapter.

The arrows $\uparrow$ (NAND) and $\downarrow$ (NOR) are just space-saving names — nothing magical. Read $A\uparrow B$ aloud as "$A$ NAND $B$".

Why the topic needs it: these two are the "magic bricks". Notice each already contains a NOT (the outer bar) — that free inversion is exactly why they turn out universal, and why plain AND/OR do not.

6. Idempotence: $A\cdot A=A$ and $A+A=A$

A rule you must trust before Step 1 of the parent note makes sense.

Why the topic needs it: tying both NAND inputs to the same wire gives $A\uparrow A=\overline{A\cdot A}=\overline{A}$ — that's how NAND makes a NOT. Without idempotence the step wouldn't simplify.

7. De Morgan's Laws — the bridge between AND and OR

The single most important tool in the parent note. It lets a bar "jump across" a group while swapping AND ↔ OR.

Rearranged (flip both sides), the version used for building OR from NAND is: $A+B=\overline{\overline{A}\cdot \overline{B}}$ Read this as: OR is nothing but "NAND of the two inverted inputs". That is the whole trick of Step 3. Full detail lives in De Morgan's Laws.

Why the topic needs it: NAND's native output is $\overline{AB}$ — an AND-shaped thing. To reach OR you must swap AND↔OR, and De Morgan is the only law that does that swap.

8. XOR — the "exactly one" gate (a bonus target)

The parent note builds this from 4 NANDs, so meet it now.

Why the topic needs it: it's the showcase example that "even a trickier rule needs only 4 copies of the one magic gate", which is why arithmetic circuits (adders) are built from NAND.

9. Monotonic — why AND and OR can't be universal

A last idea that powers the big "common mistake".

Why the topic needs it: a universal gate must be able to make NOT (an inversion). Since AND/OR are monotonic, they physically cannot — so only the inverting gates NAND/NOR qualify.

Prerequisite map

Equipment checklist

Test yourself — cover the right side.

Connections

• Boolean Algebra & Logic Gates — the parent field these symbols come from
• Universal gates (Hinglish)
• Truth Tables — how we verify every rule
• Logic Gate Symbols — the drawn shapes for these gates
• De Morgan's Laws — the AND↔OR bridge
• Duality Principle — the NAND↔NOR mirror
• Combinational Circuits — where these gates get assembled
• CMOS Transistors — the physical reason NAND/NOR are cheapest