PG1.2 Implication, converse and contrapositive

Simulate

Check the claim with numbers

"If $P$ , then $Q$ " is an implication, written $P \Rightarrow Q$ . Mathematics makes it false in one case only: $P$ true and $Q$ false. The section after the conjecture explains why; here, test what that rule does.

Take the whole numbers from 1 to 20 and the claim "if $n$ is a multiple of 4, then $n$ is even". Swap its parts and you get the converse, "if $n$ is even, then $n$ is a multiple of 4". Negate both parts and swap them, and you get the contrapositive, "if $n$ is not even, then $n$ is not a multiple of 4".

def implies(p, q): return (not p) or q # false only when p is true and q is false ns = range(1, 21) original = [n for n in ns if not implies(n % 4 == 0, n % 2 == 0)] converse = [n for n in ns if not implies(n % 2 == 0, n % 4 == 0)] contrapositive = [n for n in ns if not implies(n % 2 != 0, n % 4 != 0)] print("original fails at:", original) print("converse fails at:", converse) print("contrapositive fails at:", contrapositive)

⌘/Ctrl + Enter runs the cell

The claim and its contrapositive hold for all 20 numbers. The converse fails at 2, 6, 10, 14 and 18: each is even but not a multiple of 4. The next cell compares the three forms in all four cases of $P$ and $Q$ .

from itertools import product def implies(p, q): return (not p) or q print("P Q P=>Q Q=>P notQ=>notP") for P, Q in product([True, False], repeat=2): row = [implies(P, Q), implies(Q, P), implies(not Q, not P)] print(f"{P!s:6} {Q!s:6} {row[0]!s:6} {row[1]!s:6} {row[2]!s}")

⌘/Ctrl + Enter runs the cell

The columns for $P \Rightarrow Q$ and the contrapositive match in all four rows. The converse differs from them in rows 2 and 3.

Conjecture

P

Four rows are every case, so the table is already a proof by exhaustion. The proof below explains why the two match: each implication fails in exactly one case, and it is the same case.

What "if … then" means

Think of an implication as a promise: "if the fund beats the index, the manager gets a bonus". It is broken only when the fund beats the index and no bonus is paid.

When the fund does not beat the index, the promise is kept, whatever happens to the bonus. So an implication with a false hypothesis counts as true. This is the rule the cell's implies used.

Rule: Implication

\begin{gathered} P \Rightarrow Q \text{ is false only when} \\ P \text{ is true and } Q \text{ is false} \end{gathered}

$P$ is the hypothesis and $Q$ the conclusion. To prove $P \Rightarrow Q$ , assume $P$ and show $Q$ follows. To disprove it, find one case with $P$ true and $Q$ false.

Here $\neg$ means "not", as in lesson PG1.1. Three forms are built from one implication by swapping or negating its parts:

Name	Form	From "multiple of 4 $\Rightarrow$ even"
converse	$Q \Rightarrow P$	even $\Rightarrow$ multiple of 4
contrapositive	$\neg Q \Rightarrow \neg P$	not even $\Rightarrow$ not a multiple of 4
inverse	$\neg P \Rightarrow \neg Q$	not a multiple of 4 $\Rightarrow$ not even

Mathematics has many ways to say $P \Rightarrow Q$ : " $P$ implies $Q$ ", " $Q$ whenever $P$ ", " $P$ only if $Q$ ". It also says " $P$ is sufficient for $Q$ " and " $Q$ is necessary for $P$ ". When both $P \Rightarrow Q$ and its converse hold, write $P \Leftrightarrow Q$ , read " $P$ if and only if $Q$ ".

Format 1

Reorder the steps

Here is a proof that an implication and its contrapositive are equivalent, with its lines shuffled. Put them in order.

The two implications are false in the same single case and true in all others, so they are equivalent.
Take any statements $P$ and $Q$ . An implication is false in only one case: its hypothesis true and its conclusion false.
So $P \Rightarrow Q$ is false exactly when $P$ is true and $Q$ is false.
That happens exactly when $Q$ is false and $P$ is true, the same case as for $P \Rightarrow Q$ .
Its contrapositive, $\neg Q \Rightarrow \neg P$ , is false exactly when $\neg Q$ is true and $\neg P$ is false.

Format 3

Find the error

This argument tries to prove that every even number from 1 to 20 is a multiple of 4. The simulation says that is false. Select the line that goes wrong, then say why.

Simulate

A claim of your own to prove

The table has a fourth column to add: the inverse, $\neg P \Rightarrow \neg Q$ . Each row below prints $P$ , $Q$ , then $P \Rightarrow Q$ , the converse and the inverse.

from itertools import product def implies(p, q): return (not p) or q for P, Q in product([True, False], repeat=2): print(P, Q, implies(P, Q), implies(Q, P), implies(not P, not Q))

⌘/Ctrl + Enter runs the cell

The converse and the inverse match in all four rows. Both differ from $P \Rightarrow Q$ in the rows with $P$ and $Q$ of opposite truth values.

Conjecture

P

Again the table covers every case. Now write the reasons in sentences, and use the theorem you have just proved instead of a table where you can.

Format 4

Write it

Prove both parts. First, show that $P \Rightarrow Q$ and $Q \Rightarrow P$ are not equivalent: find a case where their truth values differ, and real statements that show it. Second, show that $Q \Rightarrow P$ is equivalent to $\neg P \Rightarrow \neg Q$ .

Your proof

Saved in this browser as you type.

Write your own first: a proof you have tried to write teaches far more than one you only read.

Stage PG2 uses the contrapositive as a proof technique: to prove $P \Rightarrow Q$ , it is enough to prove $\neg Q \Rightarrow \neg P$ .

P \Rightarrow Q

Implication, converse and contrapositive

Check the claim with numbers

What "if … then" means

Rule: Implication

Reorder the steps

Find the error

A claim of your own to prove

Write it

Summary card

Free further reading