Truth tables

The previous lesson built a language for writing forms down and gave no way at all to evaluate one.

That gap closes here, and it closes completely. Because every connective was chosen to be truth-functional, a formula's value depends on nothing but the values of its atoms, and there are only finitely many ways to assign those. Listing them all is the whole method. Validity, consistency and equivalence all become questions about a finished table, answerable by looking, and for a while that feels like the end of the subject rather than the third lesson of it.

A row is a possible situation

A valuation assigns true or false to every atom in a formula. With one atom there are two valuations, with two there are four, and in general $n$ atoms give $2^{n}$ , since each atom doubles the count. A truth table is the list of all of them with the formula's value worked out in each.

The link to the first lesson is direct. Validity was defined as the impossibility of true premises with a false conclusion, "impossible" meaning across all possible situations. In propositional logic a possible situation is exactly a valuation, because the only thing a formula can see is which atoms are true. So the vague quantifier over situations becomes a finite list of rows, and a definition that looked philosophical becomes an inspection.

That is a real narrowing, worth saying out loud. A row where $P$ is "the alloy contains nickel" and $Q$ is "the alloy contains no nickel" is counted as possible, because the notation cannot see that they conflict. Propositional logic only knows about situations in the sense of assignments to letters, and any impossibility living inside the atoms is invisible to it.

The five tables

The connectives are defined by these tables and by nothing else. All the rest of the subject is consequences of them.

$P$	$Q$	$\neg P$	$P \land Q$	$P \lor Q$	$P \to Q$	$P \leftrightarrow Q$
T	T	F	T	T	T	T
T	F	F	F	T	F	F
F	T	T	F	T	T	F
F	F	T	F	F	T	T

Four of the five columns match ordinary English closely enough to need no defence. Negation flips. A conjunction needs both. A disjunction needs at least one, and its bottom row is the only false one. A biconditional is true when the two sides agree, which is the top and bottom rows.

The conditional column is the odd one. It is false in exactly one row, the one where the antecedent is true and the consequent false, and it counts as true in both rows where the antecedent is false. That means "if the moon is made of cheese then Paris is in Spain" comes out true. There are reasons for this, and they take a lesson, which is the fourth. For now, take the column as given and notice its shape: a conditional is a promise that is broken only by a true antecedent with a false consequent.

Building a table

A compound formula is evaluated by working outward from the atoms, one column per subformula, ending with the main connective. The discipline is to give each column its own space rather than trying to do it in one's head.

Take $(P \land \neg Q) \land (\neg P \lor Q)$ . Four rows, since there are two atoms.

$P$	$Q$	$\neg Q$	$P \land \neg Q$	$\neg P$	$\neg P \lor Q$	whole
T	T	F	F	F	T	F
T	F	T	T	F	F	F
F	T	F	F	T	T	F
F	F	T	F	T	T	F

The final column is false in every row. Notice how it happened: the left conjunct picks out exactly the row where $P$ is true and $Q$ false, and the right conjunct is false in exactly that row, so nothing survives. That is worth seeing rather than just recording, because it is the reason the formula is a contradiction rather than a fact about it.

Three kinds of formula

The final column of a table can come out three ways, and the three names are used constantly.

A tautology is true in every row. $P \lor \neg P$ is one, and so is $(P \to Q) \lor (Q \to P)$ , which surprises people: whichever way the values fall, at least one of the two conditionals has a false antecedent or a true consequent, so at least one is true. A tautology says nothing about the world, since no situation can falsify it, and that emptiness is exactly why it is safe to assert anywhere.

A contradiction is false in every row, like the formula just tabulated, or the plain $P \land \neg P$ .

A contingency is true in some rows and false in others, which is what almost every useful statement is. "It is raining" tells you something precisely because it rules out situations.

A formula is satisfiable when at least one row makes it true, so tautologies and contingencies are satisfiable and contradictions are not. A set of formulas is consistent when some single row makes them all true at once. Consistency is not the same as everything being individually satisfiable: $P$ , $P \to Q$ and $\neg Q$ are each satisfiable on their own and no row makes all three true together.

Example. Classify $P \to (Q \to P)$ .

Two atoms, four rows. When $P$ is true, the inner conditional $Q \to P$ has a true consequent, so it is true, and the whole conditional has a true consequent and is true. When $P$ is false, the whole conditional has a false antecedent, so it is true by the third and fourth rows of the conditional table. Every row comes out true, so it is a tautology. It is worth pausing on how little it says: a true statement is implied by anything at all.

Now you. Classify $(P \lor Q) \land (\neg P \land \neg Q)$ .

Answer

A contradiction. The right conjunct is true only in the row where both atoms are false, and the left conjunct is false in exactly that row, so no row makes the whole thing true.

The test for validity

Here is the payoff. To test an argument, tabulate every premise and the conclusion over the same rows, then look for a row where every premise is true and the conclusion is false. If there is one, the argument is invalid and that row is a counterexample, a fully specified situation you can describe out loud. If there is no such row, the argument is valid, with no cleverness required.

Take: "If the reactor is scrammed, the pumps run. Either the pumps are not running or the valve is open. The valve is not open. So the reactor is not scrammed." With $S$ , $P$ and $V$ the argument is $S \to P$ , $\neg P \lor V$ , $\neg V$ , therefore $\neg S$ . Three atoms, so eight rows.

$S$	$P$	$V$	$S \to P$	$\neg P \lor V$	$\neg V$	$\neg S$
T	T	T	T	T	F	F
T	T	F	T	F	T	F
T	F	T	F	T	F	F
T	F	F	F	T	T	F
F	T	T	T	T	F	T
F	T	F	T	F	T	T
F	F	T	T	T	F	T
F	F	F	T	T	T	T

Scan the three premise columns for a row of all Ts. Only the last row qualifies, and its conclusion column is T. No row has true premises with a false conclusion, so the argument is valid. Note how thin the result is: seven of the eight rows were thrown out by the premises, and the verdict rests on one surviving row.

Example. Test: $P \to (Q \lor R)$ , $\neg Q$ , therefore $R$ .

Look for a row making both premises true and $R$ false. Try $R$ false and $Q$ false, which satisfies the second premise. Then $Q \lor R$ is false, so the first premise demands that $P$ be false, and $P$ false makes it true. So the row $P$ false, $Q$ false, $R$ false has both premises true and the conclusion false. The argument is invalid, and the counterexample is concrete: nothing is on, the conditional holds vacuously, and $R$ never had to be true.

Now you. Test: $(P \land Q) \to R$ , $\neg R$ , $P$ , therefore $\neg Q$ .

Answer

Valid. Suppose the conclusion is false, so $Q$ is true. With $P$ true from the third premise, $P \land Q$ is true, so the first premise forces $R$ true, contradicting $\neg R$ . No row can make the premises true with the conclusion false, so there is no counterexample.

Entailment, and a symbol for it

When no valuation makes a set of formulas $Γ$ true while making $φ$ false, $Γ$ entails $φ$ , written

Γ ⊨ φ

and read " $Γ$ entails $φ$ ", or " $φ$ is a semantic consequence of $Γ$ ". Validity of an argument is exactly entailment of its conclusion by its premises. With nothing on the left, $⊨ φ$ says $φ$ is a tautology.

The symbol matters because a second one arrives in the sixth lesson: $⊢$ , for what can be derived by a fixed set of rules. One is about tables, the other about proofs, and the fact that they coincide is the deepest result in propositional logic rather than an obvious identity.

Two facts fall straight out of the definition and settle the puzzles from the first lesson. An inconsistent set entails everything, since it makes no row true and so has no row with true premises at all. And a tautology is entailed by anything, since no row makes it false.

The short cut

Eight rows are tedious and sixteen are worse, so in practice the table is almost never drawn in full. Instead, assume the argument is invalid and try to build the offending row directly. Set the conclusion false, then work through the premises forcing values as far as they will go. If you reach a contradiction on every branch, no such row exists and the argument is valid. If you complete a row without contradiction, that row is a counterexample.

That is what the last two exercises did, and the saving grows fast: the second exercise settled a three-atom argument in two lines instead of eight rows, and the same reasoning handles ten atoms without ever mentioning 1024.

The method needs care in one place. When a premise leaves a genuine choice, both branches must be tried before declaring validity. A disjunction with neither side forced is the usual case: $P \lor Q$ with nothing else known splits into $P$ true and $P$ false with $Q$ true, and abandoning one branch is how a counterexample gets missed.

Example. Test $P \lor Q$ , $P \to R$ , $Q \to R$ , therefore $R$ , by the short cut.

Set $R$ false. The second premise then forces $P$ false and the third forces $Q$ false, since a true antecedent with a false consequent would break them. But the first premise needs one of $P$ and $Q$ to be true, and both have just been forced false. Every branch closes, so no counterexample row exists and the argument is valid. Eight rows never had to be written, and the reasoning shows which premises did the work.

Now you. Test $P \to Q$ , $R \to S$ , $P \lor R$ , therefore $Q \land S$ .

Answer

Invalid. Set the conclusion false by making $S$ false, which forces $R$ false through the second premise, which forces $P$ true through the third, which forces $Q$ true through the first. The row $P$ true, $Q$ true, $R$ false, $S$ false makes all three premises true and the conclusion false. Sixteen rows would have found the same thing more slowly.

What the table costs

The table method is complete, mechanical and guaranteed to terminate, which puts propositional logic in a rare position: its validity problem is decidable, and a procedure exists that answers every instance in finite time.

The trouble is the finite time. Rows double with each atom, so 10 atoms give 1024 rows, 20 give 1,048,576, and 30 give 1,073,741,824. At a million rows a second that last one takes about 18 minutes, and 60 atoms, still a small argument by the standards of a real legal document or circuit, would take roughly 36 years at a billion rows a second. Doubling defeats hardware improvements: buying a machine ten times faster buys about three more atoms.

There is a second complaint, and it is the one that shapes the rest of the subject. A completed table certifies that no counterexample exists without showing why the conclusion follows. It gives no argument you could present to somebody, no insight into which premise did the work, and no way to reuse a step in the next problem. It is a verdict rather than a proof.

The response to both complaints is the same: reason with the formulas instead of enumerating their rows. That needs rules for transforming formulas while preserving truth, which is the fifth lesson, and rules for deriving conclusions line by line, which is the sixth. Before either, one column of the table above still needs explaining, and the next lesson is about that column alone.