Proof techniques presented in the first week:

Direct proof (proving A => B):

    If under the assumption that A, you can prove B,
    then you can conclude that A => B.  ("the deduction theorem")

    Logical justification: if A is false, A=>B is true (see truth table for
    '=>'); if A is true, then A=>B is equivalent to B.


Indirect proof (proving A => B):

    If under the assumption that ~B, you can prove ~A,
    then you can conclude that A => B.

    Logical justification:
    ~B => ~A is equivalent to  A => B ("the contrapositive")


Proof by contradiction:

    If under the assumption that ~A, you can show a contradiction,
    then you can conclude that A.

    Equivalently:
    If under the assumption that A, you can show a contradiction,
    then you can conclude that ~A.

    Logical justification: ~A => false  is equivalent to  A
    or:  A=>false  is equivalent to ~A


Proof by cases (proving A or B => C):

    If you know that A => C
    and you know that B => C
    then you can conclude that (A or B) => C.

    In particular,
    If you know that A => C
    and you know that ~A => C,
    then you can conclude that C.

    Logical justification:
    (A or B) => C  is equivalent to  ((A => C) and (B => C))
    and (A => C) and (~A => C)  is equivalent to  (A or ~A) => C
    which is equivalent to  C


Proof of biconditional (proving A<=>B):

    If you know that A => B
    and you know that B => A
    then you can conclude that A <=> B.

    Alternate version:
    If you know that A => B
    and you know that ~A => ~B,
    then you can conclude that A <=> B.

    Logical justification: A <=> B  is equivalent to  (A => B) and (B => A)
    and ~A => ~B  is equivalent to  B => A


Proof of \thereexists:

    If k is a member of S,   [S is a set]
    and you know that P(k),   [P is a predicate]
    then you can conclude that thereexists i in S, P(i)

Proof of \forall:

    If, given an _arbitrary_ value of i in S, you can prove P(i),
    then you can conclude that forall i in S, P(i).


More proof techniques later.  Those are the ones we're using for now (almost
always implicitly).

(Not discussed in class:
Here are some basic rules of inference not included above, which in many
cases you probably use without even realizing you're doing it:

Specialization:
    If you know (A and B),
    then you can conclude that A.

Generalization:
    If you know that A,
    then you can conclude that (A or B).

Conjunction:
    If you know A,
    and you know B,
    then you can conclude that (A and B).

Modus ponens:
    If you know that A=>B,
    and you know that A,
    then you can conclude that B.

Modus tollens:
    If you know that A=>B,
    and you know that ~B,
    then you can conclude that ~A.

Transitivity:
    If you know that A=>B,
    and you know that B=>C,
    then you can conclude that A=>C.

Disjunctive syllogism:
    If you know that (A or B)
    and you know that ~A
    then you can conclude that B.

More indirect proof laws:
1:
    If you know that ~A => false,
    then you can conclude that A.
2:
    If you know that ~A => A,
    then you can conclude that A.

)