Discrete Math › Section B · Logic and proofs › Topic B.3

Truth tables, equivalence, and deduction

Logic cares about the form of a statement, not its subject matter. Truth tables reveal that form completely, and from them come the rules that let you rewrite statements, negate them correctly and decide which arguments are valid.

Building a truth table

"If the stall sells out, the owner is happy" and "if 9 is prime, then 9 is odd" share the form \(P \to Q\), and logic treats them alike. With n statement letters there are \(2^n\) combinations of values, so 2 letters need 4 rows and 3 need 8. List them systematically, then work from the inside out, adding a column for each part and finishing with the main connective, the one applied last. For \(P \wedge \neg Q\), first fill \(\neg Q\), then the conjunction.

Worked example: a three-letter table

Is \(((P \to Q) \wedge (Q \to R)) \to (P \to R)\) always true? A full table has 8 rows, but a shortcut finds the only rows that could fail. 1. The main connective is the outer arrow, so the statement is false only if its hypothesis is true and its conclusion \(P \to R\) is false. 2. \(P \to R\) is false only when P is true and R is false, which leaves 2 of the 8 rows: Q true or Q false. 3. If Q is true, then \(Q \to R\) is false, since R is false. 4. If Q is false, then \(P \to Q\) is false. 5. Either way the hypothesis fails, so no row makes the statement false: it is true in all 8 rows.

Tautologies and contradictions

A tautology is a statement that is true in every row of its truth table, true by its form alone, like the one just checked or \(P \vee \neg P\). A contradiction is false in every row, like \(P \wedge \neg P\). A statement true in some rows and false in others is contingent. A tautology says nothing about the world: "if the train is late, then the train is late or it is raining" is true whatever happens. Its value is that it is a pattern of reasoning that can never mislead.

Logical equivalence

Two statements are logically equivalent, written \(A \equiv B\), when they have the same truth value in every row. Compare columns:

\begin{array}{cc|c|c} P & Q & P \to Q & \neg P \vee Q \\ \hline T & T & T & T \\ T & F & F & F \\ F & T & T & T \\ F & F & T & T \end{array}

The columns match, so \(P \to Q \equiv \neg P \vee Q\): "if it is a multiple of 4, it is even" means "it is not a multiple of 4, or it is even". One mismatched row proves two statements are not equivalent. For example, \((P \vee Q) \to R\) and \((P \to R) \vee (Q \to R)\) differ when P is true and Q and R are false: the first is false, the second true.

The key equivalences

A handful of equivalences, each checked by a truth table, let you rewrite statements without building new tables:

\neg(P \wedge Q) \equiv \neg P \vee \neg Q \qquad \neg(P \vee Q) \equiv \neg P \wedge \neg Q

These are De Morgan's laws: negation turns and into or, and or into and. Also \(\neg\neg P \equiv P\), double negation; \(P \to Q \equiv \neg P \vee Q\); \(P \to Q \equiv \neg Q \to \neg P\), the contrapositive; and, combining these, \(\neg(P \to Q) \equiv P \wedge \neg Q\). That last one matters most: negating an implication gives a conjunction, not another implication.

Worked example: negating without a table

Negate "if it rains, then we stay in and watch a film", with P "it rains", Q "we stay in" and R "we watch a film". 1. The statement is \(P \to (Q \wedge R)\). 2. Negate an implication: \(\neg(P \to (Q \wedge R)) \equiv P \wedge \neg(Q \wedge R)\). 3. Apply De Morgan's law to the second part: \(P \wedge (\neg Q \vee \neg R)\). 4. In words: it rains, and we do not stay in or we do not watch a film. 5. Check one row: with P and Q true and R false, the original is false and the result is true, as a negation should be.

Quantifiers and negation

Truth tables cannot check quantified statements, so reason about the domain. "Not every odd number is prime" means some odd number is not prime, and 9 shows it. In general:

\neg \forall x\, P(x) \equiv \exists x\, \neg P(x) \qquad \neg \exists x\, P(x) \equiv \forall x\, \neg P(x)

Moving a negation past a quantifier switches the quantifier's type. This is De Morgan's law again: "for all" acts like a long conjunction, "there exists" like a long disjunction. Take care with \(\forall\) and \(\vee\): every integer is even or odd, but it is false that every integer is even or every integer is odd.

Worked example: negating a nested statement

Negate "every course has a student who passed it". 1. Symbols: \(\forall c\, \exists s\, \mathrm{Passed}(s, c)\). 2. Move the negation past \(\forall c\), which becomes \(\exists c\). 3. Move it past \(\exists s\), which becomes \(\forall s\). 4. Result: \(\exists c\, \forall s\, \neg \mathrm{Passed}(s, c)\), "some course has no student who passed it". 5. The same steps negate \(\forall x\, \exists y\,(y > x)\) to \(\exists x\, \forall y\,(y \le x)\): some number is at least as large as every number. Note that the negation of \(y > x\) is \(y \le x\), not \(y < x\).

Deduction rules

A deduction rule is an argument form that is always valid: whenever all its premises are true, so is its conclusion. To test a form, find every row where all premises are true; it is valid if the conclusion is true in each, as in the philosophy topic Arguments, validity, and soundness. Three rules recur. Modus ponens: from \(P \to Q\) and P, conclude Q. Modus tollens: from \(P \to Q\) and \(\neg Q\), conclude \(\neg P\). Disjunctive syllogism: from \(P \vee Q\) and \(\neg P\), conclude Q. Equivalence works in both directions; a deduction works in one.

Worked example: testing two argument forms

Use the table for \(P \to Q\), whose rows are TTT, TFF, FTT and FFT. Form 1, modus tollens: premises \(P \to Q\) and \(\neg Q\), conclusion \(\neg P\). 1. \(\neg Q\) is true in rows 2 and 4. 2. \(P \to Q\) is false in row 2, so both premises hold only in row 4. 3. There P is false, so \(\neg P\) is true: the form is valid. Form 2: premises \(P \to Q\) and Q, conclusion P. 4. Q is true in rows 1 and 3, and \(P \to Q\) holds in both. 5. Row 3 has both premises true and P false, so the form is invalid; this error is called affirming the consequent.

Common mistakes to avoid

First, negating \(P \wedge Q\) as \(\neg P \wedge \neg Q\); the connective must switch. Second, negating \(P \to Q\) as another implication instead of \(P \wedge \neg Q\). Third, negating a quantified statement without switching the quantifier. Fourth, negating \(y > x\) as \(y < x\) instead of \(y \le x\). Fifth, claiming non-equivalence because no rewrite was found; only a mismatched row proves it. Sixth, affirming the consequent.

Key takeaways

A truth table with n letters has \(2^n\) rows, filled from the inside out. A tautology is true in every row, a contradiction false in every row. Statements are equivalent when their columns always match; one mismatched row shows they are not. Learn De Morgan's laws, double negation, \(P \to Q \equiv \neg P \vee Q\) and \(\neg(P \to Q) \equiv P \wedge \neg Q\). Negating a quantifier switches \(\forall\) and \(\exists\). A form is valid when every row with all premises true has a true conclusion: modus ponens and modus tollens are valid; affirming the consequent is not.

Flashcards

Flashcard

Rows in a truth table

2ⁿ rows for n statement letters

3 letters give 8 rows.

Test your understanding

Question 1 of 5

How many rows does a truth table need for a statement built from four letters P, Q, R and S?

Question 2 of 5

Which statement is logically equivalent to ¬(P ∧ Q)?

Question 3 of 5

What is the negation of "If it snows, the school closes"?

Question 4 of 5

What is the negation of "Every student passed the quiz"?

Question 5 of 5

An argument has premises P → Q and Q, and conclusion P. What does a truth table show?

← Previous topicNext topic →