Propositional logic

The formula

The five connectives, defined completely by one four-row table:

A B |  A∧B   A∨B   A→B   A↔B   A⊕B
0 0 |   0     0     1     1     0
0 1 |   0     1     1     0     1
1 0 |   0     1     0     0     1
1 1 |   1     1     1     1     0

Reading: AND (∧) demands both, OR (∨) accepts either, IF-THEN (→) is only violated by a true premise with a false conclusion, IFF (↔) demands agreement, XOR (⊕) demands disagreement. The column is the connective — there is nothing else to know about it.

The size of the job:

n inputs  →  2ⁿ rows

Reading: every proposition built from n atomic statements is fully specified by 2ⁿ rows — 16 rows for four interlock inputs, 32 for five, and 1,048,576 by the time you reach twenty. Exhaustive checking is genuinely possible, then abruptly isn't.

The identities that do the daily work:

A → B  ≡  ¬A ∨ B              (implication is just an OR in disguise)
A → B  ≡  ¬B → ¬A             (contrapositive — the only free reversal you get)
¬(A ∧ B)  ≡  ¬A ∨ ¬B          (De Morgan: "not both" = "at least one fails")
¬(A ∨ B)  ≡  ¬A ∧ ¬B          (De Morgan: "neither" = "both fail")

Reading: two propositions are equivalent when their truth-table columns match row for row — that is the entire test, and it is decidable by brute force every time.

Where you meet it

At the test stand, writing the permissive chain. "Fire is permitted only when door closed AND N₂ purge complete AND operator arm switch made AND no abort latched" is a four-variable proposition with a 16-row truth table. Fifteen of those rows must inhibit. The review question that catches real errors is not "does the happy path work" — it's "walk me through the other fifteen rows," and propositional logic is the tool that makes that walk finite.
In the requirements clause at a design review. "The system shall enter safe mode when pressure exceeds limit or temperature exceeds limit and power is degraded." As written, that sentence is P ∨ (T ∧ D) to one reader and (P ∨ T) ∧ D to another, and the two disagree on two of the eight rows — both when pressure is high but power is healthy. Parenthesize the clause as a proposition and the argument ends in one meeting instead of surfacing at acceptance test.
In the alarm rationalization meeting. Suppression logic like "inhibit low-flow alarm when pump stopped OR valve commanded closed" is a proposition, and the failure mode is the row nobody enumerated — pump running, valve closed, flow actually low, alarm suppressed anyway. Writing out the table is how that row gets found before the incident report does it for you.
In the fault tree. Every AND gate and OR gate in an FTA is a propositional connective over failure events, and "minimal cut set" is propositional-logic vocabulary: the smallest conjunction of basic events that makes the top event true.

How it works

Propositional logic operates on statements that are each entirely true or entirely false — no partial credit, no "usually." The connectives are defined by their truth tables and by nothing else; there is no hidden meaning in → beyond its column. That flatness is the power: any question about a compound statement — is it always true (a tautology), never true (a contradiction), equivalent to the clause in rev B of the spec — reduces to a finite table check. Equivalence checking is literally XOR-ing two columns and confirming every row comes out zero.

The mistake people make, over and over, is reading A → B as causation or as a two-way street. Material implication is true whenever the premise is false. "If chamber pressure exceeds 900 psi, the vent valve shall open" is a statement that says nothing at all about what the valve does at 850 psi — the requirement is satisfied vacuously there, and a verification matrix that only tests the high-pressure case has verified half a sentence. The companion error is affirming the consequent: from A → B and B, concluding A. Valve open does not prove pressure was high. The only reversal the table licenses is the contrapositive — valve not open proves pressure was not above 900, assuming the requirement is met. Interlock troubleshooting runs on contrapositives, and half of bad troubleshooting runs on converses.

Second gotcha: operator precedence. Convention binds NOT tightest, then AND, then OR — ¬A ∨ B ∧ C means (¬A) ∨ (B ∧ C). English does not carry precedence, which is why "or...and" requirements clauses are ambiguous until parenthesized, and why PLC rung logic and the requirement text it implements can honestly disagree while both look right.

Third: know what the formalism cannot see. Propositional logic is timeless and two-valued. It has no yesterday — "arm switch made, then door opened" is a sequencing statement, and sequence belongs to state machines and temporal logic, not truth tables. It has no "unknown" — a stale sensor value is not false, which is why SQL uses three-valued logic and VHDL's std_logic carries nine values including X and U; classical tables silently assume every input is fresh and valid. And it has no quantifiers — "every channel is calibrated" over an indefinite set needs predicate logic. The two-valued table is a model of the plant, and sensors that lie, contacts that bounce, and signals still in flight all live outside the model.

Scale is the last limit, and it is a real one. The 2ⁿ blowup ends hand enumeration around five variables and ends brute force entirely somewhere past forty. Deciding satisfiability of an arbitrary proposition was the first problem ever proved NP-complete ^[12]^[13]. The practical answer is the modern SAT solver, which routinely handles instances with tens of thousands of variables and millions of clauses ^[13] — it is the engine inside formal equivalence checking and model checking of digital hardware, which is to say: the FPGA in your test rack was verified by an industrial-strength truth-table argument.

History

The subject is older than algebra. Chrysippus of Soli (c. 279–206 BC), the third head of the Stoa, built a deductive system whose atoms were whole assertibles — propositions — joined by "if," "and," and "or," resting on five indemonstrable argument forms that included what we still call modus ponens and modus tollens ^[3]^[4]. His logic was then largely lost; most of his writings did not survive antiquity ^[3]. The propositional viewpoint waited out the long dominance of Aristotle's term logic until the nineteenth century, when Boole and De Morgan rebuilt logic as algebra ^[1]. Gottlob Frege's 1879 Begriffsschrift then gave the first modern formal system — negation, implication, quantifiers, and proofs run as symbol manipulation from explicit axioms ^[5]^[6].

The truth table as a working tool arrived in a burst around 1921. Ludwig Wittgenstein's Tractatus Logico-Philosophicus, completed in wartime and published that year, used tables to argue that all propositions are truth functions of elementary ones ^[2]^[7]. The same year, Emil Post's paper in the American Journal of Mathematics — grown from his 1920 Columbia dissertation — used the truth-table method to prove the propositional calculus of Principia Mathematica complete and consistent: every tautology is provable, and nothing false is ^[8]^[9]. Charles Sanders Peirce had anticipated pieces of all of it decades earlier in manuscripts he never published ^[2]^[10]; his roughly 1880 discovery that a single NAND-like operation suffices for the whole system surfaced only in 1926, in a basket marked for discard — thirteen years after Henry Sheffer had published the result in 1913 and put his name on the stroke ^[10]^[11]. The modern chapter opened in 1971, when Stephen Cook proved propositional satisfiability NP-complete, with Leonid Levin arriving independently — the founding result of complexity theory, built directly on the humble two-valued proposition ^[12]^[13].

Related tools

/tools/adc-resolution — 2ⁿ codes per n bits, the same power-of-two count as truth-table rows
/tools/ne555-monostable — the one-shot that debounces the contact your proposition assumes is clean
/tools/ne555-astable — the clock that turns static logic into the sequential kind truth tables can't describe

Sources

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