Community › Week 2 · Foundations

Logic Gates, and Why NAND Can Build Everything

A logic gate is a tiny circuit that turns input bits into an output bit by one fixed rule: AND gives 1 only when every input is 1, OR when any input is 1, and NOT flips its input. NAND is called universal because NOT, AND and OR, and so any digital circuit, can be built from NAND gates alone.

Where you'll use this

  • University exams: truth tables, gate diagrams and "prove NAND is universal" questions
  • Verilog RTL: the &, |, ^ and ~ operators are these gates, one per bit
  • Embedded C: setting, clearing and toggling register bits with OR, AND and XOR masks
  • Interviews: building one gate out of another is a classic warm-up

Key terms

Truth table
A table listing the output for every combination of inputs. Two inputs give 4 rows, three give 8.
NAND
AND followed by NOT. Its output is 0 only when every input is 1.
XOR
Exclusive OR: 1 when the two inputs differ, 0 when they are the same.
Universal gate
A gate type that can build every other gate on its own. NAND and NOR are both universal.
Bitwise operator
An operator that applies a gate to each bit position of two numbers at once, like & and | in C and Verilog.

Questions people ask

What are the seven basic logic gates?

AND, OR, NOT, NAND, NOR, XOR and XNOR. NAND, NOR and XNOR are AND, OR and XOR with the output inverted. NOT has a single input; textbooks usually draw the others with two, though AND, OR, NAND and NOR can take more.

Why is NAND called a universal gate?

Because NOT, AND and OR can each be made from NAND gates alone, and every Boolean function can be written with those three. So a chip could in principle be built from one kind of gate. NOR is universal for the same reason.

How do I write logic gates in Verilog?

Use the bitwise operators in a continuous assignment: & for AND, | for OR, ~ for NOT and ^ for XOR, and put ~ around a whole expression to invert it. Verilog also has built-in gate primitives named and, or, nand, nor, xor, xnor and not, which list the output first.

Last updated · Reviewed by the BitForBytes team

When it opens

Part 1, the interactive concept, opens Mon, 12 Oct, 7:30 pm IST. Part 2, the harder half with worked Level-Up answers, opens Thu, 15 Oct, 7 pm IST. Both are free and need no signup.

This week's challenge

Challenge #3: Full Adder: Add three bits with a carry in: click the 8-row truth table, follow the carry, then write the Verilog. Opens Wed, 14 Oct, 7:30 pm IST.

More from the community