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

Implications and related statements

Nearly every theorem has the shape "if this, then that". This topic explains exactly when such an implication is true, why its truth table has to look the way it does, and how it relates to its converse, inverse and contrapositive.

The workhorse of mathematics

Few claims are true of every object whatsoever, so mathematicians restrict them with "if": if n is a multiple of 6, then n is even. Even claims that look different are implications underneath. "Every prime greater than 2 is odd" says: for any number, if it is a prime greater than 2, then it is odd. In \(P \to Q\), the statement P is the hypothesis, also called the antecedent, and Q is the conclusion, also called the consequent. Read the arrow as "if P, then Q" or "P implies Q".

The truth table

An implication is false in exactly one case: a true hypothesis paired with a false conclusion.

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

Think of a coach's promise: "If you attend every practice, you will play on Saturday." The promise is broken only if you attend every practice and do not play. If you miss a practice, no promise was made about you, so it is not broken. An implication need not involve cause: "If 2 + 2 = 4, then Paris is in France" is true, because both parts are true.

Why a false hypothesis gives true

The bottom two rows surprise people, but mathematics needs them. Every multiple of 4 is even, so "if n is a multiple of 4, then n is even" must hold for each number tested. The number 8 gives true, then true: row 1. The number 6 gives false, then true: row 3. The number 7 gives false, then false: row 4. Since the universal claim is true, rows 3 and 4 must count as true. An implication whose hypothesis is false is called vacuously true. Row 2 would need a multiple of 4 that is not even, and none exists.

Worked example: deciding implications

Decide whether each implication is true. 1. "If 7 is prime, then \(7^2 = 49\)." Both parts are true: row 1, true. 2. "If 15 is prime, then 15 is even." Both parts are false: row 4, true. 3. "If 2 is even, then 2 is odd." True hypothesis, false conclusion: row 2, false. 4. "If 0 > 1, then it will rain in Lima on 1 January 2100." The hypothesis is false, so the implication is true, whatever the weather. 5. "For every integer n, if n is prime, then n is odd." This is false, because \(n = 2\) makes the hypothesis true and the conclusion false. One such counterexample is enough.

Converse, inverse and contrapositive

Each implication \(P \to Q\) has three relatives. The converse is \(Q \to P\); the inverse is \(\neg P \to \neg Q\); the contrapositive is \(\neg Q \to \neg P\). Take "if n is a multiple of 6, then n is a multiple of 3", which is true. Converse: if n is a multiple of 3, then n is a multiple of 6, false, since 9 is a counterexample. Inverse: if n is not a multiple of 6, then n is not a multiple of 3, also false, because of 9. Contrapositive: if n is not a multiple of 3, then n is not a multiple of 6, true. For \(\forall x\,(P(x) \to Q(x))\), keep the quantifier outside and change only the implication inside.

Which relatives agree

Compare all four statements row by row:

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

The contrapositive matches the original in every row, so the two are logically equivalent: they always have the same truth value. The converse and inverse match each other, because the inverse is the contrapositive of the converse, but neither matches the original. A true implication may have a true or a false converse; logic alone cannot tell which.

Worked example: using the contrapositive

A drawer holds only black and white socks. Claim: if you take out 3 socks, then two of them are the same colour. 1. Form the contrapositive: if no two of your socks are the same colour, then you did not take 3 socks. 2. If no two match, you hold at most one black and at most one white sock. 3. That is at most 2 socks, so you did not take 3. 4. The contrapositive is true, so the claim is true. 5. The converse, "if two socks match, you took 3", is false: you might have taken exactly 2 black socks.

If, only if, and if and only if

The biconditional \(P \leftrightarrow Q\) asserts both \(P \to Q\) and its converse \(Q \to P\). Its two halves have names. "P if Q" means \(Q \to P\). "P only if Q" means \(P \to Q\): P cannot happen without Q. For example, "an integer is even if and only if its last digit is 0, 2, 4, 6 or 8" claims that every even integer ends in one of those digits and that every integer ending in one of them is even. Both are true, so the biconditional is true. Proving an "if and only if" theorem means proving two implications.

Many ways to say it

All of these mean \(P \to Q\): if P, then Q; Q if P; P only if Q; P implies Q; Q whenever P; not P unless Q. So do two phrases worth learning exactly. "P is sufficient for Q" means \(P \to Q\): P alone guarantees Q. "Q is necessary for P" also means \(P \to Q\): P cannot be true without Q. Being a multiple of 6 is sufficient for being even, and being even is necessary for being a multiple of 6, but not sufficient, since 4 is even. These match the necessary and sufficient conditions of the philosophy topic Logical statements.

Worked example: what follows from a true implication

Assume it is true that if Leo finishes the report by Friday, he is paid $500. 1. Leo finishes by Friday: he is paid, since the hypothesis holds. 2. Leo is paid: nothing follows about the report, because concluding that he finished would use the converse. 3. Leo does not finish: nothing follows about payment, because that would use the inverse. 4. Leo is not paid: he did not finish by Friday, by the contrapositive, which is equivalent to the original.

Common mistakes to avoid

First, calling an implication false because its hypothesis is false; it is then vacuously true. Second, assuming a converse is true because the original is. Third, confusing the inverse with the contrapositive: only the contrapositive negates and swaps. Fourth, reading "P only if Q" as \(Q \to P\). Fifth, swapping "necessary" and "sufficient". Sixth, offering a case with a false hypothesis as a counterexample.

Key takeaways

\(P \to Q\) is false only when P is true and Q is false, so a false hypothesis makes it vacuously true; the universal claim "every multiple of 4 is even" shows why. The converse \(Q \to P\) and inverse \(\neg P \to \neg Q\) are not equivalent to the original, but the contrapositive \(\neg Q \to \neg P\) is. A biconditional asserts an implication and its converse. "P only if Q", "P is sufficient for Q" and "Q is necessary for P" all mean \(P \to Q\).

Flashcards

Flashcard

P → Q

Implication: if P, then Q

False only when P is true and Q is false.

Test your understanding

Question 1 of 5

Which of these implications is false?

Question 2 of 5

What is the contrapositive of "If n is a multiple of 4, then n is even"?

Question 3 of 5

"A triangle is equilateral only if it is isosceles." Which statement means the same?

Question 4 of 5

Every multiple of 10 is even. What is being a multiple of 10, as a condition for being even?

Question 5 of 5

It is true that if Mia's code passes every test, it is merged. Mia's code was not merged. What follows?

← Previous topicNext topic →