586 Appendix A • Logic and Proofs
Definition A.1.6 The implication "If P, then Q" (or "P implies Q" ) is
symbolized P =? Q and is defined by the truth-table:
Table A.3p Q p ::::} Q
T T T
T F F
F T T
F F TIn the compound proposition P =? Q, the proposition P is called the hy-
pothesis and the proposition Q is called the conclusion. Notice that an im-
plication is false only when its hypothesis is true and its conclusion is false. An
implication with a false hypothesis is true regardless of the conclusion.
Examples A.1. 7 Some implications:
(a) If you can't come tonight, then we'll cancel the party.
(b) If you hit me, I'll scream.
(c) "A~ B";^1 that is , "A is a subset of B." This statement is intended to
mean "any x belonging to A must belong to B." That is, if x EA, then x EB.
In symbols, x E A =? x E B.
(d) Because of (c), the empty set^1 0 is a subset of every set B. That is,
0 ~ B , for all sets B. This is because x E 0 =? x E B is always true, since
x E 0 is always false.
CAUTION: An implication is one-directional, in the sense that Q =?Pis
not the same as P =? Q. For example,
"If x > 2, then x > 1"
is not the same statement as
"If x > 1, then x > 2." D- See Appendix B .1, where the notions of sets, subsets, and the empty s et are discussed.