Truth tables: a law of logic is two columns that agree on every row¶

Level: 101 · for anyone who has seen ¬, ∧, ∨, →, ↔ and wondered what makes one of the "logic laws" true

One line: A sentence built from P, Q, R with connectives is a function of their truth values, a truth table lists it on every input, and two sentences are logically equivalent when their columns agree; so every law in a textbook's list, De Morgan's and the contrapositive included, is proved by a table with 2ⁿ rows, and the difference between ↔ and ⇔ is the difference between a column and a claim about two columns.

The connectives, and the one that surprises¶

Symbol	Name	Read aloud	True when
¬P	negation	not P	P is false
P ∧ Q	conjunction	P and Q	both are true
P ∨ Q	disjunction	P or Q (or both)	at least one is true
P → Q	conditional	if P then Q	always, except when P is true and Q is false
P ↔ Q	biconditional	P if and only if Q	P and Q have the same truth value

Only the conditional needs explaining, and the first lesson of this chapter spends a page on it: "if P then Q" is a promise broken in one case only, P true and Q false, so it is true whenever P is false, whatever Q says. The biconditional is two conditionals at once, P → Q and Q → P, which the program checks as a law.

Cunningham, whose section 1.2 this page follows, writes the connectives inside a sentence as →, ↔ and the relations between sentences as ⇒, ⇔; Cori and Lascar write ⇒, ⇔ for both. The axioms chapter has a table of who writes what.

A truth table, built inside out¶

A sentence is read like an arithmetic expression: find the outermost connective, then its parts. In ¬P → (Q ∧ P) the outermost is →, with ¬P on its left and Q ∧ P on its right. So the table gets a column for P and Q, then ¬P, then Q ∧ P, then the whole. Section 1 of the program prints it. With n letters there are 2ⁿ rows, every combination of true and false, and the table is complete: nothing about P and Q matters except their truth values.

Three words for what a column can look like. A tautology is true on every row, like P ∨ ¬P. A contradiction is false on every row, like P ∧ ¬P. Two sentences are logically equivalent, written ψ ⇔ φ, when their columns agree on every row, which is the same as saying that ψ ↔ φ is a tautology. That is the whole difference between the two arrows: ↔ is a connective that makes a longer sentence, ⇔ is a statement about two sentences, and the second is what a "law" is.

Why a table proves a law¶

Section 4 checks Cunningham's entire list, De Morgan's laws, the commutative, associative, idempotent and distributive laws, double negation, the two conditional laws and the contrapositive, on all eight rows for three letters. Each comes back True, and that True is a proof, not a sample: a law says nothing about P, Q, R except how their truth values combine, and the eight rows are every combination there is. This is the same argument the algebra of sets makes for checking set identities on a four-element universe, and it is no accident: ∪, ∩ and complement are ∨, ∧ and ¬ applied to "is x a member?", so the two lists of laws are one list.

Section 3 shows the other half: two sentences that are not equivalent, P ∨ (Q ∧ ¬P) and (P ∨ Q) ∧ ¬P. One row where they differ is enough, and the program finds it. The brackets moved and the meaning changed, which is why a sentence like P → Q → R is not allowed without brackets: section 5 shows that (P → Q) → R and P → (Q → R) differ, so → does not associate, unlike ∧ and ∨.

Exercises 1.2, settled¶

Section 5 runs the eight exercises of the section. Six are laws. One, exercise 8, is the non-associativity of → that the book wants you to discover. And exercise 4 as printed in this edition, (P ∨ Q) ∧ R ⇔ (P ∧ R) ∨ (P ∧ Q), is not a law: with P false and Q, R true the left side is true and the right false. The intended right side is (P ∧ R) ∨ (Q ∧ R), the distributive law, and the one-row counterexample is how a misprint is caught.

What the program prints¶

Verified output of truth_tables_and_laws.py — regenerated by tools/run_examples.py, never hand-typed.

1. A TRUTH TABLE, BUILT INSIDE OUT (CUNNINGHAM, PROBLEM 1)
   ¬P → (Q ∧ P): the outside connective is →, its parts ¬P and Q ∧ P.
      P         Q         ¬P       Q∧P     ¬P→(Q∧P)
      T         T         F         T         T    
      T         F         F         F         T    
      F         T         T         F         F    
      F         F         T         F         F    
   → is false in one case only, T → F; the two F rows are the rows with P false.

2. TAUTOLOGY, CONTRADICTION, AND WHAT ⇔ MEANS
    P     ¬P   P∨¬P  P∧¬P
    T     F     T     F  
    F     T     T     F  
   P ∨ ¬P is true on every row: a tautology. P ∧ ¬P never: a contradiction.
   ψ ⇔ φ ('logically equivalent') means the columns of ψ and φ agree on
   every row, which is the same as saying ψ ↔ φ is a tautology. ↔ is a
   connective inside a sentence; ⇔ is a claim about two sentences.
   ¬(P∨Q) ⇔ ¬P∧¬Q: columns agree: True;   ¬(P∨Q) ↔ (¬P∧¬Q) is a tautology: True

3. TWO SENTENCES THAT ARE NOT EQUIVALENT (PROBLEM 3): ONE ROW DECIDES
      P         Q      P∨(Q∧¬P)  (P∨Q)∧¬P
      T         T         T         F    
      T         F         T         F    
      F         T         T         T    
      F         F         F         F    
   equivalent: False. The brackets moved and the meaning changed.

4. CUNNINGHAM'S LOGIC LAWS, EVERY ONE CHECKED ON EVERY ROW
   De Morgan 1        ¬(P∨Q) ⇔ ¬P∧¬Q               rows: 8   holds: True
   De Morgan 2        ¬(P∧Q) ⇔ ¬P∨¬Q               rows: 8   holds: True
   commutative        P∧Q ⇔ Q∧P                    rows: 8   holds: True
   associative        P∨(Q∨R) ⇔ (P∨Q)∨R            rows: 8   holds: True
   idempotent         P∧P ⇔ P                      rows: 8   holds: True
   distributive 1     P∧(Q∨R) ⇔ (P∧Q)∨(P∧R)        rows: 8   holds: True
   distributive 2     P∨(Q∧R) ⇔ (P∨Q)∧(P∨R)        rows: 8   holds: True
   double negation    ¬¬P ⇔ P                      rows: 8   holds: True
   tautology law      P∧(Q∨¬Q) ⇔ P                 rows: 8   holds: True
   contradiction law  P∨(Q∧¬Q) ⇔ P                 rows: 8   holds: True
   conditional 1      P→Q ⇔ ¬P∨Q                   rows: 8   holds: True
   conditional 2      P→Q ⇔ ¬(P∧¬Q)                rows: 8   holds: True
   contrapositive     P→Q ⇔ ¬Q→¬P                  rows: 8   holds: True
   biconditional      P↔Q ⇔ (P→Q)∧(Q→P)            rows: 8   holds: True
   Problem 4          (P→R)∧(Q→R) ⇔ (P∨Q)→R        rows: 8   holds: True
   Three letters, eight rows: a finite check that is a complete proof,
   because a law says nothing about the letters except their truth values.

5. EXERCISES 1.2
   1  ¬(P→Q) ⇔ P∧¬Q              True
   2  P↔Q ⇔ (P→Q)∧(Q→P)          True
   3  P ⇔ ¬P→(Q∧¬Q)              True
   4  (P∨Q)∧R ⇔ (P∧R)∨(P∧Q)      False   differ at P, Q, R = T, T, F
   5  (P→Q)∧(P→R) ⇔ P→(Q∧R)      True
   6  (P→R)∨(Q→R) ⇔ (P∧Q)→R      True
   7  P→(Q→R) ⇔ (P∧Q)→R          True
   8  (P→Q)→R ⇔ P→(Q→R)          False   differ at P, Q, R = F, T, F
   Exercise 4 as printed is not a law: with P false, Q and R true, the
   left side is true and the right false; the intended right side is
   (P∧R)∨(Q∧R). Exercise 8 is the book's own example of a non-equivalence:
   → does not associate, so the brackets in P→Q→R must be written.

Po polsku, w skrócie¶

Zdanie zbudowane z liter P, Q, R i spójników ¬ (nie), ∧ (i), ∨ (lub), → (jeśli, to), ↔ (wtedy i tylko wtedy) jest funkcją wartości logicznych tych liter, a tabela prawdy wypisuje ją dla każdego z 2ⁿ wierszy. Tautologia jest prawdziwa w każdym wierszu, sprzeczność w żadnym, a dwa zdania są logicznie równoważne (ψ ⇔ φ), gdy ich kolumny zgadzają się w każdym wierszu; to samo, co powiedzieć, że ψ ↔ φ jest tautologią. Stąd różnica między strzałkami: ↔ to spójnik wewnątrz zdania, ⇔ to twierdzenie o dwóch zdaniach, i właśnie takim twierdzeniem jest każde „prawo logiki". Tabela jest dowodem, a nie próbką, bo prawo nie mówi o literach nic poza ich wartościami logicznymi, a tabela wyczerpuje wszystkie kombinacje. Program sprawdza całą listę praw Cunninghama (de Morgan, rozdzielność, kontrapozycja), znajduje jeden wiersz, w którym dwa podobne zdania się różnią, pokazuje, że → nie jest łączna, i wyłapuje błąd drukarski w zadaniu 4.

Auf Deutsch: Stichwörter¶

Ein Gesetz der Logik sind zwei Spalten einer Wahrheitstafel, die in jeder Zeile übereinstimmen; Tautologie, Kontradiktion, De Morgan.

Stichwörter: Wahrheitstafel, Junktor (und, oder, nicht, wenn-dann), Tautologie, Kontradiktion, logische Äquivalenz, De-Morgan-Gesetze, Aussagenlogik.

Run it yourself¶

From the root of your clone of this repository:

python3 11_Logic/truth_tables_and_laws/examples/truth_tables_and_laws.py