1549901369-Elements_of_Real_Analysis__Denlinger_

A.l The Logic of Propositions 591

We can use truth-tables to verify (prove) that these are tautologies. For

example, to verify (c) we construct the following truth t able:

Table A .6

p Q PVQ P:::;, (P v Q)

T T T T

T F T T

F T T T

F F F T

Notice that the last column of this truth-table consists of all T's, indicating

that the compound proposition heading that column is a tautology. D

Definition A.1.16 Two compound propositions "P" and "Q"are logically

equivalent if and only if the assertion "P ¢:> Q" is a tautology; that is, P

and Q always have the same truth-value. To denote that P and Qare logically

equivalent we shall write

P:=Q.

Examples A.1.17 Some obvious logical equivalences:

(a) P =(PI\ P); P = (P VP);

(b) PI\ (QI\ R) =(PI\ Q) I\ R ;

(c) P V (Q V R) = (P V Q) V R. D

Examples A.1.18 Prove de Morgan's laws:

(a) ""'(PI\ Q) = ""'P V ""'Q;

(b) ""' ( p v Q) = ""' p (\ ""' Q.

Proof. We prove (a) using the following truth-table, and leave the proof
of (b) as Exercise 11 below.

Table A.7

p Q p (\ Q ""'(PI\ Q) ""'p ""'Q ""'Pv""'Q

T T T F F F F

T F F T F T T

F T F T T F T

F F F T T T T

t t

Observe that the fourth and seventh columns of Table A. 7 are identical.

That is, the propositions""' (Pl\ Q) and""' P V""' Q have the same truth-value,