Implication and Direct Proof

The Implication Connective

An implication is a statement of the form “If $P$, then $Q$”, written $P \Rightarrow Q$.

• $P$ is the antecedent (or hypothesis, premise)
• $Q$ is the consequent (or conclusion)

Truth Table

$P$	$Q$	$P \Rightarrow Q$
T	T	T
T	F	F
F	T	T
F	F	T

The implication $P \Rightarrow Q$ is false only when $P$ is true and $Q$ is false.

Vacuous Truth

When $P$ is false, the implication $P \Rightarrow Q$ is true regardless of $Q$. This is called vacuous truth.

Example: “If $0 = 1$, then pigs fly” is true (vacuously).

Logical Equivalences

Contrapositive

The contrapositive of $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$.

Theorem: An implication is logically equivalent to its contrapositive: $P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$

Converse

The converse of $P \Rightarrow Q$ is $Q \Rightarrow P$.

Important: The converse is NOT equivalent to the original. Proving the converse does not prove the original implication.

$P$	$Q$	$P \Rightarrow Q$	$Q \Rightarrow P$
T	T	T	T
T	F	F	T
F	T	T	F
F	F	T	T

Inverse

The inverse of $P \Rightarrow Q$ is $\neg P \Rightarrow \neg Q$.

Important: The inverse is equivalent to the converse (not to the original).

Proof Strategies for Implication

Method 1: Direct Proof

To prove $P \Rightarrow Q$:

1. Assume $P$ is true
2. Using logical steps, derive $Q$

Method 2: Proof by Contrapositive

To prove $P \Rightarrow Q$:

1. Assume $\neg Q$ is true
2. Using logical steps, derive $\neg P$

The contrapositive is useful when $\neg Q$ provides a “stronger” starting point than $P$.

Example: Direct Proof

Statement: If $n$ is even, then $n^2$ is even.

Direct proof:

1. Assume $n$ is even
2. Then $n = 2k$ for some integer $k$
3. So $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$
4. Since $2k^2$ is an integer, $n^2$ is even

Example: Proof by Contrapositive

Statement: If $n^2$ is even, then $n$ is even.

Contrapositive: If $n$ is odd, then $n^2$ is odd.

Proof:

1. Assume $n$ is odd
2. Then $n = 2k + 1$ for some integer $k$
3. So $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$
4. Since $2k^2 + 2k$ is an integer, $n^2 = 2m + 1$ for some integer $m$
5. Therefore $n^2$ is odd

By the contrapositive, if $n^2$ is even, then $n$ is even.

Combining Implications

Transitivity

If $P \Rightarrow Q$ and $Q \Rightarrow R$, then $P \Rightarrow R$.

Hypothetical Syllogism

From $P \Rightarrow Q$ and $Q \Rightarrow R$, conclude $P \Rightarrow R$.

Common Pitfalls

Confusing Converse and Implication

Trap: Proving $Q \Rightarrow P$ does not prove $P \Rightarrow Q$.

Example: “If $x > 5$, then $x > 3$” is true. Its converse “If $x > 3$, then $x > 5$” is false (consider $x = 4$).

Assuming the Conclusion

Trap: When proving $P \Rightarrow Q$, do not assume $Q$ at the start. This is circular reasoning.

Forgetting the Antecedent

Trap: When proving $P \Rightarrow Q$, you must begin by assuming $P$. If you forget this, your proof structure is incorrect.

Multiple Antecedents

Implications can have multiple antecedents:

$P_1 \land P_2 \land P_3 \Rightarrow Q$

To prove this:

1. Assume all of $P_1$, $P_2$, $P_3$
2. Derive $Q$

---

Summary

• $P \Rightarrow Q$ means “if $P$ then $Q$”
• The contrapositive $\neg Q \Rightarrow \neg P$ is logically equivalent
• The converse $Q \Rightarrow P$ is NOT equivalent
• Direct proof: assume $P$, derive $Q$
• Proof by contrapositive: assume $\neg Q$, derive $\neg P$