Logic Gates
AND, OR, XOR, NOT: the atomic units of digital hardware.
Problem
How does hardware compute? Every digital circuit is built from a small set of Boolean logic gates.
How it works
AND: output is 1 only when all inputs are 1. Written A·B.
OR: output is 1 when any input is 1. Written A+B.
XOR (exclusive OR): output is 1 when inputs differ. Written A⊕B. This is the "addition without carry" gate.
NOT (inverter): flips 0→1, 1→0. Written ¬A or Ā.
NAND / NOR: AND/OR followed by NOT. NAND is "universal": any circuit can be built from NAND gates alone.
OR: output is 1 when any input is 1. Written A+B.
XOR (exclusive OR): output is 1 when inputs differ. Written A⊕B. This is the "addition without carry" gate.
NOT (inverter): flips 0→1, 1→0. Written ¬A or Ā.
NAND / NOR: AND/OR followed by NOT. NAND is "universal": any circuit can be built from NAND gates alone.
Key insightEvery circuit: adders, multipliers, CPUs: is just a composition of these gates. A single gate switching is the smallest unit of time in our delay models.