Logic-Basic Proof methods I

A few of the basic tautologies we shall refer to are

P v ~ P    Excluded middle
(P => Q) <=> (~Q => ~P)   Contrapositive
P v (Q v R) <=> (P v Q) v R   Associative
P ^ (Q ^ R <=> (P ^ Q) ^ R    Associative
P ^ (Q v R) <=> (P ^ Q) v (P ^ R)   Distributive
P v (Q ^ R) <=> (P v Q) ^ (P v R)   Distributive
(P <=> Q) <=> (P => Q) ^ (Q => P)   Biconditional
~(P => Q) <=> P ^ ~Q   Denial of implication
~(P ^ Q)<=> ~P v ~Q    De morgan's law
~(P v Q) <=> ~P ^ ~Q   De morgan's law
P <=> (~P => (Q ^ ~ Q))  Contradiction
[(P => Q) ^ (Q => R)] => (P => R)   Transitivity
[P ^ (P => Q) => Q    Modus Poenus

Direct Proof of P => Q

Assume P.
     .
     .
     .
Therefore, Q.
Thus P => Q

QED

Example. Suppose a, b, and c are integers. Prove that if a divides b and b divides c, then a divides c.

Proof. [For a direct proof, we assume the antecedent, which is "a divides b and b divides c." Our goal is to derive the consequent, "a divides c," as our last step.] Suppose a, b, and c are integers, and that a divides b and b divides c. [We now rewrite these assumptions by using the definition of "divides," so that we have some equation to work with.] Then b = ak for some integer k, and c = bj for some integer j. [To show that a divides c, we have to write c as a multiple of a.] Therefore, c = bj = (ak)j = a(kj), so a divides b and b divides c, a divides c.

QED