Logic Gates & Boolean Algebra: From Transistors to CPUs

Why binary, and the four basic gates

A transistor is a voltage-controlled switch: on (≈3.3 V) or off (≈0 V). That naturally maps to 1 and 0. Binary is also maximally noise-resistant — designing for ten stable voltage levels would demand far more precision than two. A logic gate takes one or two binary inputs and produces a binary output from a truth table. AND (A·B) is 1 only if both inputs are 1, like two switches in series. OR (A+B) is 1 if at least one input is 1, like switches in parallel. NOT (Ā) simply flips the bit. XOR (A⊕B) is 1 when the inputs differ — the gate that makes addition and error detection possible.

NAND, NOR and De Morgan's laws

Adding a NOT stage to AND or OR gives NAND and NOR. Augustus De Morgan's laws connect them: NOT(A·B) = Ā+B̄, and NOT(A+B) = Ā·B̄ — negating an AND is the same as OR-ing the negated inputs, and vice versa. Because of this duality, NAND alone (or NOR alone) is functionally complete: every Boolean function, including XOR, can be built from NAND gates only. In CMOS silicon, a 2-input NAND needs just 4 transistors versus 6 for AND, so real chips are synthesised almost entirely in NAND logic.

Building an adder

A half adder adds two bits: Sum = A⊕B, Carry = A·B — but it cannot accept a carry-in. A full adder takes three inputs (A, B, Cᵢₙ) and is built from two half adders plus an OR gate, producing Sum and Carry-out. Chain 64 full adders into a ripple-carry adder and you can add two 64-bit integers — though bit 63's sum can't resolve until the carry ripples through all 63 prior stages. Real CPUs use carry-lookahead adders that compute every carry in parallel, finishing 64-bit addition in about 5 gate delays instead of 64.

Half adder:  Sum = A ⊕ B          Carry = A · B
Full adder:  Sum = (A⊕B) ⊕ Cin    Cout = A·B + Cin·(A⊕B)
NAND is universal:
  NOT A   = NAND(A, A)
  A AND B = NAND(NAND(A,B), NAND(A,B))
  A OR B  = NAND(NAND(A,A), NAND(B,B))

The ALU and gates in silicon

An Arithmetic Logic Unit takes two operands and an operation selector, then routes them through the right gate network for addition, bitwise logic, shifts, and comparisons — the selector drives a multiplexer that channels the operands to the correct block. Physically, each gate is a complementary pair of MOSFET networks: a pull-up PMOS network and a pull-down NMOS network. The Apple M4 chip (2024) packs roughly 28 billion transistors into a 3 nm process — each one obeying the same truth tables on this page. Claude Shannon proved in his 1937 master's thesis, at age 21, that any Boolean function can be built from switching circuits; 87 years of engineering later, the underlying algebra hasn't changed by a single axiom.

Frequently asked questions

Try it live

Everything above runs in your browser — open Logic Gates and flip inputs across 8 gate types while watching animated signal wires and a live truth table. Nothing is installed, nothing is uploaded.