Boolean algebra

The formula

Three operations generate the whole system. In switching notation, AND is written as multiplication, OR as addition, NOT as an overbar or prime:

A·B        AND — output is 1 only when both inputs are 1
A + B      OR  — output is 1 when at least one input is 1
Ā          NOT — output is the opposite of the input

The laws that make it an algebra rather than a lookup table:

A·1 = A          A + 0 = A          (identity)
A·0 = 0          A + 1 = 1          (annihilator — a 0 kills an AND, a 1 saturates an OR)
A·A = A          A + A = A          (idempotence — no such thing as "twice as true")
A·Ā = 0          A + Ā = 1          (complement)
A + A·B = A                         (absorption — the A·B term adds nothing)
A·(B + C) = A·B + A·C               (AND distributes over OR, like ordinary algebra)
A + B·C = (A + B)·(A + C)           (OR distributes over AND — no arithmetic counterpart)

And the pair that does most of the daily work, De Morgan's laws:

NOT(A·B)  = Ā + B̄     — "not both" means at least one is false
NOT(A+B)  = Ā·B̄       — "neither" means both are false

An inversion pushed through a parenthesis flips every AND to OR and every OR to AND. That single rule is how active-low logic, NAND-only designs, and inverted interlock conditions all get reasoned about.

Everything else is built from the three primitives. Exclusive-OR, the disagreement detector behind parity and comparators:

A ⊕ B = A·B̄ + Ā·B     — 1 exactly when the inputs differ

Where you meet it

The PLC rack on a test stand. A ladder rung is a Boolean expression drawn sideways: contacts in series are AND, parallel branches are OR, a normally-closed contact is NOT. The run-permissive rung that reads "tank pressure OK AND lockout key in AND E-stop not pressed" is P·K·Ē, and every rung on the stand parses the same way.
Firmware and test-script conditionals. if (!(valveOpen && pumpOn)) is a De Morgan expression waiting to be misread. Half the logic bugs a test engineer chases at 4 p.m. are an inversion applied to a compound condition without swapping the AND for an OR.
Digital design review. When an FPGA or board design goes in front of a review board, the abort logic gets walked through as Boolean algebra: which combination of sensor states fires the abort, which combinations can't, and whether the minimized expression still covers every case the requirement listed.
FMEA and interlock analysis. "The system is safe when A and B and C all hold" has a failure condition of Ā + B̄ + C̄ — any one out of family. Writing the unsafe condition correctly is a De Morgan exercise, and getting it wrong on paper is how a single-point failure hides in plain sight.

How it works

The variables take exactly two values, and every operation returns one of those two values, so any function of n inputs is fully described by a truth table with 2^n rows. Two inputs give 4 rows and 2^4 = 16 possible functions — AND, OR, XOR, NAND, and twelve others. Eight inputs give 256 rows. That finiteness is the point: unlike a differential equation, a Boolean expression can be verified exhaustively, and for anything under a few dozen inputs, it should be.

It looks like the algebra you learned in school and then betrays you in specific places. There is no carry: 1 + 1 = 1, not 2. Idempotence means exponents and coefficients don't exist. Both distributive laws hold — A + B·C = (A+B)·(A+C) is legal here and nonsense in arithmetic. And there is no subtraction or division, which means you cannot cancel: A·X = A·Y does not let you conclude X = Y (set A = 0 and the premise is true for any X and Y).

NAND alone is functionally complete: NAND(A,A) = Ā, and from NOT plus NAND you can build AND, OR, and everything else. This is why entire logic families were built from one gate type, and why a designer who can push inversions around with De Morgan can read a NAND-NAND schematic as the AND-OR expression it actually implements.

The identities are also the minimization toolkit. A raw sum-of-products expression read straight off a truth table is rarely the cheapest implementation; absorption, complements, and De Morgan shrink it, and a Karnaugh map does the same job graphically for up to four or five variables by grouping adjacent 1s. Fewer terms means fewer gates, fewer rungs, fewer places to be wrong — with the timing caveat below.

In code, precedence sets its own trap. C, Python, and most ladder-logic compilers bind AND tighter than OR, so A + B·C and a or b and c mean A + (B·C) — but a reviewer skimming the line often reads it left to right as (A + B)·C. Those differ (take A = 1, C = 0: the first gives 1, the second gives 0). Parenthesize compound conditions like you expect them to be misread, because they will be.

The classic mistake is distributing a NOT without flipping the operator — reading NOT(A·B) as Ā·B̄. Check it with one row: A = 1, B = 0 gives NOT(1·0) = 1 but Ā·B̄ = 0·1 = 0. Not the same function. The mixed active-high/active-low nets on a real board multiply the opportunities to make exactly this error.

Two limits worth respecting. First, algebraic equality is not timing equality. The consensus identity A·B + Ā·C + B·C = A·B + Ā·C says the B·C term is logically redundant — but in hardware that "redundant" term is often the hazard cover that keeps the output from glitching while A transitions. Minimize the expression and you can introduce a glitch the algebra can't see. Second, the algebra assumes clean two-state signals. Floating inputs, metastability, contact bounce, and race conditions all live outside the model, which is why a rung that is provably correct on paper still needs a debounce timer in front of it.

History

George Boole was born in Lincoln, England in 1815, the son of a shoemaker, and never earned a degree — he taught himself mathematics (and French, German, and Greek), took a junior teaching job at sixteen, and was running his own school at nineteen ^[2]^[3]. In 1847 he published the pamphlet The Mathematical Analysis of Logic, the first of his works treating logic as algebra, and in 1854 the fuller statement, An Investigation of the Laws of Thought ^[1]^[2]. On the strength of his papers, the self-taught schoolmaster was appointed the first professor of mathematics at Queen's College, Cork in 1849, where he stayed until his death in 1864, at 49 ^[2]^[3]. His contemporary Augustus De Morgan (1806–1871), a reformer of mathematical logic in London, put into formal notation the negation-swapping pair that carries his name ^[4]^[5].

For eighty years this stayed philosophers' territory. Then in 1937 a 21-year-old MIT graduate student named Claude Shannon wrote a master's thesis, A Symbolic Analysis of Relay and Switching Circuits, showing that relay contacts in series and parallel obey Boole's algebra exactly — and that the algebra could therefore be used to analyze and simplify the relay networks in telephone switching systems ^[1]^[6]^[7]. Shannon went on to Bell Labs in 1941 ^[7]. The thesis has been called the most important master's thesis of the century ^[6], and the claim holds up: it is the document that turned a Victorian schoolteacher's logic into the working language of every digital circuit built since.

Related tools

/tools/adc-resolution — 2^n counts per n bits; the same power-of-two structure as a truth table
/tools/snr-enob — effective number of bits, where the binary bookkeeping meets analog reality
/tools/ne555-astable — the clock source that steps sequential logic through its states
/tools/ne555-monostable — one-shot pulse generation for debouncing the switches your Boolean model assumes are clean

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →