The formula
Two governing relationships. Everything digital is one or the other, or a mix.
Combinational: Y = f(X)
Reading: the output vector Y is a pure function of the input vector X. No memory, no clock. Same inputs, same outputs, every time. A truth table fully describes it.
Sequential: Q(next) = f(X, Q(current))
Y = g(X, Q(current))
Reading: the next stored state Q(next) depends on the inputs X and the present state Q. The output Y reads off the state (and maybe the inputs). This is a finite-state machine.
D flip-flop: Q(next) = D (sampled at the clock edge)
Reading: on the active clock edge, the output takes whatever D was. Between edges it holds. This one element is the workhorse of every synchronous design.
Truth-table size: rows = 2^n (n input bits)
Distinct functions: 2^(2^n) (n-input Boolean functions)
Reading: three inputs give 8 rows and 256 possible functions; four inputs give 16 rows and 65,536. The state space explodes fast, which is why you minimize before you build.
NAND is universal: NOT a = a NAND a
a AND b = NOT(a NAND b)
a OR b = (NOT a) NAND (NOT b)
Reading: give an engineer nothing but NAND gates and they can build any logic function. NOR is universal the same way. This is why fabs optimize the daylights out of one gate.
Where you meet it
- On the bench, debugging a state machine that "sometimes" hangs. A vending-style controller, a valve sequencer, a built-in-test FSM — it works on the logic analyzer at slow clock, then locks up in the field. Nine times out of ten it's a sequential-logic problem: a missing reset state, an input sampled asynchronously, or a state you can enter but can't leave.
- In an FPGA timing review, staring at a setup-time failure. The synthesis tool reports negative slack on a path between two flip-flops. That path is combinational logic — a chain of gates — and it's too deep to settle before the next clock edge. You shorten the path (restructure the logic, retime, tighten placement), pipeline it, or slow the clock — and if the data genuinely has multiple cycles to arrive, you tell the tool so with a multicycle constraint.
- Designing a data-acquisition front end at a test stand. The address decoder that picks which ADC channel to read is pure combinational logic. The sample-and-hold command and the channel counter that walks the mux are sequential. Get the boundary between the two wrong and you latch stale data.
- Bringing up a board where two clock domains meet. A signal crossing from a 10 MHz domain into a 100 MHz domain hits a flip-flop that may catch it mid-transition. This is the metastability case, and it's the one that turns a "should never happen" into a warranty return.
How it works
Combinational logic is the easy half to reason about and the easy half to get subtly wrong. Because Y = f(X), you can write the whole thing as a truth table and minimize it — Karnaugh map for four variables or fewer, a Quine–McCluskey pass or a synthesis tool above that. The trap is glitches. Real gates have propagation delay, and when two inputs change at once, the output can momentarily flip to a wrong value while the signals race through different path lengths before settling. If a combinational output feeds a clocked flip-flop and the glitch has cleared by the setup window, you never see it. If it feeds an asynchronous reset or a latch enable, the glitch is a live round. The fix is discipline: register your outputs, and don't gate clocks or resets with raw combinational logic.
Sequential logic is where the real trouble lives, because now timing is a first-class citizen. A flip-flop only captures data correctly if D is stable for a setup time before the clock edge and a hold time after it. Violate either and the flip-flop can go metastable — its output hovers between valid 0 and valid 1 for an unbounded, probabilistic interval before resolving. You cannot design metastability to zero; you can only push its probability down with synchronizer chains (two or three flip-flops in series) so the mean time between failures is longer than the age of the program. Anyone who tells you a single flip-flop "cleans up" an asynchronous signal has never chased the resulting bug.
The distinction between a latch and a flip-flop is the mistake juniors make most. A latch is level-sensitive: while its enable is high, its output follows the input — it's transparent. A flip-flop is edge-sensitive: it samples only at the clock transition. The classic edge-triggered part is the master-slave design, two gated latches in series with opposite enable phases, so the input is captured by the master while the slave holds, then handed off on the edge. Modern flip-flop naming — SR, D, T, JK — was pinned down by Montgomery Phister in a 1954 UCLA course and his book that followed [1]. Accidental latches are a top synthesis warning: leave an output unassigned in one branch of a combinational block and the tool infers a latch you never wanted, complete with its own timing hazards.
The limit of validity for the whole clean picture is synchronous design. The formulas assume one clock, edges everywhere, setup and hold met on every path. The moment you have two unrelated clocks, an asynchronous input, or a combinational loop, you've left the model — and that's exactly where hangs, glitches, and metastable states come from. Ripple counters make the point: chain N toggle flip-flops and the last bit doesn't settle until N propagation delays after the edge, so reading the count during that window gives garbage. The synchronous fix clocks every stage together and pays for it in gates.
History
The math came first, by seventy years. In 1854 the English mathematician George Boole published An Investigation of the Laws of Thought, reducing logic to an algebra of TRUE and FALSE that you could manipulate like numbers [2]. For decades it stayed a curiosity of mathematical logic with no hardware to run on.
The hardware showed up in 1918. British physicists William Eccles and Frank Wilfred Jordan filed a patent that June for what they called an "ionic relay," and in September 1919 they described it in a one-page note in The Electrician, "A trigger relay utilizing three-electrode thermionic vacuum tubes" [1][3]. Two vacuum tubes cross-coupled so each held the other in state — the first bistable circuit, the ancestor of every flip-flop. They pitched it for telegraphy and telephony; they had no idea they'd built the storage cell of the computer age.
The two halves met in 1937. Claude Shannon, a 21-year-old MIT research assistant running Vannevar Bush's differential analyzer, noticed that the open-and-closed behavior of switching relays mapped exactly onto Boole's TRUE and FALSE. His master's thesis, submitted August 1937 and published in 1938, showed you could design and simplify switching circuits with Boolean algebra [5]. That thesis is the reason we say "logic design" and mean electronics. From there the field filled in the practical tools: Edward Veitch published his chart in 1952, and Maurice Karnaugh refined it into the Karnaugh map in 1953 — the grid every EE student still uses to minimize a truth table by hand [4].
Related tools
- /tools/ne555-astable
- /tools/ne555-monostable
- /tools/adc-resolution
- /tools/rc-charge-time