Hints for Doing Proofs
   
 

Though the Natural Deduction rules are natural, they are still syntactic. A computer could do a natural deduction proof by applying suitable rules without knowing about the 'meaning' of the logic connectives (eg. The Pandora Tutor in the Tutorial).

Once you have put the assumptions at the top of a proof and the conclusion at the bottom, what do you do next? You might be able to use some automatic steps. Introduction rules produce conclusions so usually they are used when filling in a proof from the bottom upwards; where elimination rules work on the data and so they are usually used when filling in a proof from the top downwards. In Pandora, there are two ways of applying a rule - Forwards and Backwards. If you know what you do next will make progresses to the proof, then you may apply the rules straight away (forwards) on the data. Otherwise, it is worth you trying out the rules backwards with the conclusion/goal.

There are many useful tactics which you will discover for yourself. The following is a subset of the tactics (that are used by the Pandora Tutor):

  • Work on the goal
    If you are sure that what you do next will make progresses to the proof, you may apply the rules on the data forwards straight away. If not, it might be a good idea to check the principle connective of the current goal. For example, if the current goal is:
    • A B: then try to use Arrow Introduction(backwards). After doing that, you will have B as your new goal and what you do next is to prove B from A and/or other existing data (formulae that are in scope of B).
    • ¬P: then try to use Not Introduction(backwards). Then what you do next is to find a contradiction (that is, to prove Bottom/Falsity) from the existing data by assuming P.
    • a conjunction or disjunction: then use And Introduction(backwards) or Or Introduction(backwards). However, while using Or Introduction(backwards), you have to decide which subformula of the disjunction should become the new goal. Oftenly only one side of the disjunction is provable.
    • A B: then try to use IFF Introduction(backwards) or IFF Introduction-derived(backwards).
    • with quantifier or : if you cannot derive them by using the rules forwards on the existing data, then you may have to use the corresponding introduction rule backwards on the goal. Using There Exists Introduction(backwards) sometimes is quite hard because you have to select a suitable term for the variable in the goal.
  • Work on the data
    Sometimes, if you have no idea what to do with the goal, you might be able to temporarily ignore the goal and work on the data only (using rules forwards), hoping you can derive something new and useful to the proof. For example:
    • And Elimination(forwards): If there is an conjunction in your proof, then you may use And Elimination to extract its sub-formulae. Maybe they can help in proving the goal.
    • Arrow Elimination(forwards): If there exist an implication A B and a formula A in your proof, then you may use Arrow Elimination(forwards) with them to derive D, which might be useful later on.
    • Not Elimination(forwards)/Bottom Introduction(forwards) with Bottom Elimination(forwards): If there exist P and ~P in your proof, the best next-step will be using Not Elimination(forwards) or Bottom Introduction(forwards) (in fact, they are the same) to derive Bottom/Falsity, and then use Bottom Elimination(forwards) to derive the goal.
  • Work on both the data and the goal
    These tactics require you to check both the data and the current goal. Sometimes if you find the current goal is hard to prove, you might be able to use some rules backwards with the data and the current goal to get a new goal, which might be easier to prove. For example:
    • as 'if': If there is an implication D C and the conclusion is C then try to use Arrow Elimination(backwards) to derive D as a new goal, and then try to show D. D C can be read as C if D, from which the tactic gets its name.
    • Make use of negated-formula: If the conclusion is Bottom/Falsity and there is a negated-formula say ¬P available, then you could use Not Elimination(backwards) to change the current goal from Bottom/Falsity to P.
    • Combined V rules: The Or Introduction and Or Elimination often go together. If the goal is a disjunction, say C V D, and there is also a disjunction, say A V B in scope of the goal, you may first use Or Elimination(backwards) and then use Or Introduction. The Or Elimination rule will force two subproofs, one using A and one using B, and perhaps in one you can prove C and in the other D. In both cases the Or Introduction rule will yield C V D, as you required..
    • Bottom Elimination(backwards) anywhere: If you cannot see what to do next perhaps you can use Bottom Elimination(backwards) to derive Bottom/Falsity as your new goal. This often happens in some branches of a Or Elimination box.
  • Other tactics
    There are some other rules that you may want to try if all else fails,
    • Law of Excluded Middle: If you are really stuck, you may introduce a theorem of the form P V ¬P and immediately use Or Elimination. However, to select a suitable P is sometimes quite hard.
    • PC: Instead of trying the Law of Excluded Middle, you may also want to try the PC(Proof by Contradiction) rule. However, if all else does not fail then do not use PC, as the negated assumptions it introduces often make the proof more difficult to read.

    Practically, Lemmas are used in some large scale proofs. Sometimes, a large proof can best be tackled by breaking it down into smaller steps. For example, if your problem is to show Data |- Conclusion then maybe you could show Data |- Lemma and then make use of the Lemma to show Data + Lemma |- Conclusion.


references:
  • K.Broda, S.Eisenbach, H.Khoshnevisan and S.Vickers, Reasoned Programming, Prentice Hall, 1994
  • Ian Hodkinson, C140 Logic Lecture Notes, available at http://www.doc.ic.ac.uk/~imh/teaching/140_logic/logic.html