Page 47 - Discrete Mathematics and Its Applications

26 1 / The Foundations: Logic and Proofs

TABLE 2 De
Morgan’s Laws.
¬(p ∧ q) ≡¬p ∨¬q
¬(p ∨ q) ≡¬p ∧¬q

giving their truth values agree. Example 2 illustrates this method to establish an extremely
important and useful logical equivalence, namely, that of ¬(p ∨ q) with ¬p ∧¬q. This logical
equivalence is one of the two De Morgan laws, shown in Table 2, named after the English
mathematician Augustus De Morgan, of the mid-nineteenth century.

EXAMPLE 2 Show that ¬(p ∨ q) and ¬p ∧¬q are logically equivalent.

Solution: The truth tables for these compound propositions are displayed in Table 3. Because
the truth values of the compound propositions ¬(p ∨ q) and ¬p ∧¬q agree for all possible
combinationsofthetruthvaluesofp andq,itfollowsthat¬(p ∨ q) ↔ (¬p ∧¬q)isatautology
and that these compound propositions are logically equivalent. ▲

TABLE 3 Truth Tables for ¬(p ∨ q) and ¬p ∧¬q.
p q p ∨ q ¬(p ∨ q) ¬p ¬q ¬p ∧¬q
T T T F F F F
T F T F F T F
F T T F T F F
F F F T T T T

EXAMPLE 3 Show that p → q and ¬p ∨ q are logically equivalent.

Solution: We construct the truth table for these compound propositions in Table 4. Because the
truth values of ¬p ∨ q and p → q agree, they are logically equivalent. ▲

TABLE 4 Truth Tables for ¬p ∨ q and
p → q.

p q ¬p ¬p ∨ q p → q
T T F T T
T F F F F
F T T T T
F F T T T

We will now establish a logical equivalence of two compound propositions involving three
different propositional variables p, q, and r. To use a truth table to establish such a logical
equivalence, we need eight rows, one for each possible combination of truth values of these
three variables. We symbolically represent these combinations by listing the truth values of p,
q, and r, respectively. These eight combinations of truth values are TTT, TTF, TFT, TFF, FTT,
FTF, FFT, and FFF; we use this order when we display the rows of the truth table. Note that we
need to double the number of rows in the truth tables we use to show that compound propositions
are equivalent for each additional propositional variable, so that 16 rows are needed to establish
the logical equivalence of two compound propositions involving four propositional variables,
n
and so on. In general, 2 rows are required if a compound proposition involves n propositional
variables.