Fundamentals of Computing: Proof by Contradiction and Contrapositive

Lesson overview

Use indirect proof techniques when direct proof is awkward.

CourseFundamentals of Computing

Topic strandProof

Assessment styleDigital exam practice

EvidenceWorked answer plus justification

Starter: make the model explicit

Before reading the worked example, write down the objects involved, the claim being made and the notation you expect to use. This prevents the common error of calculating before modelling.

Learning objectives

State the contrapositive of an implication.
Use contradiction to expose an impossible assumption.
Decide when indirect proof is appropriate.

Learning outcomes

By the end of this lesson, you can state the contrapositive of an implication.
By the end of this lesson, you can use contradiction to expose an impossible assumption.
By the end of this lesson, you can decide when indirect proof is appropriate.

Key vocabulary

What this lesson is about

Proof by contrapositive proves an implication by proving its logically equivalent reverse-negative form. Proof by contradiction assumes the conclusion is false and derives an impossibility.

A contradiction proof must name the impossible result. For instance, assuming an integer is both odd and even forces 2a = 2b + 1, so 1 = 2(a - b), which says an odd number is even.

These techniques are useful when a direct route is awkward. The danger is mixing them with the converse, which is not equivalent to the original implication.

Terms, acronyms and named methods

These are the phrases and named techniques used in this lesson. Read this section before the worked example so the notation and examples have a clear meaning.

ContrapositiveNamed proof technique. For an implication P ⇒ Q, the contrapositive is ¬Q ⇒ ¬P. It is logically equivalent to the original implication.

Proof by contradictionNamed proof technique. A proof method that assumes the desired conclusion is false and derives an impossibility.

ConverseLogic term. For P ⇒ Q, the converse is Q ⇒ P. It is not generally equivalent to the original statement.

NegationLogic term. The logical 'not' of a statement.

Formal notation and definitions

Contrapositive of P \Rightarrow Q is \negQ \Rightarrow \negP. Proof by contradiction assumes \negC and derives a contradiction ⊥. P \Rightarrow Q is equivalent to \negQ \Rightarrow \negP, not to Q \Rightarrow P.

How to read the symbols

$P\Rightarrow Q$ The original implication.

$\neg Q\Rightarrow\neg P$ The contrapositive, logically equivalent to the original implication.

$\bot$ Contradiction: an impossible result under the assumptions.

Use the contrapositive only because it is logically equivalent to the original implication. Do not confuse it with the converse.

Degree-level reasoning

A proof is a general argument over a whole domain, not a persuasive example. The domain and assumptions must be visible.

The strongest answers identify the structure of the claim first: universal, existential, implication, equality, recurrence or invariant.

Do not stop at a correct-looking answer. State why the method is valid, whether the result depends on a hidden assumption, and what would count as a counterexample.

Worked formal model

This section shows the model, notation, calculation and interpretation as one worked answer. The notation is part of the reasoning, not decoration.

1. Context and objects

To prove if a value is divisible by 4 then it is even, the contrapositive says if it is not even then it is not divisible by 4.

Objects: the implication P ⇒ Q, its contrapositive ¬Q ⇒ ¬P, the temporary contradiction assumption, and the impossible conclusion.

Model cue: Use two equivalent routes for implication: prove P ⇒ Q directly, or prove ¬Q ⇒ ¬P as the contrapositive.

2. Mathematical working

P\Rightarrow Q\quad\text{is equivalent to}\quad \neg Q\Rightarrow\neg P

\text{If }n\text{ is not even, then }n=2k+1

2k+1\ne4m\quad\text{for any }m\in\mathbb{Z}

n=2a\land n=2b+1\Rightarrow 2(a-b)=1\quad\text{which is impossible}

Plain text version

Contrapositive of P ⇒ Q is ¬Q ⇒ ¬P.
Proof by contradiction assumes ¬C and derives a contradiction ⊥.
P ⇒ Q is equivalent to ¬Q ⇒ ¬P, not to Q ⇒ P.

Worked use: To prove 'if n is divisible by 4 then n is even', prove the contrapositive: if n is not even, then n is not divisible by 4. An odd integer has form 2k + 1, which cannot equal 4m. For contradiction, assume an integer is both even and odd: n = 2a and n = 2b + 1, so 2a = 2b + 1 and 2(a - b) = 1, impossible because the left side is even.

3. How to read the working

Read P ⇒ Q as the original implication and ¬Q ⇒ ¬P as the contrapositive; these have the same truth value.
When using the contrapositive, start by assuming the conclusion Q is false, not by assuming P is true.
In the integer example, 'not even' means n = 2k + 1, which cannot be equal to 4m.
For proof by contradiction, make the temporary assumption explicit, then derive an impossible statement such as 2(a - b) = 1.
Do not replace the contrapositive with the converse Q ⇒ P. The converse is a different claim.

4. Computing meaning and check

The proof route is legitimate because the contrapositive is logically equivalent to the original implication. The converse is a different claim.

Now check: State the converse of the divisibility claim and explain why it is not equivalent. Then write the contradiction reached when assuming one integer is both even and odd.

Worked example

From scenario to formal reasoning

Scenario: To prove if a value is divisible by 4 then it is even, the contrapositive says if it is not even then it is not divisible by 4.

Method: Use the definitions and notation introduced above, then state what the result means in this computing scenario.

Reveal model answer

To prove 'if n is divisible by 4 then n is even', prove the contrapositive: if n is not even, then n is not divisible by 4. An odd integer has form 2k + 1, which cannot equal 4m. For contradiction, assume an integer is both even and odd: n = 2a and n = 2b + 1, so 2a = 2b + 1 and 2(a - b) = 1, impossible because the left side is even.

Worked solution structure

How a strong answer should be written

Define: State the domain and the objects under discussion. For this lesson, begin from Contrapositive of P ⇒ Q is ¬Q ⇒ ¬P.
Apply: Use the relevant definition from proof; do not rely on the diagram, wording or intuition alone.
Check: Test a boundary case, counterexample candidate or representation limit.
Conclude: Write one sentence that connects the formal result back to the computing scenario.

Common misconception

A common mistake is confusing the converse with the contrapositive. The converse is not logically equivalent to the original statement.

Guided practice

State the contrapositive of 'if n is divisible by 4, then n is even' and prove it.
State the converse and explain why it is a different claim.
Write a proof by contradiction that no integer is both odd and even.
Identify the impossible statement that creates the contradiction.

Quick checks

1. The contrapositive of P ⇒ Q is:

¬P ⇒ ¬Q¬Q ⇒ ¬PQ ⇒ P

2. In proof by contradiction, you assume:

the conclusion is false and derive an impossibilitythe converse is trueseveral examples are enough

Digital exam practice

Example exam task

Prove one implication by contrapositive and prove by contradiction that no integer is both odd and even. Identify the converse and explain why it does not prove the original.

Notation toolkit

P\Rightarrow Q

Means: the original implication

How to use: Use it to identify the assumption and conclusion.

\neg Q\Rightarrow\neg P

Means: the contrapositive of the implication

How to use: Use it when the original direction is awkward.

\bot

Means: a contradiction or impossible statement

How to use: Use it when an assumption leads to something false.

What a good answer is expected to show

A strong answer for this lesson defines the implication P ⇒ Q, its contrapositive ¬Q ⇒ ¬P, the temporary contradiction assumption, and the impossible conclusion, applies the proof method with visible working, and finishes by interpreting the result in the computing scenario.

How to solve it

Read P ⇒ Q as the original implication and ¬Q ⇒ ¬P as the contrapositive; these have the same truth value.
When using the contrapositive, start by assuming the conclusion Q is false, not by assuming P is true.
In the integer example, 'not even' means n = 2k + 1, which cannot be equal to 4m.
For proof by contradiction, make the temporary assumption explicit, then derive an impossible statement such as 2(a - b) = 1.
Do not replace the contrapositive with the converse Q ⇒ P. The converse is a different claim.

Model answer

Reveal model answer

P\Rightarrow Q\equiv\neg Q\Rightarrow\neg P

n=2a\land n=2b+1\Rightarrow2(a-b)=1\Rightarrow\bot

For 'if 4 | n then n is even', the contrapositive is 'if n is not even then 4 ∤ n'. If n is odd, n = 2k + 1, which cannot equal 4m. For contradiction, assume n is both even and odd: n = 2a and n = 2b + 1, so 2(a - b) = 1, impossible. The converse is 'if n is even then 4 | n', which is false for n = 2.

Practise next

State the contrapositive of 'if n is divisible by 4, then n is even' and prove it.
State the converse and explain why it is a different claim.

Self-marking criteria

States the original implication and its contrapositive.
Does not confuse contrapositive with converse.
Assumes the negation for the contradiction proof.
Derives an impossible parity statement.
States why the proof route is valid.

Extension

Change one assumption in the worked scenario and decide whether the same method still applies. If it does not, name the exact point where the reasoning breaks.

Study route

Save one clean worked answer from this lesson. Include the problem statement, notation, working, final answer and a short note explaining the computing meaning of the result.

Next lesson: Mathematical Induction for Computing Problems.