Bridge to Abstract Mathematics: Mathematical Proof and Structures

2.3 THEOREMS OF THE PROPOSITIONAL CALCULUS 65

EXAMPLE (^1) Find pairs of equivalent statement forms among p -+ q,
q -) p, *q -+ -p, and -p -+ -9.
Solution We can most efficiently deal with this problem by constructing a
single truth table, as illustrated in Figure 2.6. A comparison of columns
(5) through (8) shows that p -+ q and - q -+ - p are logically equivalent,
asareq -+pand -p+ --q,
DEFINITION 1
If p -+ q is a conditional, then the corresponding conditional --q -, --p
is called its contrapositive, q -+ p is called its converse, and -p + -q is
called its inverse.
Figure 2.6 Truth tables for the original, converse, inverse, and contrapositive of
a conditional p -+ q.
-P
F
F
T
ppP-pp "(I
F
T
F
T
P
The final outcome of Example 1 is that any conditional is equivalent
to its contrapositive, but not to its converse and inverse. The converse
and inverse of a given conditional, however, are equivalent to each other.
[Why? What is the relationship between q -+ p and -p 4 -q? See Ex-
ercise 4(b).] The theorem of the propositional calculus suggested by Exam-
ple 1 is: The statement form (p -, q) - (-9 -, -p) is a tautology. The fact
that p -+ q is not equivalent to its converse q -+ p means that the statement
form (p + q) - (q p) is not a tautology. This means that a statement of
the form p -+ q can be true, even when the corresponding statement q -+ p
is false. Can you give some examples from your mathematical experience of
this situation?
4
TT
TF
FT
FFT
In the next example we encounter two more important equivalences; the
statement form p t, q is equivalent to (p -+ q) A (q -, p) and the form
p -+ (q v r) is equivalent to (p A -- q) -+ r.
P-'4
T
F
T
T
EXAMPLE 2 Show that the following biconditionals are tautologies:
4-'P
T
T
F
T
"P-+"(I
T
T
F
T
-4-'-P
T
F
T
T