CONSTRUCTING PROOFS

A proof is a finite series of  formulas, beginning with the premises of an argument and ending with its conclusion, in which each line is either a premise or derived from the premises according to established rules of inference and equivalence.  Constructing a proof for an argument definitively establishes that the argument is valid.  Failure to construct a proof, however, establishes nothing.  One's inability to construct a proof may be caused by the non-validity of the argument in question, but it may be caused by a lack of skill and insight.

A proof is very much like a set of instructions on how to get from A to B, where A is the set of premises in an argument and B is the conclusion.  A proof answers the question "How could I get from the premises of an argument to its conclusion"?  Each line in a proof after the premises is analogous to a step in a set of instructions--first you go here, then your turn left at first stop light, and so forth.  The rules of inference and equivalence define the legitimate moves we can make--only those steps that are justified by the rules are legitimate.

Consider the following argument:

 1.  P→  Q premise        ∴R 2.  ~T ▼  P premise 3.  T premise 4.  ~Q ▼ S premise 5.   S   → R premise

In order to get to R, you need somehow to get S, because S plus premise 5 gets you R by Modus Ponens.  OK, so how do we get to S?  Well, if we had  ~~Q, we could get S from line 4 by Disjunctive Syllogism.  So far, so good, but how do we get ~~Q?  Well, if we had Q, we could get ~~Q from Double Negation, and if we had P, we could get Q from 1 by Modus Ponens.  And if we had ~~T, we could get P by Disjunctive Syllogism, and we can get ~~T from line 3 by Double Negation.  Let's complete the proof.

 1.  P →  Q premise        ∴R 2.  ~T ▼  P premise 3.  T premise 4.  ~Q ▼ S premise 5.   S   → R premise 6.  ~~T 3  DN 7.  P 2, 6 DS 8,.  Q 1, 7 MP 9.  ~~Q 8 DN 10.  S 4, 9 DS 11.  R 5, 10 MP

Constructing a proof requires a bit of skill and imagination.  Perhaps the best way to start is by identifying some sub-goals, that is, lines that you would like to have.  In the example above, I set as a goal the line S because S would allow me get to the conclusion.  I call this process backwards tracking--start at the conclusion and work backwards toward the premises.  Once you get to the premises you are done!

Another useful procedure is simple to scan the premises and ask yourself "Which moves are available to me?"  Consider the following argument:

 1.  P →  (Q  ▼ S) premise        ∴N 2.  T →  P premise 3.  T premise 4.  ~Q ▼ ~T premise 5.   S   → (R ●  N) premise

Just glancing at these premises I see a step of Hypothetical Syllogism (lines 1 and 2), a step of Modus Ponens (2 and 3), a step of Disjunctive Syllogism (3 and 4, with DN on 3).  Each of these leads to a different overall strategy for constructing the proof.  Which is the best?  None, they are equally good.  How you see you way through a proof is more a matter of individual psychology than logic.  Sure, some strategies are shorter or more elegant, but those are unimportant to the logician.  I am sure that you have had the experience of riding in someone else's car and wondering "Why on earth is she going this way?"  Well, her way might be just as good as yours, or, for her it simply works better.  Constructing proof is very much like that.  Find rules and patterns that makes sense to you and that you are comfortable with, then apply them.  What follows is a list of strategy hints for constructing proofs.

Strategy hints for constructing proofs

1. Be sure that you have translated or copied the problem correctly. If you make a mistake, then you may have written down an invalid argument. If so, you'll never prove it valid!
2. Similarly, make sure the argument is valid. Don't make up problems at random except for adventure. If your problem is invalid, then (if you make no mistakes) your proof will trudge on inconclusively forever.
3. Know the rules of inference and replacement intimately. For this purpose, practice is much more valuable than memorization. You will only see a path from your given premises to your desired conclusion if you know how to walk.
4. If any of the rules still seem strange (illogical, unwarranted) to you, try to see why they are valid. You can prove them valid or you can work to make their validity familiar and intuitive. But until you get this far, they will be much harder to apply in practice.
5. Remember that the rules of inference apply to all statements that share their form, even if enormously complicated. For example, modus ponens applies to any conditional statement no matter how complex, provided it and its antecedent are both given. Recognize huge compounds as cases of your simpler rules. In large, complex compounds, look for the main connective to help you diagnose what rules might apply to it.
6. Think backwards. Ask yourself what would suffice to prove the conclusion; then ask what would suffice to prove that, and so on. Eventually you should reach one of your given premises, or get so close that you can see the bridge from where they are to where you are.
7. Remember that the different variables in the rules of inference might, in a special case, stand for the same proposition. For example, the rule of material material implication tells us that (p q) « (~p q). One case of this general truth is (p p) « (~p p), which can be very helpful.
8. Get simple. Derive the simplest propositions you can and use them to build up to a compound conclusion.
9. If a simple proposition occurs in the premises and not in the conclusion, drop it as soon as you can. Remember which rules (and combinations of rules) allow you to drop components of compounds.
10. If a simple proposition occurs in the conclusion and not in any or all the premises, add it to the appropriate proposition. Remember which rules (and combinations of rules) allow you to add components to compounds.
11. Learn how to use the rules to change connectives you don't want into connectives you do want.
12. Learn how to use the rules to change from a negated compound to an un-negated one. Take negation signs off the outside of compounds whenever you can; only then can you decompose them (pursuant to tip 8 above).
13. Learn useful "sub-routines" or clusters of rules. For some examples, see below.
14. Use the methods of conditional and indirect proof when appropriate. Try them whenever you get stuck if only for a change of scenery.
15. If you get stuck, check to see whether you have made any mistakes to that point. Check each step. Check your original translation or transcription of the problem.
16. If you are really stuck, make (valid) inferences at random. That is, follow the inference rules but have no particular goal. This is inelegant but perfectly valid. It will enlarge the set of "premises" from which you can draw inferences. At some point you might see a path from where you are to the conclusion. (Keep one eye on tips 8-10 as you go.)

Useful Sub-Routines

1. ANYTHING follows from a contradiction.

 A · ~A given A simplification ~A simplification A B addition; B is any statement we happen to need B disjunctive syllogism

2. Move from any B to A B

 B given B ~A addition ~A B commutation A → B material implication

3. Move from A(B · C) to AB

 A→(B · C) given ~A(B · C) material implication (~AB) · (~AC) distribution ~AB simplification A→B material implication

4. Move from (AB)C to AC

 (AB)→C given ~(AB)C material implication (~A · ~B)C DeMorgan's theorem C(~A · ~B) commutation (C~A) · (C~B) distribution C~A simplification ~AC commutation A→C material implication

5. Move from A ~A to ~A

 A → ~A given ~A ~A material implication ~A redundancy

6. Move from ~A A to A

 ~A → A given A A material implication A redundancy