Page 48 - Discrete Mathematics and Its Applications

1.3 Propositional Equivalences 27

TABLE 5 A Demonstration That p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r) Are Logically
Equivalent.
p q r q ∧ r p ∨ (q ∧ r) p ∨ q p ∨ r (p ∨ q) ∧ (p ∨ r)

T T T T T T T T
T T F F T T T T
T F T F T T T T
T F F F T T T T
F T T T T T T T
F T F F F T F F
F F T F F F T F
F F F F F F F F

EXAMPLE 4 Show that p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r) are logically equivalent. This is the distributive
law of disjunction over conjunction.

Solution: We construct the truth table for these compound propositions in Table 5. Because
the truth values of p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r) agree, these compound propositions are
logically equivalent. ▲

The identities in Table 6
Table 6 contains some important equivalences. In these equivalences, T denotes the com-
are a special case of
Boolean algebra identities pound proposition that is always true and F denotes the compound proposition that is always
found in Table 5 of
Section 12.1. See Table 1
in Section 2.2 for TABLE 6 Logical Equivalences.
analogous set identities.
Equivalence Name
p ∧ T ≡ p Identity laws
p ∨ F ≡ p
p ∨ T ≡ T Domination laws
p ∧ F ≡ F
p ∨ p ≡ p Idempotent laws
p ∧ p ≡ p
¬(¬p) ≡ p Double negation law

p ∨ q ≡ q ∨ p Commutative laws
p ∧ q ≡ q ∧ p

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) Associative laws
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) Distributive laws
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

¬(p ∧ q) ≡¬p ∨¬q De Morgan’s laws
¬(p ∨ q) ≡¬p ∧¬q

p ∨ (p ∧ q) ≡ p Absorption laws
p ∧ (p ∨ q) ≡ p
p ∨¬p ≡ T Negation laws
p ∧¬p ≡ F