Propositional logic and truth tables

Every proof is built from small logical steps: if this and that, then something else; either this or that; not this. Propositional logic is the study of how such combinations of statements work. It treats whole statements as units, without looking inside them, and asks how the truth of a compound statement depends on the truth of its parts. The rules are few and mechanical, and once you know them you can analyse any argument, spot common errors and rewrite statements into forms that are easier to prove.

Logic also matters well beyond pure mathematics. The conditions in a computer program, the queries you send to a database, the circuits inside a processor and the rules in a legal contract are all built from 'and', 'or', 'not' and 'if … then'. This lesson gives you precise meanings for those words, a systematic way of evaluating them called a truth table, and a list of equivalences that you will use in every lesson that follows.

Propositions and connectives

We use letters such as \(P\), \(Q\) and \(R\) for statements, also called propositions. Each has a truth value, true (T) or false (F). From simple statements we build compound ones with five connectives.

Two of these need comment. In mathematics 'or' is inclusive: \(P \vee Q\) is true when \(P\) is true, when \(Q\) is true, and when both are true. Everyday speech often uses an exclusive or ('soup or salad'), but a mathematician who says '\(n\) is even or \(n\) is a multiple of 3' includes 6, which is both. If you mean exactly one, say so: 'either \(P\) or \(Q\) but not both'.

The conditional \(P \implies Q\) causes the most confusion. It makes a promise: whenever \(P\) holds, \(Q\) holds too. The promise is broken only when \(P\) is true and \(Q\) is false. If \(P\) is false the promise is not tested, and we count the conditional as true. Think of a professor who says 'if you score 90 on the final, you will get an A'. The professor has lied only if a student scores 90 and does not get an A. A student who scores 70 and gets an A anyway has not caught the professor in a lie.

This convention, sometimes called vacuous truth, is exactly what mathematics needs. The theorem 'if \(n\) is an integer and \(n^2\) is even, then \(n\) is even' should count as true, and when we check it for \(n = 3\) the hypothesis \(n^2\) even is false, so that case says nothing. A conditional with a false hypothesis is not a problem; it is simply a case the theorem does not speak about.

Truth tables

A truth table lists every combination of truth values of the simple statements and the resulting truth value of the compound. With two statements there are \(2^2 = 4\) rows, with three there are 8, and with \(n\) there are \(2^n\). Here is the table for all five connectives.

To build the table of a longer expression, work from the inside out, adding a column for each part. For \((P \implies Q) \wedge (Q \implies P)\), first compute the column for \(P \implies Q\), then the column for \(Q \implies P\), then combine them with 'and'. The final column is T, F, F, T, the same as \(P \iff Q\). That is why the biconditional is often described as 'a conditional in both directions', and why a proof of '\(P\) if and only if \(Q\)' usually has two parts.

Tautologies, contradictions and equivalence

A compound statement that is true in every row of its truth table is a tautology. The simplest is \(P \vee \neg P\), the law of the excluded middle: every statement is either true or false. A compound that is false in every row is a contradiction, such as \(P \wedge \neg P\). Proof by contradiction, in lesson 5, works by showing that an assumption leads to a statement of this second kind.

Two compound statements are logically equivalent, written \(A \equiv B\), if they have the same truth value in every row. Equivalent statements can be swapped for each other in any proof. The following equivalences are used constantly; check each one with a truth table at least once.

• Double negation: \(\neg\neg P \equiv P\).

• Commutative laws: \(P \wedge Q \equiv Q \wedge P\) and \(P \vee Q \equiv Q \vee P\).

• Associative laws: \((P \wedge Q) \wedge R \equiv P \wedge (Q \wedge R)\), and the same for \(\vee\).

• Distributive laws: \(P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R)\) and \(P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)\).

• De Morgan's laws: \(\neg(P \wedge Q) \equiv \neg P \vee \neg Q\) and \(\neg(P \vee Q) \equiv \neg P \wedge \neg Q\).

• Conditional as disjunction: \(P \implies Q \equiv \neg P \vee Q\).

• Contrapositive: \(P \implies Q \equiv \neg Q \implies \neg P\).

• Negation of a conditional: \(\neg(P \implies Q) \equiv P \wedge \neg Q\).

De Morgan's laws, named after the nineteenth-century logician Augustus De Morgan, say that negation flips 'and' into 'or' and the other way round. The negation of 'the function is continuous and bounded' is 'the function is discontinuous or unbounded', not 'the function is discontinuous and unbounded'. Getting this wrong is one of the most common errors in proofs, so practise it until it is automatic.

Converse, contrapositive and inverse

Every conditional \(P \implies Q\) has three relatives. The converse is \(Q \implies P\). The contrapositive is \(\neg Q \implies \neg P\). The inverse is \(\neg P \implies \neg Q\). The example above shows that a conditional and its contrapositive always have the same truth value, while the converse can differ. The inverse is the contrapositive of the converse, so it always agrees with the converse.

Take the true statement 'if \(n\) is a multiple of 4, then \(n\) is even'. Its contrapositive, 'if \(n\) is odd, then \(n\) is not a multiple of 4', is also true. Its converse, 'if \(n\) is even, then \(n\) is a multiple of 4', is false: 6 is a counterexample. Confusing a statement with its converse is a classic logical error, known as affirming the consequent. It is the error in 'all cats have tails; my dog has a tail; so my dog is a cat'.

The equivalence of a statement and its contrapositive is the basis of a whole proof technique. Sometimes \(\neg Q \implies \neg P\) is much easier to prove directly than \(P \implies Q\). Lesson 5 shows how to use this.

Necessary and sufficient

Mathematicians express \(P \implies Q\) in many ways, and you need to recognize them all. Each of the following means exactly 'if \(P\), then \(Q\)':

• \(P\) implies \(Q\).

• \(Q\) if \(P\).

• \(P\) only if \(Q\).

• \(P\) is sufficient for \(Q\).

• \(Q\) is necessary for \(P\).

• \(Q\) whenever \(P\).

'Only if' is the trickiest. 'You may enter only if you have a ticket' means that entering requires a ticket: if you enter, then you have a ticket. It does not promise that a ticket gets you in. Similarly, 'a number is divisible by 6 only if it is even' means 'if divisible by 6, then even'. A condition that is both necessary and sufficient is the biconditional, written 'if and only if', often abbreviated iff. Definitions are traditionally written with 'if', but they are always meant as 'if and only if'.

Arguments and rules of inference

An argument is valid if the conclusion must be true whenever all the premises are true. Truth tables can test validity: an argument with premises \(A_1, \dots, A_k\) and conclusion \(C\) is valid exactly when \((A_1 \wedge \dots \wedge A_k) \implies C\) is a tautology. A few valid patterns appear so often that they have names.

• Modus ponens: from \(P\) and \(P \implies Q\), conclude \(Q\).

• Modus tollens: from \(\neg Q\) and \(P \implies Q\), conclude \(\neg P\).

• Hypothetical syllogism: from \(P \implies Q\) and \(Q \implies R\), conclude \(P \implies R\).

• Disjunctive syllogism: from \(P \vee Q\) and \(\neg P\), conclude \(Q\).

Invalid patterns have names too. Affirming the consequent goes from \(Q\) and \(P \implies Q\) to \(P\). Denying the antecedent goes from \(\neg P\) and \(P \implies Q\) to \(\neg Q\). Both can lead from true premises to false conclusions, and a truth table shows the row where it happens.

Truth tables by computer

A truth table is a finite computation, so a short program can build one for any expression and decide whether two expressions are equivalent. The code below represents each statement as a Python function of truth values, checks De Morgan's law and the contrapositive, and confirms that the converse is not equivalent by printing the rows where it differs.

from itertools import product

def implies(p, q):
    return (not p) or q

def table(f, names):
    rows = []
    for vals in product([True, False], repeat=len(names)):
        rows.append((vals, f(*vals)))
    return rows

def equivalent(f, g, n):
    return all(f(*v) == g(*v) for v in product([True, False], repeat=n))

def show(f, names, label):
    print(label)
    for vals, out in table(f, names):
        print("  ", " ".join("T" if x else "F" for x in vals), "->", "T" if out else "F")

show(lambda p, q: implies(p, q), "PQ", "P => Q")
print("De Morgan: not(P and Q) == (not P) or (not Q):",
      equivalent(lambda p, q: not (p and q), lambda p, q: (not p) or (not q), 2))
print("contrapositive equivalent:",
      equivalent(lambda p, q: implies(p, q), lambda p, q: implies(not q, not p), 2))
diff = [v for v in product([True, False], repeat=2)
        if implies(*v) != implies(v[1], v[0])]
print("converse differs in rows (P, Q):", diff)
taut = all(implies(p and implies(p, q), q) for p, q in product([True, False], repeat=2))
print("modus ponens is a tautology:", taut)

P => Q
   T T -> T
   T F -> F
   F T -> T
   F F -> T
De Morgan: not(P and Q) == (not P) or (not Q): True
contrapositive equivalent: True
converse differs in rows (P, Q): [(True, False), (False, True)]
modus ponens is a tautology: True

This brute force works because there are only \(2^n\) rows. For a handful of variables it is instant; for hundreds of variables the number of rows is astronomically large, and deciding whether a formula can ever be true becomes the famous satisfiability problem of computer science, for which no fast general method is known.