2.5: Proof Strategies

Proof strategies

Finding a proof is very much the same as solving a puzzle that tells you a starting position and a goal, and gives specific rules about exactly what steps you are allowed to take to complete the task. At each step (of a proof or a puzzle) there are several options for what to do, and you need to choose the right one. There is no simple recipe that will always tell you what to do; being successful requires the same skills that you need to solve a maze.

Exercise \(\PageIndex{1}\)

Find a path through each maze from the top left corner to the bottom right corner.

There is no substitute for practice, but here are some suggestions and strategies to keep in mind when doing proofs.

Work forwards from what you have. Look at the hypotheses (and any other assertions that you have derived so far). Think about the elimination rules for the main operators in these assertions. These will tell you what your options are. For example:

• If you have \(P \& Q\), you can immediately obtain both \(P\) and \(Q\).
• If you have both \(P\) and \(P \Rightarrow Q\), you can use \(\Rightarrow\)-elimination to obtain \(Q\).
• If you have \(P \lor Q\), you should consider using a proof by cases.

Exercise \(\PageIndex{2}\)

Give a two-column proof of the deduction \[\text{$A \Rightarrow (B \& C)$, $A$, \ $\therefore C$}\]

Work backwards from what you want. The ultimate goal is to derive the conclusion. Look at the conclusion and ask what the introduction rule is for its main logical operator. This gives you an idea of where you want to be just before the last line of the proof. Then you can treat this line as if it were your goal; we call it a subgoal because it represents partial progress toward the true goal. Ask what you could do to derive the subgoal. For example:

• If your conclusion is \(A\&B\), then you need to figure out a way to prove \(A\) and a way to prove \(B\).
• If your conclusion is a conditional \(A\Rightarrow B\), plan to use the \(\Rightarrow\)-intro rule. This requires starting a subproof in which you assume . In the subproof, you want to derive .
• The last of the four mazes in Exercise 2.5.1 is easy if you work backwards from the finish, instead of forward from the start.

Exercise \(\PageIndex{3}\)

Give a two-column proof of the deduction \[\text{$(P \lor Q) \Rightarrow (R \& S)$, $(R \lor S) \Rightarrow (P \& Q)$, $\therefore P \Rightarrow Q$}\]

Try breaking the proof down into cases. If it looks like you need an additional hypothesis (\(A\)) to prove what you want, try considering two cases: since \(A \lor \lnot A\) is a tautology (“Law of Excluded Middle”), it suffices to prove that \(A\) and \(\lnot A\) each yield the desired conclusion.

Exercise \(\PageIndex{4}\)

[pr.basicproofargPQRS-S] Give a two-column proof of the deduction \[\text{$P \Rightarrow Q$, $\lnot P \Rightarrow R$, $(Q \lor R) \Rightarrow S$, $\therefore S$}\]

Look for useful subgoals. Working backwards is one way to identify a worthwhile subgoal, but there are others. For example, if you have \(A \Rightarrow B\), you should think about whether you can obtain \(A\) somehow, so that you can apply \(\Rightarrow\)-elimination.

Exercise \(\PageIndex{5}\)

[pr.basicproofargPQRS-R->P] Give a two-column proof of the deduction \[\text{$(R \lor S) \Rightarrow (P \lor Q)$, $\lnot Q$, \ $\therefore R \Rightarrow P$}\]

Change what you are looking at. Replacement rules can often make your life easier; if a proof seems impossible, try out some different substitutions. For example:

• the Rules of Negation should become second nature; they can often transform an assertion into a more useful form.
• Remember that every implication is logically equivalent to its contrapositive. The contrapositive may be easier to prove as a conclusion, and it might be more useful as a hypothesis.

Exercise \(\PageIndex{6}\)

Give a two-column proof of the deduction \[\text{$P$, $\lnot (P \& Q)$, $Q \lor R$, \ $\therefore R$ }\]

Do not forget proof by contradiction. If you cannot find a way to show something directly, try assuming its negation, and then look for a contradiction. For example, instead of proving \(A \lor B\) directly, you can assume both \(\lnot A\) and \(\lnot B\), which is likely to make the work easier.

Exercise \(\PageIndex{7}\)

Give a two-column proof of the deduction \[\text{$P \Rightarrow Q$, $Q \Rightarrow \lnot P$, \ $\therefore \lnot P$ }\]

Repeat as necessary. After you have made some progress, by either deriving some new assertions or deciding on a new goal that would represent substantial progress, see what the above strategies suggest in your new situation.

Perist. Try different things. If one approach fails, try something else. When solving a difficult maze, you should expect to have to backtrack several times, and the same is true when doing proofs.

Exercise \(\PageIndex{8}\)

Give a two-column proof of each of these deductions.

1. \((P \& \lnot Q) \Rightarrow (Q \lor R)\), \(\therefore (P \& \lnot Q) \Rightarrow (R \lor S)\)
2. \(P \Rightarrow (Q \lor R)\), \(Q \Rightarrow \lnot P\), \(R \Rightarrow S\), \(\therefore P \Rightarrow S\)