Boolean Algebra Explainer (3D)

What this page shows

A Boolean function of two to four variables, in four forms: the truth table, a Karnaugh map, the minimal sum of products (SOP) and a gate-level AND-OR circuit whose wires show the live signal values for the current input.

Algebra used

Boolean algebra has AND (product), OR (sum) and NOT (prime). The identities used are absorption A + AB = A, adjacency AB + AB' = A, and De Morgan's laws (AB)' = A' + B', (A + B)' = A'B'. Every function is the OR of its minterms (rows where f = 1); merging adjacent minterms removes the variable that changes. On a Karnaugh map the rows and columns are in Gray-code order so that physical neighbours (including across the edges) differ in exactly one variable, and each rectangle of 1, 2, 4, 8 or 16 cells is one product term.

Quine-McCluskey

The page minimises with the Quine-McCluskey method: repeatedly merge cubes that differ in one bit to get all prime implicants (largest groups that contain no 0), then choose the cheapest set that covers every 1. Selection is exact: all subsets of the primes are tried and the one with the fewest terms, then fewest literals, wins. Cells marked X (don't care) may be used in groups but need not be covered; the seven-segment preset uses this for the six unused BCD codes. The product of sums is obtained by minimising the complement and applying De Morgan.

Cost model

Literals are the number of variable occurrences in the SOP. A two-level circuit needs one AND gate per multi-literal term and one OR; counted as two-input gates this is ∑(ki - 1) + (terms - 1). The histogram compares the current function with 150 random functions of the same size.

Checks run in the page

1. The minimal SOP reproduces the truth table on every care input. 2. The prime implicants found by Quine-McCluskey equal those found by exhaustively testing all 3ⁿ cubes. 3. The product of sums obtained through De Morgan matches the table. 4. The gate-level netlist drawn on screen, evaluated wire by wire, equals the SOP on all inputs.

Honest simplifications

Gates have no delay, so the circuit shows no glitches or hazards; a real two-level circuit can glitch when a single input changes. The two-level form is not always the cheapest circuit (multi-level factoring such as XOR chains can be smaller), and minimal cost here means fewest terms, then fewest literals. Four variables is the practical limit for hand Karnaugh maps.