Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 57 ยท Logic Gates

Universal Gates and Gate Counts

Learn why NAND and NOR are universal gates, build NOT, AND, OR and XOR from NAND only and NOR only, and compare gate and transistor counts with live Python checks.

You have met seven gates so far: NOT, AND, OR, NAND, NOR, XOR and XNOR (see AND, OR and NOT Gates and NAND, NOR, XOR and XNOR). Do you really need all of them? No. A single kind of gate is enough to build every other one. Gates with this power are called universal gates, and NAND and NOR are the two universal gates.

This matters in practice. A factory that has to make millions of identical chips prefers one well-tuned building block over a zoo of different ones. In this lesson you will build each basic gate from NAND only, then from NOR only, count how many gates each construction costs, and prove with a Python checker that the results behave exactly like the originals.

What "universal" means

A set of gates is functionally complete when every Boolean function can be built from it. The classic set {AND, OR, NOT} is complete, because every truth table can be written as a sum of products (you will see this in Sum of Products and Product of Sums). So if a single gate can imitate NOT, AND and OR, that gate is universal too.

Why one gate is enough

Complete set AND, OR and NOT can build any function.
Imitate them If NAND can act as all three, NAND alone is complete.

NOR can do the same, with the roles of 0 and 1 swapped.

1 / 2

Everything from NAND

The NAND output is NOT (a AND b). Two small observations give you the whole toolbox.

  • NOT from NAND. Tie both inputs together: NAND(a, a) equals NOT a, because a AND a is just a.
  • AND from NAND. A NAND followed by a NOT undoes the inversion: AND(a, b) = NOT(NAND(a, b)).

Once you have NOT and AND, OR follows from De Morgan's theorem (covered in depth in De Morgan's Theorems and Bubble Pushing): a OR b = NOT(NOT a AND NOT b), which is NAND(NOT a, NOT b). XOR can be built from four NAND gates, and that is the smallest NAND-only version:

TEXT
m   = NAND(a, b)
XOR = NAND( NAND(a, m), NAND(b, m) )

Here is the full set in Python. The helper NAND counts how many times it is called, so you can see the gate cost of each construction. The check function compares a construction against a reference over every input combination, which is exactly what a truth table does.

Python Build every gate from NAND only

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every row says True, so the NAND-only versions are indistinguishable from the real gates. The cost column shows NOT = 1, AND = 2, OR = 3, XOR = 4, NOR = 4 and XNOR = 5 NAND gates. (The count is per evaluation, so a shared signal such as m in XOR is built once and counted once.)

Everything from NOR

NOR is the mirror image of NAND. Swap the roles of AND and OR, and of 0 and 1, and every construction carries over.

  • NOT a = NOR(a, a)
  • OR(a, b) = NOT(NOR(a, b))
  • AND(a, b) = NOR(NOT a, NOT b)
  • NAND(a, b) = NOT(AND(a, b))
  • XNOR(a, b) = NOR( NOR(a, n), NOR(b, n) ) with n = NOR(a, b), and XOR is that followed by a NOT.

The pairing between the two families is called duality: take a NAND-only circuit, replace every NAND by NOR and swap what you mean by 0 and 1, and you get the matching NOR-only circuit.

Now the live equivalence checker. It has a generic equivalent function that tries every input combination and, when two circuits differ, reports the first input where they disagree. It then checks the NOR-only versions.

Python Equivalence checker for NOR-only gates

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line shows how an equivalence checker earns its keep: it does not just say "wrong", it hands you an input where the circuits disagree, which is usually the fastest clue to what you forgot.

Gate counts and transistors

Why do real chips not use NAND for everything? Because "number of gates" is not the same as "cost". The real cost is the number of transistors, and in CMOS, the technology almost every chip uses, the cheapest gates are the inverting ones.

A CMOS gate has two halves that never conduct at the same time:

  • a pull-up network of PMOS transistors that connects the output to the supply (logic 1), and
  • a pull-down network of NMOS transistors that connects the output to ground (logic 0).

For a 2-input NAND, the two NMOS transistors sit in series (both inputs must be 1 to pull the output low) and the two PMOS transistors sit in parallel (either input at 0 pulls the output high). A NOR is the mirror image: NMOS in parallel, PMOS in series.

Inputs a, b Pull-down (NMOS in series) Pull-up (PMOS in parallel) Output
0, 0 off on 1
0, 1 off on 1
1, 0 off on 1
1, 1 on off 0

That is 4 transistors for a NAND2 or NOR2, and 2 for a NOT. An AND is a NAND followed by a NOT, so it costs 6 transistors, and an OR costs 6 as well. Non-inverting gates are always larger than inverting ones.

Python Transistor cost of NAND-only designs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

So the NAND-only version is a simplification of the toolbox, not the cheapest design. Real designs mix gate types. The big win for NAND-only (or NOR-only) is regularity: one cell, repeated, with predictable speed and layout. Also, engineers almost never build an AND-OR circuit with AND and OR gates. They use the NAND-NAND form, which is faster and smaller, and you will learn the trick in the next lessons.

CMOS gates are inverting because the output node is pulled by transistors that respond to the opposite input level: a high input turns an NMOS on and pulls the output low. A non-inverting gate needs an extra stage, which is why an AND is a NAND plus an inverter.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How do you make a NOT gate from a single NAND gate?

    NAND(a, a) is NOT (a AND a), which is NOT a.
  2. 2. Which set of gates is NOT enough to build every Boolean function?

    AND and OR are monotone, so they can never produce an output that falls when an input rises. Without NOT you cannot make an inverter, so the set is not complete.
  3. 3. How many 2-input NAND gates are needed to build an OR gate?

    Two NANDs act as inverters on a and b, and a third NAND combines them: OR(a, b) = NAND(NAND(a, a), NAND(b, b)).
  4. 4. In CMOS, why is an AND gate larger than a NAND gate?

    CMOS stages invert naturally, so a non-inverting gate needs an extra inverting stage, which adds 2 transistors.

Summary

  • A set of gates is functionally complete when it can build every Boolean function; NAND alone and NOR alone are complete.
  • NOT = NAND(a, a); AND = NOT(NAND); OR = NAND(NOT a, NOT b); XOR needs four NANDs.
  • NOR constructions mirror the NAND ones through duality.
  • An equivalence checker tries all input combinations and can report the first mismatch.
  • In CMOS, NAND and NOR cost 4 transistors, NOT costs 2, and AND and OR cost 6; gate count and transistor count are different measures.

Next: Boolean Algebra Laws, the rules for rewriting logic expressions.