Learn · The Concrete Discrete Math of Real Systems

seedling

A Policy Fits on a Tiny Table

The words inside an if statement obey a tiny algebra — and once you can run that algebra by hand, tangled policies become tables, equivalent rules become visibly equal, and implication stops pretending to be causation.

discrete-math, logic, boolean-algebra, truth-tables, implication, learn

They exhibit it not as a mere collection of signs, but as a system of expression.

— George Boole, The Calculus of Logic, 1848

This is the first chapter of The Concrete Discrete Math of Real Systems. You will turn an ordinary policy into a truth table; use AND, OR, and NOT as operations rather than English words; prove two rules equivalent by showing that no input separates them; read “if $P$ , then $Q$” without smuggling causation into it; and explain why an implication with a false premise is true. The only prerequisite is having read or written an if statement.

The deploy argument

A release is waiting. The team's rule says:

Deploy when the tests pass and the request is approved, or when the incident override is on.

Mina reads that as “ordinary deployments need both tests and approval; an incident may override both.” Arun reads it as “tests must always pass; either approval or an incident flag supplies the second key.” Their two readings are:

Mina: (tests AND approved) OR incident.
Arun: tests AND (approved OR incident).

Both sound responsible. Both match the sentence. They disagree in exactly one kind of situation: an incident is active while tests are failing. Mina's rule allows the deploy; Arun's refuses it.

Before reading further, decide which policy the sentence actually promised. There is no trick answer. The ambiguity is the defect.

Commit before the name. Two readings agree on seven input rows and split on one. Which one did the policy owner mean?

The ordinary cure is more prose: “to be absolutely clear…” But longer English is still English. The durable cure is to list every possible input and let the rule answer each one.

A machine with eight inputs

Each fact has only two possible values: true or false. Three such facts make $2^3 = 8$ possible worlds. In every world, the rule emits exactly one answer. That input-output table is a truth table.

Note

The person behind “Boolean.” George Boole (1815–1864) was a largely self-educated English mathematician who supported his family by teaching before becoming professor of mathematics at Queen's College, Cork. His 1848 calculus of logic and 1854 Laws of Thought made logical relations algebraic. Modern Boolean algebra is named for that program, but its switching form also owes a decisive engineering step to Claude Shannon. “Named after” does not mean one person supplied the finished modern subject.

Proposition — a statement to which “true” or “false” applies, such as “the tests passed.” A question, command, or vague preference is not yet a proposition. Learn more.

Truth table — an exhaustive table of a logical expression's output for every assignment of truth values to its inputs. Learn more.

Call the three propositions $T$ (tests pass), $A$ (approved), and $I$ (incident). Mina's rule is $(T \wedge A) \vee I$ . Read the wedge as “and” and the vee as “or.” Arun's is $T \wedge (A \vee I)$ .

The symbols have earned their place: they preserve the grouping that the sentence lost. From here on, $\neg P$ means “not $P$ ,” $P \wedge Q$ means “both,” and $P \vee Q$ means “at least one, possibly both.”

The truth-table law. A finite Boolean rule is completely determined by its output on every possible input row. Two rules are equivalent if and only if every row gives the same output.

This law changes what “same behavior” means. Similar-looking source is irrelevant. Matching examples are insufficient. If two rules agree on every row, no Boolean input can distinguish them; if they differ, the first differing row is a complete counterexample.

That is why Claude Shannon's 1938 relay-circuit paper mattered so much. Shannon showed that switching circuits could be represented and simplified with the algebra of logic. A relay open or closed became a truth value. Wiring became an expression. A question about metal and current became a calculation.

Three operations do the work

NOT flips. AND requires both. OR requires at least one. Their tables are small enough to keep in working memory:

$P$	$Q$	$\neg P$	$P \wedge Q$	$P \vee Q$
F	F	T	F	F
F	T	T	F	T
T	F	F	F	T
T	T	F	T	T

Every finite decision over named yes/no inputs can be written with these operations. One brutally direct construction proves it: for each row that should return true, write an AND clause describing that row; then OR all those clauses together. The result may be ugly, but it exists. Later chapters will shrink such expressions without changing their answers.

De Morgan's laws. Negating a conjunction turns it into a disjunction of negations, and negating a disjunction turns it into a conjunction of negations:

$\neg(P \wedge Q) \equiv (\neg P \vee \neg Q), \qquad \neg(P \vee Q) \equiv (\neg P \wedge \neg Q).$

There are four assignments to $P$ and $Q$ . Evaluate both sides of the first claimed equivalence on those four rows. Both are true on FF, FT, and TF, and false on TT. Therefore the truth-table law says they are equivalent. The same four-row check proves the second law: both sides are true only on FF.

In plain English: “it is not the case that both gates opened” means at least one gate did not open. “Neither gate opened” is stronger: the first did not open and the second did not open.

Note

The person behind the laws. Augustus De Morgan (1806–1871), born in Madurai and raised in Britain, became the first mathematics professor at the institution now called University College London. He introduced the term “mathematical induction” in 1838 and developed the logical laws that now bear his name. The identities have roots in older syllogistic logic; the eponym credits De Morgan's explicit algebraic formulation, not the first human recognition of the pattern.

Remove either swap in De Morgan's law and a bug appears. Negating “paid AND verified” as “not paid AND not verified” excludes a user who paid but was not verified. The correct negation is “not paid OR not verified.” The row paid=true, verified=false is the counterexample.

“If” has only one bad row

Now for the connective that makes correct people uncomfortable.

“If the request is approved, the audit record exists.” Write it $A \to R$ . This statement makes no claim that approval caused the record. It says there must be no approved request lacking one. Its table has one false row:

$A$	$R$	$A \to R$
F	F	T
F	T	T
T	F	F
T	T	T

When approval is false, the rule has not been violated, whatever the record does. This is vacuous truth. The name sounds like a loophole; the behavior is exactly what production collection APIs already do.

Implication — $P \to Q$ , false only when $P$ is true and $Q$ is false. It asserts a constraint, not a cause or a timeline. Learn more.

Suppose a validator says “every failed check has an error message.” An empty list of failed checks satisfies the rule. There is no offending check. In many programming languages, every([]) or all([]) returns true for precisely this reason: a universal rule fails only when a counterexample exists, and the empty collection contains none.

The useful equivalence is:

$P \to Q \equiv \neg P \vee Q.$

Again there are four rows. The only row where $\neg P \vee Q$ is false has $P$ true and $Q$ false. That is exactly the only row where $P \to Q$ is false. The truth-table law finishes the proof.

In plain English: “approved implies recorded” means “either it was not approved, or it was recorded.” The formula does not explain why either fact holds; it rules out one forbidden combination.

The converse $Q \to P$ is a different rule. “If approved, then recorded” does not imply “if recorded, then approved”; rejected requests may be recorded too. The contrapositive $\neg Q \to \neg P$ is equivalent: if no record exists, approval cannot have happened. One is a reversal; the other is the original forbidden row viewed from the opposite side.

Put your own rule in the machine

The machine below accepts a deliberately small policy language: at most six named axes, eight options per axis, 4,096 total combinations, and twenty-four rules. Those bounds keep evaluation immediate and make the entire truth space inspectable. Beyond them, symbolic structures from Chapter 18 are the right tool; pretending enumeration scales forever would teach the wrong lesson.

Write axes as name: option, option. Then add rules such as require tests=pass, incident=off needs approval=yes, or region=eu excludes storage=us. Edit the sample into a policy you actually recognize.

A policy is a region of its truth space. Edit the axes and rules, then evaluate. The surviving rows are the policy's exact meaning; if none survive, the machine returns a smallest conflicting set of rules.

This evaluator uses choices larger than true/false, but nothing changed in principle. Each equality such as tests=pass is a proposition. The rules combine those propositions. The survivors are the truth-table rows on which the combined expression returns true.

What the algebra does not promise

A truth table proves what a rule says, not whether the rule is wise. It cannot tell you whether incident overrides should bypass tests. It cannot establish that the input named approved came from an authorized approver. It cannot turn an ambiguous real-world category into an honest Boolean by naming it eligible.

Nor does a short equivalent expression always exist. Enumeration gives a complete answer and an exponential bill: $n$ Boolean inputs make $2^n$ rows. The next several acts will keep asking the same engineering question: what additional structure lets us avoid listing everything?

The algebra's promise is narrower and stronger. Once the inputs and their meanings are fixed, the verdict is no longer a matter of prose.

Lessons

An if statement is an algebraic expression over propositions, not an English sentence that happens to contain punctuation.
A truth table is an exhaustive finite machine. Agreement on every row proves equivalence; disagreement produces a counterexample.
NOT, AND, and OR are enough to express every finite Boolean decision, though the resulting expression may be large.
$P \to Q$ forbids exactly one row: $P$ true and $Q$ false. It states a constraint, not causation.
Vacuous truth is what lets universal rules behave correctly on empty collections.

Practice

Completion — finish the negation.

Discrimination — implication is not its converse.

Transfer — find the hidden vacuous truth.

The question this algebra cannot phrase yet

We can now decide any rule over a fixed list of named propositions. But real specifications rarely name every request: they say “for every request there is a server that can handle it,” or “there is one server that can handle every request.” The words are nearly identical. The architectures are not.

How do we make a claim range over a whole population — and how much can change when we swap two tiny words?

References

Boole. “The Calculus of Logic.” Cambridge and Dublin Mathematical Journal, 1848. — the epigraph and the original program: logical language as a calculus rather than a collection of phrases
Boole. “An Investigation of the Laws of Thought.” Walton and Maberly, 1854. — Boole's mature algebra of logic and probability; read the opening chapters for the historical notation and ambition
Shannon. “A Symbolic Analysis of Relay and Switching Circuits.” Transactions of the AIEE, 1938. — the bridge from Boolean algebra to switching circuits — the ancestor of logic synthesis
Cornell CS 3110. “Propositional logic.” Cornell University, 2011. — a compact next treatment of connectives, implication, equivalence, and proof rules

The dangerous conditional is rarely the one nobody understands. It is the one two people understand differently. “Allow the deploy when the tests pass and the request is approved or the incident flag is on” sounds clear until one reader groups the approval with the tests and another groups the incident override with the whole rule. Code chooses one grouping whether the sentence did or not. A truth table makes every choice explicit, one row per possible world. The table is not clerical work. It is a small machine: feed it facts, receive a verdict, and know that no mood or metaphor entered between them.