return to main page

Additional Material





Telescoping implications, an indirect proof (adv)

For any logical statements p,q,r if p ==> q and q ==> r are true implications then p ==> r is a true implication.

Suppose p ==> q is true and q ==> r is true. It is desirable to show that p ==> r cannot be false. Suppose that it is false. Then p is true and r is false (the only way that the implication can be false). Since q ==> r is true, by definition of implication, it cannot happen that q is true and r is false. The only way is that q must be false. But since p ==> q is true, again by definition of implication, it cannot happen that p is true and q is false. This means that p must be false. But p was true by the assumption about p ==> r being false. Therefore p is both true and false, a logical impossibility.
Therefore, assuming p ==> r is false, leads to an impossibility. This means that the implication p ==> r must be true.



Evaluations of two expressions with parentheses

                 1   2    3        4              5                                       1   2    3          6                            7
                                   (2+3)       (1+4)                                                       (1+2)                     (6+3)
                 p   q   r      q or r    p and (q or r)                          p   q    r     p and q      (p and q) or r
                T   T   T        T             T                                       T   T   T         T                          T
                T   T   F        T             T                                       T   T   F         T                          T
                T   F   T        T             T                                       T   F   T         F                          T
                T   F   F        F             F                                       T   F   F          F                          F
                F   T   T        T             F                                       F   T   T         F                          T
                F   T   F        T             F                                       F   T   F         F                           F
                F   F   T        T             F                                       F   F   T         F                          T
                F   F   F        F             F                                       F   F   F         F                           F

The idea here is to evaluate pieces of the two expressions p and (q or r), (p and q) or r by its participating pieces. p, (q or r) are pieces of the first expression, (p and q), r are pieces of the second expression. The pieces in parentheses are evaluated in columns 4 and 6. The expressions (2+3) and (1+2) indicate what columns contain truth values that are used to determine the truth values in 4 and 6. Look at these as rows, not columns.



Equivalence of an implication and its contrapositive

The implication is   p ==> q.   Its contrapositive is   ~q ==> ~p.   They appear in columns 3 and 6 in the following truth table.

                 1    2           3            4      5               6                          7
                                (1+2)        (2)   (1)           (4+5)                  (3+6)
                 p   q      p ==>q       ~q   ~p      ~q ==> ~p       3,6 equivalent (have same truth value)
                 T   T          T           F     F                T                         T
                 T   F          F           T     F                F                         T
                 F   T          T           F     T                T                         T
                 F   F          T           T     T                T                         T