Mathematical-Reasoning · Unit 11 · Video 1 · Interactive Practice

Direct, Contrapositive or Contradiction: Choosing a Proof

IKey Formulas

Method	Process	Why it is valid	Often indicated when
Direct proof	Assume $P$ ; show $Q$	When $P$ is false, $P \to Q$ is true, so there is nothing to prove	Neither $P$ nor $Q$ contains a negation
Contrapositive	Assume $\neg Q$ ; show $\neg P$	$P \to Q \equiv \neg Q \to \neg P$	$P$ and $Q$ are both negations, or $Q$ is a disjunction
Contradiction	Assume $P \wedge \neg Q$ ; reach a contradiction	$\neg(P \to Q) \equiv P \wedge \neg Q$	$Q$ is a negation and $P$ is not, or $Q$ is a disjunction
De Morgan's Law	$\neg(Q_1 \vee Q_2) \equiv \neg Q_1 \wedge \neg Q_2$	A disjunction is false only when both parts are false	The conclusion contains or

Key Insight: All three methods rule out the same single row of the truth table, the row where $P$ is true and $Q$ is false. They differ only in what they assume on the way there.

IIOne Row to Rule Out

Each method proves $P \to Q$ by eliminating its only false row: $P$ true, $Q$ false.

Step 1

IIIReading the Form of the Statement

Where the negations sit, and whether the conclusion contains or, indicates which method to try first.

Statement

IVA Contradiction With No Fixed Target

Assuming an integer $n$ with $4 \mid (n^2 - 2)$ leads forward, line by line, to $1$ being even.

Line 1

1. Assume $P \wedge \neg Q$ : there is an integer $n$ with $4 \mid (n^2 - 2)$ .

2. There is an integer $k$ with

n^2 - 2 = 4k.

3. Adding $2$ to both sides, $n^2$ is even:

n^2 = 4k + 2 = 2(2k + 1).

4. Since $n^2$ is even, $n$ is even, so there is an integer $m$ with

n = 2m.

5. Substituting $n = 2m$ into line 3:

4m^2 = 4k + 2.

6. Subtracting $4k$ from both sides and dividing by $2$ :

2m^2 - 2k = 1.

7. Factoring out $2$ , the integer $1$ is even:

1 = 2(m^2 - k).

But $1$ is odd, and no integer is both even and odd.

VQuiz Questions

Problem 1 · Which Method Does the Form Indicate?

Given: the statement if $a$ and $b$ are integers, then $a^2 - 4b \neq 2$ . Which method does its form indicate?

✅ Correct! The conclusion

a^2 - 4b \neq 2

is a negation and the hypothesis is not, so we assume

P

together with

a^2 - 4b = 2

, an equation we can work forward from.

❌ Not quite. A direct proof is indicated when neither part contains a negation, but the conclusion

a^2 - 4b \neq 2

is a negation, and a direct proof gives us no equation to work toward.

❌ Not quite. The contrapositive is indicated when both parts are negations or the conclusion contains or. Here the hypothesis is positive, so the contrapositive would have to conclude that

a

is not an integer or

b

is not an integer.

Show solution

Write the statement as $P \to Q$ with

$P$ : $a$ and $b$ are integers (no negation),
$Q$ : $a^2 - 4b \neq 2$ (a negation, and not a disjunction).

The conclusion is a negation and the hypothesis is not, which is the form that indicates a proof by contradiction. Its assumption $P \wedge \neg Q$ reads: $a$ and $b$ are integers and $a^2 - 4b = 2$ . That gives both an equation and the integer facts to work forward from.

Problem 2 · Negating an Or

Given: for real numbers $x$ and $y$ , if $x + y \geq 2$ , then $x \geq 1$ or $y \geq 1$ . Which statement is its contrapositive?

✅ Correct! By De Morgan's Law the negation of

x \geq 1

y \geq 1

is the conjunction

x < 1

and

y < 1

, which becomes the hypothesis of

\neg Q \to \neg P

❌ Check the negation of the or. The negation of a disjunction is a conjunction:

\neg(Q_1 \vee Q_2) \equiv \neg Q_1 \wedge \neg Q_2

, so the or must become and.

❌ Not quite. This swaps hypothesis and conclusion without negating them, which gives the converse

Q \to P

, and the converse is not logically equivalent to

P \to Q

❌ Not quite. The contrapositive starts from

\neg Q

, not

\neg P

, and this version also negates the or as an or. Its form is

\neg P \to (\neg Q_1 \vee \neg Q_2)

, which is not equivalent to

P \to (Q_1 \vee Q_2)

Show solution

Write the statement as $P \to (Q_1 \vee Q_2)$ with $P$ : $x + y \geq 2$ , $Q_1$ : $x \geq 1$ , $Q_2$ : $y \geq 1$ . The contrapositive is $\neg(Q_1 \vee Q_2) \to \neg P$ .

By De Morgan's Law, $\neg(Q_1 \vee Q_2) \equiv \neg Q_1 \wedge \neg Q_2$ , which reads $x < 1$ and $y < 1$ . The negation of $P$ is $x + y < 2$ . So the contrapositive is

\text{if } x < 1 \text{ and } y < 1, \text{ then } x + y < 2.

This version is easy to prove directly: adding the two inequalities gives $x + y < 1 + 1 = 2$ .

Problem 3 · Carry Out the Contradiction

Prove by contradiction: if $a$ and $b$ are integers, then $a^2 - 4b \neq 2$ . Answer both parts.

What does the proof assume?

After showing $a$ is even and writing $a = 2m$ , which line gives the contradiction?

✅ Correct! From

a^2 - 4b = 2

the proof reaches

1 = 2(m^2 - b)

, so the odd integer

1

would be even, which is impossible.

❌ Not quite. This assumes

Q

, the conclusion we are trying to prove. A proof by contradiction assumes

P

and

\neg Q

, and

\neg Q

here is

a^2 - 4b = 2

❌ Not quite. This negates the hypothesis as well. The negation of

P \to Q

P \wedge \neg Q

, so we keep

P

a

and

b

are integers.

❌ Not quite. A proof by contradiction assumes

P \wedge \neg Q

❌ Check the substitution. The square

(2m)^2

equals

4m^2

, not

2m^2

, and

m^2 - 2b = 1

is no contradiction, since an integer

m^2 - 2b

can equal

1

❌ Not yet. This line is true, and it is how we learn that

a

is even, but nothing contradicts it. The contradiction comes only after substituting

a = 2m

❌ Not quite. Substitute

a = 2m

into

a^2 - 4b = 2

and simplify.

Show solution

We assume, to the contrary, that there are integers $a$ and $b$ with $a^2 - 4b = 2$ . Then

a^2 = 4b + 2 = 2(2b + 1),

and $2b + 1$ is an integer by closure, so $a^2$ is even. Since $a^2$ is even, $a$ is even, so $a = 2m$ for some integer $m$ . Substituting,

4m^2 - 4b = 2, \qquad 2m^2 - 2b = 1, \qquad 1 = 2(m^2 - b).

Since $m^2 - b$ is an integer, $1$ is even. But $1$ is odd, and no integer is both even and odd. This contradiction shows that the assumption is false, so $a^2 - 4b \neq 2$ for all integers $a$ and $b$ .

Problem 4 · What Was Actually Proved?

Given: a student sets out to prove $P \to Q$ , assumes $\neg P$ , and correctly derives $\neg Q$ . What has been proved?

✅ Correct! The statement

\neg P \to \neg Q

is the contrapositive of the converse

Q \to P

, so the converse is what has been proved;

P \to Q

is still open.

❌ Not quite. The contrapositive of

P \to Q

\neg Q \to \neg P

: it assumes the negation of the conclusion. When

P

is true and

Q

is false,

\neg P \to \neg Q

is true while

P \to Q

is false, so they are not equivalent.

❌ Not quite. The negation

\neg(P \to Q)

is equivalent to

P \wedge \neg Q

, a claim that

P

is true; deriving

\neg Q

from

\neg P

says nothing of the kind.

❌ Not quite. Only one conditional was proved. Together the two would give

P \leftrightarrow Q

, but

P \to Q

still needs its own proof.

Show solution

Assuming $\neg P$ and deriving $\neg Q$ is a direct proof of $\neg P \to \neg Q$ . Its contrapositive is $\neg(\neg Q) \to \neg(\neg P)$ , that is $Q \to P$ , so

\neg P \to \neg Q \equiv Q \to P.

The student has proved the converse. The converse is not equivalent to $P \to Q$ : in the row with $P$ true and $Q$ false, $Q \to P$ is true and $P \to Q$ is false. To prove $P \to Q$ through the contrapositive, we must assume $\neg Q$ and show $\neg P$ .

Solved: 0 / 4