Page 52 - Discrete Mathematics and Its Applications

1.3 Propositional Equivalences 31

satisfiability problem. However, to show that a compound proposition is unsatisfiable, we need
to show that every assignment of truth values to its variables makes it false. Although we can
always use a truth table to determine whether a compound proposition is satisfiable, it is often
more efficient not to, as Example 9 demonstrates.

EXAMPLE 9 Determine whether each of the compound propositions (p ∨¬q) ∧ (q ∨¬r) ∧
(r ∨¬p), (p ∨ q ∨ r) ∧ (¬p ∨¬q ∨¬r), and (p ∨¬q) ∧ (q ∨¬r) ∧ (r ∨¬p) ∧
(p ∨ q ∨ r) ∧ (¬p ∨¬q ∨¬r) is satisfiable.

Solution: Instead of using truth table to solve this problem, we will reason about truth values.
Note that (p ∨¬q) ∧ (q ∨¬r) ∧ (r ∨¬p) is true when the three variable p, q, and r have
the same truth value (see Exercise 40 of Section 1.1). Hence, it is satisfiable as there is at
least one assignment of truth values for p, q, and r that makes it true. Similarly, note that
(p ∨ q ∨ r) ∧ (¬p ∨¬q ∨¬r) is true when at least one of p, q, and r is true and at least one
is false (see Exercise 41 of Section 1.1). Hence, (p ∨ q ∨ r) ∧ (¬p ∨¬q ∨¬r) is satisfiable,
as there is at least one assignment of truth values for p, q, and r that makes it true.
Finally, note that for (p ∨¬q) ∧ (q ∨¬r) ∧ (r ∨¬p) ∧ (p ∨ q ∨ r) ∧ (¬p ∨¬q ∨¬r)
to be true, (p ∨¬q) ∧ (q ∨¬r) ∧ (r ∨¬p) and (p ∨ q ∨ r) ∧ (¬p ∨¬q ∨¬r) must both
be true. For the first to be true, the three variables must have the same truth values, and
for the second to be true, at least one of three variables must be true and at least one must
be false. However, these conditions are contradictory. From these observations we conclude
that no assignment of truth values to p, q, and r makes (p ∨¬q) ∧ (q ∨¬r) ∧ (r ∨¬p) ∧
(p ∨ q ∨ r) ∧ (¬p ∨¬q ∨¬r) true. Hence, it is unsatisfiable. ▲

AUGUSTA ADA, COUNTESS OF LOVELACE (1815–1852) Augusta Ada was the only child from the
marriage of the famous poet Lord Byron and Lady Byron, Annabella Millbanke, who separated when Ada
was 1 month old, because of Lord Byron’s scandalous affair with his half sister. The Lord Byron had quite a
reputation, being described by one of his lovers as “mad, bad, and dangerous to know.” Lady Byron was noted for
her intellect and had a passion for mathematics; she was called by Lord Byron “The Princess of Parallelograms.”
Augusta was raised by her mother, who encouraged her intellectual talents especially in music and mathematics,
to counter what Lady Byron considered dangerous poetic tendencies. At this time, women were not allowed to
attend universities and could not join learned societies. Nevertheless,Augusta pursued her mathematical studies
independently and with mathematicians, including William Frend. She was also encouraged by another female
mathematician, Mary Somerville, and in 1834 at a dinner party hosted by Mary Somerville, she learned about Charles Babbage’s
ideas for a calculating machine, called the Analytic Engine. In 1838 Augusta Ada married Lord King, later elevated to Earl of
Lovelace. Together they had three children.
Augusta Ada continued her mathematical studies after her marriage. Charles Babbage had continued work on his Analytic
Engine and lectured on this in Europe. In 1842 Babbage asked Augusta Ada to translate an article in French describing Babbage’s
invention. When Babbage saw her translation, he suggested she add her own notes, and the resulting work was three times the
length of the original. The most complete accounts of the Analytic Engine are found in Augusta Ada’s notes. In her notes, she
compared the working of the Analytic Engine to that of the Jacquard loom, with Babbage’s punch cards analogous to the cards used
to create patterns on the loom. Furthermore, she recognized the promise of the machine as a general purpose computer much better
than Babbage did. She stated that the “engine is the material expression of any indefinite function of any degree of generality and
complexity.” Her notes on the Analytic Engine anticipate many future developments, including computer-generated music. Augusta
Ada published her writings under her initials A.A.L. concealing her identity as a woman as did many women at a time when women
were not considered to be the intellectual equals of men. After 1845 she and Babbage worked toward the development of a system
to predict horse races. Unfortunately, their system did not work well, leaving Augusta Ada heavily in debt at the time of her death
at an unfortunately young age from uterine cancer.
In 1953 Augusta Ada’s notes on the Analytic Engine were republished more than 100 years after they were written, and after
they had been long forgotten. In his work in the 1950s on the capacity of computers to think (and his famous Turing Test), Alan
Turing responded to Augusta Ada’s statement that “TheAnalytic Engine has no pretensions whatever to originate anything. It can do
whatever we know how to order it to perform.” This “dialogue” between Turing and Augusta Ada is still the subject of controversy.
Because of her fundamental contributions to computing, the programming language Ada is named in honor of the Countess of
Lovelace.