Page 55 - Discrete Mathematics and Its Applications

34 1 / The Foundations: Logic and Proofs

Solving Satisfiability Problems

A truth table can be used to determine whether a compound proposition is satisfiable, or equiv-
alently, whether its negation is a tautology (see Exercise 60). This can be done by hand for
a compound proposition with a small number of variables, but when the number of variables
grows, this becomes impractical. For instance, there are 2 20 = 1,048,576 rows in the truth ta-
ble for a compound proposition with 20 variables. Clearly, you need a computer to help you
determine, in this way, whether a compound proposition in 20 variables is satisfiable.
When many applications are modeled, questions concerning the satisfiability of compound
propositions with hundreds, thousands, or millions of variables arise. Note, for example, that
when there are 1000 variables, checking every one of the 2 1000 (a number with more than 300
decimal digits) possible combinations of truth values of the variables in a compound proposition
cannot be done by a computer in even trillions of years. No procedure is known that a com-
puter can follow to determine in a reasonable amount of time whether an arbitrary compound
proposition in such a large number of variables is satisfiable. However, progress has been made
developing methods for solving the satisfiability problem for the particular types of compound
propositions that arise in practical applications, such as for the solution of Sudoku puzzles.
Many computer programs have been developed for solving satisfiability problems which have
practical use. In our discussion of the subject of algorithms in Chapter 3, we will discuss this
question further. In particular, we will explain the important role the propositional satisfiability
problem plays in the study of the complexity of algorithms.
Exercises

1. Use truth tables to verify these equivalences. b) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r).
a) p ∧ T ≡ p b) p ∨ F ≡ p 5. Use a truth table to verify the distributive law
c) p ∧ F ≡ F d) p ∨ T ≡ T p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r).
e) p ∨ p ≡ p f) p ∧ p ≡ p 6. Use a truth table to verify the first De Morgan law
2. Show that ¬(¬p) and p are logically equivalent. ¬(p ∧ q) ≡¬p ∨¬q.
3. Use truth tables to verify the commutative laws 7. Use De Morgan’s laws to find the negation of each of the
a) p ∨ q ≡ q ∨ p. b) p ∧ q ≡ q ∧ p. following statements.
4. Use truth tables to verify the associative laws a) Jan is rich and happy.
a) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r). b) Carlos will bicycle or run tomorrow.

HENRY MAURICE SHEFFER (1883–1964) Henry Maurice Sheffer, born to Jewish parents in the western
Ukraine, emigrated to the United States in 1892 with his parents and six siblings. He studied at the Boston Latin
School before entering Harvard, where he completed his undergraduate degree in 1905, his master’s in 1907,
and his Ph.D. in philosophy in 1908. After holding a postdoctoral position at Harvard, Henry traveled to Europe
on a fellowship. Upon returning to the United States, he became an academic nomad, spending one year each
at the University of Washington, Cornell, the University of Minnesota, the University of Missouri, and City
College in New York. In 1916 he returned to Harvard as a faculty member in the philosophy department. He
remained at Harvard until his retirement in 1952.
Sheffer introduced what is now known as the Sheffer stroke in 1913; it became well known only after its use
in the 1925 edition of Whitehead and Russell’s Principia Mathematica. In this same edition Russell wrote that Sheffer had invented
a powerful method that could be used to simplify the Principia. Because of this comment, Sheffer was something of a mystery man
to logicians, especially because Sheffer, who published little in his career, never published the details of this method, only describing
it in mimeographed notes and in a brief published abstract.
Sheffer was a dedicated teacher of mathematical logic. He liked his classes to be small and did not like auditors. When strangers
appeared in his classroom, Sheffer would order them to leave, even his colleagues or distinguished guests visiting Harvard. Sheffer
was barely five feet tall; he was noted for his wit and vigor, as well as for his nervousness and irritability. Although widely liked, he
was quite lonely. He is noted for a quip he spoke at his retirement: “Old professors never die, they just become emeriti.” Sheffer is
also credited with coining the term “Boolean algebra” (the subject of Chapter 12 of this text). Sheffer was briefly married and lived
most of his later life in small rooms at a hotel packed with his logic books and vast files of slips of paper he used to jot down his
ideas. Unfortunately, Sheffer suffered from severe depression during the last two decades of his life.