Bridge to Abstract Mathematics: Mathematical Proof and Structures

68 LOGIC, PART I: THE PROPOSITIONAL CALCULUS Chapter 2

conjunction involves disjunction (and the negation of the original com-

ponent statements), and vice versa. Like the two analogous theorems of

set theory [Fact 6, (34)(35), Article 1.41, these are known as De Morgan's

laws. To get a feeling for (e), ask yourself what must happen (i.e., What

statement is true?) in order for the promise "if you pass this test, you will

pass the course" to be a lie, that is, a false statement. As for (f), we can

convince ourselves of its reasonableness by combining the first tautology

in Example 2 with parts (c) and (e) of Theorem 1. Here is an alternative

approach to understanding (f). Suppose your teacher had promised "you

will pass the course if and only if you pass this test." What possibilities

could have occurred if you conclude, after the fact, that the instructor did

not keep the promise?

EXAMPLE 3 Write a positive statement equivalent to the negation of "If

rainfall is light, then the crop is disappointing and grain prices rise."

Solution This statement has the form p + (q A r). By Theorem l(e), its

negation has the form p A [- (q A r)] which, by (c) of Theorem 1, is equiv-

alent to p A ( -- q v - r). This statement form may be interpreted in this

example as "rainfall is light and (yet) either the crop is not disappointing

or grain prices are not rising." 0

Selected equivalences of the propositional calculus. The proof of each part

of the following theorem consists of a truth table. Since the process of con-

structing truth tables has been demonstrated earlier and is laborious, there

is little to be gained from proving all parts of this theorem. A compromise

is suggested in Exercise 2(a).

THEOREM 1

The following statement forms, each having the biconditional as main connec-

tive, are all tautologies (and thus equivalences):

(reflexive property of

equivalence)

(negation of negation)

(negation of conjunction;

De Morgan's law)

(negation of disjunction;

De Morgan's law)

(negation of conditional)

(negation of biconditional)

(commutativity of disjunction)

(commutativity of conjunction)

(associativity of disjunction)

(associativity of conjunction)

(disjunction distributes over

conjunction)