Proof Strategy: Working Backward

Building Short Proofs gave the main idea: work backward from the conclusion. This lesson turns it into a short checklist, with the cases that trip people up most.

Key idea

Find the conclusion, or its letters, inside the premises. Plan the last step first: which rule would produce the conclusion, and what does it need? Then treat that need as a new goal. When the conclusion contains a letter that appears in no premise, Add is almost always how it gets in.

Why it works

Working forward, the number of possible lines grows quickly; working backward, each step narrows the search to what one rule needs. It is like planning a trip from the destination: to arrive by train, you must first reach the station. Each premise is a resource; the conclusion tells you which resources to spend.

Working backward.
The conclusion is …	Likely last step	You will need
the consequent of a conditional premise	MP	that conditional's antecedent
the negation of an antecedent	MT	the negation of the consequent
a disjunct of a disjunction premise	DS	the negation of the other disjunct
a conjunct of a conjunction	Simp	the conjunction
a conjunction	Conj	each conjunct
a disjunction with a new letter	Add	one of its disjuncts
a conditional	HS	two conditionals that chain

Planned backward, written forward.

Worked examples

Worked example: Plan backward

Premises: $t \to r$, $s \to t$, $s$. Conclusion $r$. Plan.

$r$ is the consequent of $t \to r$: last step MP, needing $t$.
$t$ is the consequent of $s \to t$: MP again, needing $s$.
$s$ is a premise.

Answer: Line 4: $t$ (MP 2, 3). Line 5: $r$ (MP 1, 4).

Worked example: A new letter

Premises: $p \to q$, $p$. Conclusion $q \lor u$. How does $u$ get in?

$u$ is in no premise.
Get $q$ by MP, then Add.

Answer: Line 3: $q$ (MP 1, 2). Line 4: $q \lor u$ (Add 3).

Worked example: Two goals

Premises: $p \land q$, $p \to r$, $q \to s$. Conclusion $r \land s$.

Last step Conj: need $r$ and $s$.
$r$: MP from $p \to r$ and $p$ (Simp 1).
$s$: MP from $q \to s$ and $q$ (Simp 1).

Answer: Six lines: Simp, MP, Simp, MP, Conj.

When you are stuck, try writing the goal on scrap paper and asking which premise mentions it. If a premise mentions it inside a conditional, the other side of that conditional becomes your next goal. If none mentions it at all, look for Add. If two premises mention it, try each; one of the routes usually comes out shorter.

Common mistake

Never using Add, because it seems to lose information. When the conclusion has a letter that no premise has, no other rule can produce it. Look for that clue first: it tells you the last step at once.

Proof Strategy: Working Backward

Worked examples

Practice

Builds on

Leads to

Sources and further reading