1549901369-Elements_of_Real_Analysis__Denlinger_

592 Appendix A • Logic and Proofs

regardless of the truth-values of P and Q. By Definition A.l.16, this means

that these compound propositions are logically equivalent. D

NOTE: de Morgan's laws illustrate a very important principle: The nega-

tion of an "and" is not another "and;" rather, it is an "or." Similarly, the

negation of an "or" is not another "or;" it is an "and." This should be pon-

dered and remembered, so that it is not a stumbling block for you.

Example A.1. 19 Equivalent form of:=;.: (P =? Q) = ""P V Q.

P r o of. We use the following truth-table:

Table A .8

p Q p =? Q rv p rv P V Q

T T T F T

T F F F F

F T T T T

F F T T T

I I

Since columns three and five are identical, we have proved that P =? Q and
""P V Q are equivalent. D

Example A.1. 20 E q uivalence o f contraposit ive: P =? Q = ""Q =? ""P.

Proof. As in the previous examples, we use a truth-table:

Table A.9

p Q p =? Q rv Q rv p rv Q =?rv p

T T T F F T

T F F T F F

F T T F T T

F F T T T T

t t

The proof is completed by observing that columns three and six are identical.D