Free Digital logic lessons
Composition turns switches into decisions
AND, OR, and NOT are sufficient to express any Boolean function; NAND or NOR alone are also functionally complete. A truth table specifies behaviour for every input combination. Algebra and circuit structure then provide implementations with different area, delay, power, and fan-out.
A 2-to-1 multiplexer outputs A when selector S is 0 and B when S is 1: (NOT S AND A) OR (S AND B). That one pattern routes register values, chooses ALU operands, and selects the next program counter. Control is often data selection expressed in gates.
Build arithmetic and see the carry path
For bits A, B, and carry-in, sum is their parity and carry-out is true when at least two inputs are true. Chaining full adders creates multi-bit addition. In a ripple-carry adder, each stage waits on the previous carry, making a simple local design into a global delay path.
In a fixed width, negating x means invert its bits and add one. Then subtraction x−y can use the same adder as x+(−y). Overflow is interpreted according to signed or unsigned meaning; the bit pattern alone does not carry that meaning.
Registers, clocks, and state over time
Feedback allows a circuit to retain a state. Latches and flip-flops constrain when that state may change; registers group bits; a clock creates agreed capture boundaries. Between boundaries, combinational logic computes the next state from current state and inputs.
Data must settle before a capture edge for setup time and remain stable after it for hold time. Violating either can leave a storage element metastable—temporarily neither a dependable 0 nor 1. Synchronizers reduce the probability that asynchronous uncertainty escapes into logic, but cannot make it mathematically impossible.
Make control explicit and test every transition
Name the states, inputs, transition function, and outputs. Moore-style outputs depend on state; Mealy-style outputs may also depend directly on inputs. Reachability analysis exposes dead or unsafe states, while temporal properties state what must always or eventually happen.
States can encode vehicle green, yellow, all-red, and pedestrian crossing. A button sets a pending-request bit so a brief press is not lost. Transitions respect minimum timing and the invariant that conflicting directions are never green together. The model cleanly separates request memory from phase control.