Combinational Logic & Boolean Algebra
The primitive logic gates every digital circuit is built from, and the Boolean algebra rules used to simplify them.
Digital logic is the bridge between the binary representation covered in Number Systems & Digital Representation and an actual working circuit. Every CPU, no matter how complex, is built from a small set of primitive gates composed at scale.
The primitive gates
| Gate | Symbol | Truth table (A, B → Out) |
|---|---|---|
| AND | & | 00→0, 01→0, 10→0, 11→1 |
| OR | | | 00→0, 01→1, 10→1, 11→1 |
| NOT | ! | 0→1, 1→0 |
| XOR | ^ | 00→0, 01→1, 10→1, 11→0 |
| NAND | — | NOT(AND) — universal gate |
| NOR | — | NOT(OR) — universal gate |
NAND and NOR are called universal gates because either one alone can implement AND, OR, and NOT. This matters in practice: a standard-cell library or an FPGA's logic fabric can be built almost entirely from one gate type, simplifying manufacturing.
Combinational logic
Combinational logic has no memory — outputs depend only on the current inputs. A classic example is a 2-to-1 multiplexer, which selects one of two inputs based on a select line:
out = (select AND b) OR (NOT select AND a)Boolean algebra lets you simplify expressions like this before committing them to hardware. Two laws that come up constantly:
- De Morgan's law:
NOT(A AND B) = (NOT A) OR (NOT B), and the dualNOT(A OR B) = (NOT A) AND (NOT B). - Absorption:
A OR (A AND B) = A.
Simplification isn't academic — fewer gates means less propagation delay, less power, and less die area.
Gates alone can't build a counter or a register, because there's no way to retain state between clock cycles. The next sub-lesson, Sequential Logic & Synchronous Design, covers the flip-flop — the building block that gives digital circuits memory.