From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU  Mon Feb 18 20:21:05 2008

========================================================================
SOME STRATEGIES FOR PROVING THEOREMS (NOT A COMPLETE LIST!!)
========================================================================

Meta-strategies (i.e., strategies for using the strategies):

    1. Determine the logical form of the theorem to be proved.
       Then use an appropriate strategy.

    2. If more than one strategy is applicable,
       then try each of them until you find one that works.

========================================================================

                                        Strategy
If the logical form is:                 Then try to show:

------------------------------------------------------------------------
P(x), where P(x) =def D(x)              D(x)
------------------------------------------------------------------------
-P(x), where P(x) is a compound         Q(x), where Q(x) equiv P(x),
proposition                             but the "-" has been moved
                                        to the right by DeMorgan
------------------------------------------------------------------------
P                                       Indirect Proof:
                                          Assume (i.e., suppose;
                                          i.e., make believe) that -P
                                          & try to find R such that
                                            (R ^ -R)    
------------------------------------------------------------------------
ExP(x)                                  Constructive Proof:
                                          Find c such that P(c)

                                        Non-constructive Proof:
                                          Proof by Contradiction:
                                            Assume -ExP(x)
                                            & try to find R such that
                                              (R ^ -R)    
------------------------------------------------------------------------
-AxP(x)                                 Find a counterexample;
                                        i.e., try to show Ex-P(x)
------------------------------------------------------------------------
(P -> Q), where P is a contradiction    "vacuous" proof:
                                        (P -> Q) must be T!
------------------------------------------------------------------------
(P -> Q), where Q is a tautology        "trivial" proof:
                                        (P -> Q) must be T!
------------------------------------------------------------------------
(P -> Q)                                Direct Proof:
                                          Assume P
                                          & then try to show Q

                                          Hint:  If P =def D(x)
                                                 then suppose D(x)
                                                 & try to show Q
------------------------------------------------------------------------
(P -> Q)                                Indirect Proofs:

                                          Proof by Contraposition:
                                            Try to show (-Q -> -P)
                                            (by using one of the other 
                                            strategies for "->")

                                          Proof by Contradiction:
                                            Assume P
                                            Assume -Q
                                            & try to find R such that
                                              (R ^ -R)
------------------------------------------------------------------------
(P -> Q),                                 Proof by Cases:
where P equiv (P1 v P2 v ... v Pn)          Show (P1 -> Q)
i.e., (P1 v P2 v ... v Pn) -> Q             & show (P2 -> Q)    
                                            ...
                                            & show (Pn -> Q)
                                            (by using any of the above
                                            strategies for "->")
------------------------------------------------------------------------
Ax[P(x) -> Q(x)]                          P(c) -> Q(c), for arbitrary c
                                          (by using one of the strategies
                                          for "->"; then apply UG)
------------------------------------------------------------------------
(P <-> Q)                                 Show (P -> Q)
                                          & show (Q -> P)
                                          (by using any of the above 
                                          strategies for "->")
------------------------------------------------------------------------
(P1 <-> P2 <-> ... <-> Pn)                Show (P1 -> P2)
                                          & show (P2 -> P3)
                                          ...
                                          & show (Pn -> P1)
                                          (by using any of the above
                                          strategies for "->")
------------------------------------------------------------------------