Page 50 - Discrete Mathematics and Its Applications

1.3 Propositional Equivalences 29

EXAMPLE 5 Use De Morgan’s laws to express the negations of “Miguel has a cellphone and he has a laptop
computer” and “Heather will go to the concert or Steve will go to the concert.”

Solution: Let p be “Miguel has a cellphone” and q be “Miguel has a laptop computer.” Then
“Miguel has a cellphone and he has a laptop computer” can be represented by p ∧ q. By the
first of De Morgan’s laws, ¬(p ∧ q) is equivalent to ¬p ∨¬q. Consequently, we can express
the negation of our original statement as “Miguel does not have a cellphone or he does not have
a laptop computer.”
Let r be “Heather will go to the concert” and s be “Steve will go to the concert.” Then
“Heather will go to the concert or Steve will go to the concert” can be represented by r ∨ s.
By the second of De Morgan’s laws, ¬(r ∨ s) is equivalent to ¬r ∧¬s. Consequently, we can
express the negation of our original statement as “Heather will not go to the concert and Steve
will not go to the concert.” ▲

Constructing New Logical Equivalences

The logical equivalences in Table 6, as well as any others that have been established (such as
those shown in Tables 7 and 8), can be used to construct additional logical equivalences. The
reason for this is that a proposition in a compound proposition can be replaced by a compound
proposition that is logically equivalent to it without changing the truth value of the original
compound proposition. This technique is illustrated in Examples 6–8, where we also use the
fact that if p and q are logically equivalent and q and r are logically equivalent, then p and r
are logically equivalent (see Exercise 56).

EXAMPLE 6 Show that ¬(p → q) and p ∧¬q are logically equivalent.

Solution: We could use a truth table to show that these compound propositions are equivalent
(similar to what we did in Example 4). Indeed, it would not be hard to do so. However, we want
to illustrate how to use logical identities that we already know to establish new logical identities,
somethingthatisofpracticalimportanceforestablishingequivalencesofcompoundpropositions
with a large number of variables. So, we will establish this equivalence by developing a series of

AUGUSTUS DE MORGAN (1806–1871) Augustus De Morgan was born in India, where his father was a
colonel in the Indian army. De Morgan’s family moved to England when he was 7 months old. He attended
private schools, where in his early teens he developed a strong interest in mathematics. De Morgan studied
at Trinity College, Cambridge, graduating in 1827. Although he considered medicine or law, he decided on
mathematics for his career. He won a position at University College, London, in 1828, but resigned after the
college dismissed a fellow professor without giving reasons. However, he resumed this position in 1836 when
his successor died, remaining until 1866.
DeMorganwasanotedteacherwhostressedprinciplesovertechniques.Hisstudentsincludedmanyfamous
mathematicians, including Augusta Ada, Countess of Lovelace, who was Charles Babbage’s collaborator in his
work on computing machines (see page 31 for biographical notes on Augusta Ada). (De Morgan cautioned the countess against
studying too much mathematics, because it might interfere with her childbearing abilities!)
De Morgan was an extremely prolific writer, publishing more than 1000 articles in more than 15 periodicals. De Morgan also
wrote textbooks on many subjects, including logic, probability, calculus, and algebra. In 1838 he presented what was perhaps the first
clear explanation of an important proof technique known as mathematical induction (discussed in Section 5.1 of this text), a term
he coined. In the 1840s De Morgan made fundamental contributions to the development of symbolic logic. He invented notations
that helped him prove propositional equivalences, such as the laws that are named after him. In 1842 De Morgan presented what
is considered to be the first precise definition of a limit and developed new tests for convergence of infinite series. De Morgan was
also interested in the history of mathematics and wrote biographies of Newton and Halley.
In 1837 De Morgan married Sophia Frend, who wrote his biography in 1882. De Morgan’s research, writing, and teaching left
little time for his family or social life. Nevertheless, he was noted for his kindness, humor, and wide range of knowledge.