Page 49 - Discrete Mathematics and Its Applications

28 1 / The Foundations: Logic and Proofs
When using De Morgan’s
laws, remember to change
the logical connective ¬(p ∨ q) ≡¬p ∧¬q tells us that the negation of a disjunction is formed by taking the con-
after you negate.
TABLE 7 Logical Equivalences TABLE 8 Logical
Involving Conditional Statements. Equivalences Involving
Biconditional Statements.
p → q ≡¬p ∨ q
p ↔ q ≡ (p → q) ∧ (q → p)
p → q ≡¬q →¬p
p ↔ q ≡¬p ↔¬q
p ∨ q ≡¬p → q
p ↔ q ≡ (p ∧ q) ∨ (¬p ∧¬q)
p ∧ q ≡¬(p →¬q)
¬(p ↔ q) ≡ p ↔¬q
¬(p → q) ≡ p ∧¬q
(p → q) ∧ (p → r) ≡ p → (q ∧ r)
(p → r) ∧ (q → r) ≡ (p ∨ q) → r
(p → q) ∨ (p → r) ≡ p → (q ∨ r)
(p → r) ∨ (q → r) ≡ (p ∧ q) → r
false. We also display some useful equivalences for compound propositions involving condi-
tional statements and biconditional statements in Tables 7 and 8, respectively. The reader is
asked to verify the equivalences in Tables 6–8 in the exercises.
The associative law for disjunction shows that the expression p ∨ q ∨ r is well defined,
in the sense that it does not matter whether we first take the disjunction of p with q and then
the disjunction of p ∨ q with r, or if we first take the disjunction of q and r and then take the
disjunctionofp withq ∨ r. Similarly,theexpressionp ∧ q ∧ r iswelldefined. Byextendingthis
reasoning, it follows that p 1 ∨ p 2 ∨ ··· ∨ p n and p 1 ∧ p 2 ∧ ··· ∧ p n are well defined whenever
p 1 ,p 2 ,...,p n are propositions.
Furthermore, note that De Morgan’s laws extend to
¬(p 1 ∨ p 2 ∨ ··· ∨ p n ) ≡ (¬p 1 ∧¬p 2 ∧· · ·∧¬p n )
and
¬(p 1 ∧ p 2 ∧ ··· ∧ p n ) ≡ (¬p 1 ∨¬p 2 ∨· · ·∨¬p n ).
n n
We will sometimes use the notation j=1 p j for p 1 ∨ p 2 ∨ ··· ∨ p n and j=1 p j for
p 1 ∧ p 2 ∧ ··· ∧ p n . Using this notation, the extended version of De Morgan’s laws can be
n n n n
written concisely as ¬ j=1 p j ≡ j=1 ¬p j and ¬ j=1 p j ≡ j=1 ¬p j . (Methods for
proving these identities will be given in Section 5.1.)
Using De Morgan’s Laws
The two logical equivalences known as De Morgan’s laws are particularly important. They tell
us how to negate conjunctions and how to negate disjunctions. In particular, the equivalence
junction of the negations of the component propositions. Similarly, the equivalence ¬(p ∧ q) ≡
¬p ∨¬q tells us that the negation of a conjunction is formed by taking the disjunction of the
negations of the component propositions. Example 5 illustrates the use of De Morgan’s laws.