Logic and Proofs: Foundations (PDF)

34 1 / The Foundations: Logic and Proofs FIGURE 1 otherwise. Note that squares (i, j) and (i′ , j′ ) are on the same diagonal if either i + i′ = j + j′ or i − i′ = j − j′. In the chessboard in Figure 1, p(6, 2) and p(2, 1...

34 1 / The Foundations: Logic and Proofs FIGURE 1 otherwise. Note that squares (i, j) and (i′ , j′ ) are on the same diagonal if either i + i′ = j + j′ or i − i′ = j − j′. In the chessboard in Figure 1, p(6, 2) and p(2, 1) are true, while p(3, 4) and p(5, 4) are false. For no two of the n queens to be in the same row, there must be one queen in each row. We can show that there is one queen in each row by verifying that every row ⋁contains at least one n queen and that every row contains at most one queen. We first note that j=1 p(i, j) asserts that row i contains at least one queen, and ⋀ n ⋁ n Q1 = p(i, j) i=1 j=1 asserts that every row contains at least one queen. For every row to include at most one queen, it must be the case that p(i, j) and p(k, j) are not both true for integers j and k with 1 ≤ j < k ≤ n. Observe that ¬p(i, j) ∨ ¬p(i, k) asserts that at least one of ¬p(i, j) and ¬p(i, k) is true, which means that at least one of p(i, j) and p(i, k) is false. So, to check that there is at most one queen in each row, we assert ⋀ ⋀ ⋀ n n−1 n Q2 = (¬p(i, j) ∨ ¬p(k, j)). i=1 j=1 k=j+1 To assert that no column contains more than one queen, we assert that ⋀ ⋀ ⋀ n n−1 n Q3 = (¬p(i, j) ∨ ¬p(k, j)). j=1 i=1 k=i+1 (This assertion, together with the previous assertion that every row contains a queen, implies that every column contains a queen.) To assert that no diagonal contains two queens, we assert ⋀ ⋀ ⋀ n n−1 min(i−1,n−j) Q4 = (¬p(i, j) ∨ ¬p(i − k, k + j)) i=2 j=1 k=1 and ⋀ ⋀ ⋀ n−1 n−1 min(n−i,n−j) Q5 = (¬p(i, j) ∨ ¬p(i + k, j + k)). i=1 j=1 k=1  1.3 Propositional Equivalences 35 The innermost conjunction in Q4 and in Q5 for a pair (i, j) runs through the positions on a diagonal that begin at (i, j) and runs rightward along this diagonal. The upper limits on these innermost conjunctions identify the last cell in the board on each diagonal. Putting all this together, we find that the solutions of the n-queens problem are given by the assignments of truth values to the variables p(i, j), i = 1, 2, … , n and j = 1, 2, … , n that make Q = Q1 ∧ Q2 ∧ Q3 ∧ Q4 ∧ Q5 true. Using this and other approaches, the number of ways n queens can be placed on a chessboard so that no queen can attack another has been computed for n ≤ 27. When n = 8 there are 92 such placements, while for n = 16 this number grows to 14,772,512. (See the OEIS discussed in Section 2.4 for details.) ◂ EXAMPLE 11 Sudoku Sudoku puzzles are constructed using a 9 × 9 grid made up of nine 3 × 3 subgrids, known as blocks, as shown in Figure 2. For each puzzle, some of the 81 cells, called givens, are assigned one of the numbers 1, 2, … , 9, and the other cells are blank. The puzzle is solved by assigning a number to each blank cell so that every row, every column, and every one of the nine 3 × 3 blocks contains each of the nine possible numbers. Note that instead of using a 9 × 9 grid, Sudoku puzzles can be based on n2 × n2 grids, for any positive integer n, with the n2 × n2 Links grid made up of n2 n × n subgrids. The popularity of Sudoku dates back to the 1980s when it was introduced in Japan. It took 20 years for Sudoku to spread to rest of the world, but by 2005, Sudoku puzzles were a worldwide craze. The name Sudoku is short for the Japanese suuji wa dokushin ni kagiru, which means “the digits must remain single.” The modern game of Sudoku was apparently designed in the late 1970s by an American puzzle designer. The basic ideas of Sudoku date back even further; puzzles printed in French newspapers in the 1890s were quite similar, but not identical, to modern Sudoku. Sudoku puzzles designed for entertainment have two additional important properties. First, they have exactly one solution. Second, they can be solved using reasoning alone, that is, without resorting to searching all possible assignments of numbers to the cells. As a Sudoku puzzle is solved, entries in blank cells are successively determined by already known values. For instance, in the grid in Figure 2, the number 4 must appear in exactly one cell in the second row. How can we determine in which of the seven blank cells it must appear? First, we observe that 4 cannot appear in one of the first three cells or in one of the last three cells of this row, because it already appears in another cell in the block each of these cells is in. We can also see that 4 2 9 4 5 1 4 4 2 6 7 5 7 3 5 1 9 6 FIGURE 2 A 9 × 9 Sudoku puzzle. 36 1 / The Foundations: Logic and Proofs cannot appear in the fifth cell in this row, as it already appears in the fifth column in the fourth row. This means that 4 must appear in the sixth cell of the second row. Many strategies based on logic and mathematics have been devised for solving Sudoku puzzles (see [Da10], for example). Here, we discuss one of the ways that have been devel- oped for solving Sudoku puzzles with the aid of a computer, which depends on modeling the puzzle as a propositional satisfiability problem. Using the model we describe, particular Sudoku puzzles can be solved using software developed to solve satisfiability problems. Cur- rently, Sudoku puzzles can be solved in less than 10 milliseconds this way. It should be noted that there are many other approaches for solving Sudoku puzzles via computers using other techniques. To encode a Sudoku puzzle, let p(i, j, n) denote the proposition that is true when the number n is in the cell in the ith row and jth column. There are 9 × 9 × 9 = 729 such propositions, as i, j, and n all range from 1 to 9. For example, for the puzzle in Figure 2, the number 6 is given as the value in the fifth row and first column. Hence, we see that p(5, 1, 6) is true, but p(5, j, 6) is false for j = 2, 3, … , 9. Given a particular Sudoku puzzle, we begin by encoding each of the given values. Then, we construct compound propositions that assert that every row contains every number, every column contains every number, every 3 × 3 block contains every number, and each cell contains no more than one number. It follows, as the reader should verify, that the Sudoku puzzle is solved by finding an assignment of truth values to the 729 propositions p(i, j, n) with i, j, and n each ranging from 1 to 9 that makes the conjunction of all these compound propositions true. After listing these assertions, we will explain how to construct the assertion that every row contains every integer from 1 to 9. We will leave the construction of the other assertions that every column contains every number and each of the nine 3 × 3 blocks contains every number to the exercises. ▶ For each cell with a given value, we assert p(i, j, n) when the cell in row i and column j has the given value n. ▶ We assert that every row contains every number: ⋀ 9 ⋀ 9 ⋁ 9 p(i, j, n) i=1 n=1 j=1 ▶ We assert that every column contains every number: ⋀ 9 ⋀ 9 ⋁ 9 p(i, j, n) j=1 n=1 i=1 ▶ We assert that each of the nine 3 × 3 blocks contains every number: It is tricky setting up the two inner indices so that ⋀ 2 ⋀ 2 ⋀ 9 ⋁ 3 ⋁ 3 all nine cells in each p(3r + i, 3s + j, n) square block are r=0 s=0 n=1 i=1 j=1 examined. ▶ To assert that no cell contains more than one number, we take the conjunction over all values of n, n′ , i, and j, where each variable ranges from 1 to 9 and n ≠ n′ of p(i, j, n) → ¬p(i, j, n′ ). We now explain how to construct the assertion that every row contains every number. ⋁9 First, to assert that row i contains the number n, we form j=1 p(i, j, n). To assert that row i contains all n numbers, we form the conjunction of these disjunctions over all nine ⋀ ⋁ possible values of n, giving us 9n=1 9j=1 p(i, j, n). Finally, to assert that every row contains  1.3 Propositional Equivalences 37 ⋀9 ⋁9 every number, we take the conjunction of n=1 j=1 p(i, j, n) over all nine rows. This gives ⋀ ⋀ ⋁ us 9i=1 9n=1 9j=1 p(i, j, n). (Exercises 71 and 72 ask for explanations of the assertions that every column contains every number and that each of the nine 3 × 3 blocks contains every number.) Given a particular Sudoku puzzle, to solve this puzzle we can find a solution to the satisfi- ability problems that asks for a set of truth values for the 729 variables p(i, j, n) that makes the conjunction of all the listed assertions true. ◂ 1.3.7 Solving Satisfiability Problems A truth table can be used to determine whether a compound proposition is satisfiable, or equivalently, whether its negation is a tautology (see Exercise 64). 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 220 = 1,048,576 rows in the truth table for a compound proposition with 20 variables. Thus, you need a com- puter 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 21000 (a number with more than 300 decimal digits) possible combinations of truth values of the variables in a compound proposi- tion 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 Links 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. Links 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. Courtesy of Harvard Sheffer introduced what is now known as the Sheffer stroke in 1913; it became well known only after University Portrait its use in the 1925 edition of Whitehead and Russell’s Principia Mathematica. In this same edition Russell Collection, Department of Philosophy 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. 38 1 / The Foundations: Logic and Proofs Exercises 1. Use truth tables to verify these equivalences. 13. Show that each conditional statement in Exercise 11 is a) p ∧ T ≡ p b) p ∨ F ≡ p a tautology using the fact that a conditional statement is c) p ∧ F ≡ F d) p ∨ T ≡ T false exactly when the hypothesis is true and the conclu- e) p ∨ p ≡ p f) p ∧ p ≡ p sion is false. (Do not use truth tables.) 2. Show that ¬(¬p) and p are logically equivalent. 14. Show that each conditional statement in Exercise 12 is 3. Use truth tables to verify the commutative laws a tautology using the fact that a conditional statement is a) p ∨ q ≡ q ∨ p. b) p ∧ q ≡ q ∧ p. false exactly when the hypothesis is true and the conclu- sion is false. (Do not use truth tables.) 4. Use truth tables to verify the associative laws 15. Show that each conditional statement in Exercise 11 is a a) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r). tautology by applying a chain of logical identities as in b) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r). Example 8. (Do not use truth tables.) 5. Use a truth table to verify the distributive law 16. Show that each conditional statement in Exercise 12 is a p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r). tautology by applying a chain of logical identities as in 6. Use a truth table to verify the first De Morgan law Example 8. (Do not use truth tables.) ¬(p ∧ q) ≡ ¬p ∨ ¬q. 17. Use truth tables to verify the absorption laws. 7. Use De Morgan’s laws to find the negation of each of the a) p ∨ (p ∧ q) ≡ p b) p ∧ (p ∨ q) ≡ p following statements. 18. Determine whether (¬p ∧ (p → q)) → ¬q is a tautology. a) Jan is rich and happy. b) Carlos will bicycle or run tomorrow. 19. Determine whether (¬q ∧ (p → q)) → ¬p is a tautology. c) Mei walks or takes the bus to class. Each of Exercises 20–32 asks you to show that two compound d) Ibrahim is smart and hard working. propositions are logically equivalent. To do this, either show 8. Use De Morgan’s laws to find the negation of each of the that both sides are true, or that both sides are false, for ex- following statements. actly the same combinations of truth values of the proposi- tional variables in these expressions (whichever is easier). a) Kwame will take a job in industry or go to graduate school. 20. Show that p ↔ q and (p ∧ q) ∨ (¬p ∧ ¬q) are logically b) Yoshiko knows Java and calculus. equivalent. c) James is young and strong. 21. Show that ¬(p ↔ q) and p ↔ ¬q are logically equivalent. d) Rita will move to Oregon or Washington. 22. Show that p → q and ¬q → ¬p are logically equivalent. 9. For each of these compound propositions, use the conditional-disjunction equivalence (Example 3) to find 23. Show that ¬p ↔ q and p ↔ ¬q are logically equivalent. an equivalent compound proposition that does not in- 24. Show that ¬(p ⊕ q) and p ↔ q are logically equivalent. volve conditionals. 25. Show that ¬(p ↔ q) and ¬p ↔ q are logically equivalent. a) p → ¬q 26. Show that (p → q) ∧ (p → r) and p → (q ∧ r) are logi- b) (p → q) → r cally equivalent. c) (¬q → p) → (p → ¬q) 27. Show that (p → r) ∧ (q → r) and (p ∨ q) → r are logi- 10. For each of these compound propositions, use the cally equivalent. conditional-disjunction equivalence (Example 3) to find an equivalent compound proposition that does not in- 28. Show that (p → q) ∨ (p → r) and p → (q ∨ r) are logi- volve conditionals. cally equivalent. a) ¬p → ¬q 29. Show that (p → r) ∨ (q → r) and (p ∧ q) → r are logi- b) (p ∨ q) → ¬p cally equivalent. c) (p → ¬q) → (¬p → q) 30. Show that ¬p → (q → r) and q → (p ∨ r) are logically 11. Show that each of these conditional statements is a tau- equivalent. tology by using truth tables. 31. Show that p ↔ q and (p → q) ∧ (q → p) are logically a) (p ∧ q) → p b) p → (p ∨ q) equivalent. c) ¬p → (p → q) d) (p ∧ q) → (p → q) 32. Show that p ↔ q and ¬p ↔ ¬q are logically equivalent. e) ¬(p → q) → p f ) ¬(p → q) → ¬q 33. Show that (p → q) ∧ (q → r) → (p → r) is a tautology. 12. Show that each of these conditional statements is a tau- tology by using truth tables. 34. Show that (p ∨ q) ∧ (¬p ∨ r) → (q ∨ r) is a tautology. a) [¬p ∧ (p ∨ q)] → q 35. Show that (p → q) → r and p → (q → r) are not logically b) [(p → q) ∧ (q → r)] → (p → r) equivalent. c) [p ∧ (p → q)] → q 36. Show that (p ∧ q) → r and (p → r) ∧ (q → r) are not log- d) [(p ∨ q) ∧ (p → r) ∧ (q → r)] → r ically equivalent.  1.3 Propositional Equivalences 39 37. Show that (p → q) → (r → s) and (p → r) → when either p or q, or both, are false; and it is false when both p (q → s) are not logically equivalent. and q are true. The proposition p NOR q is true when both The dual of a compound proposition that contains only the p and q are false, and it is false otherwise. The propositions logical operators ∨, ∧, and ¬ is the compound proposition p NAND q and p NOR q are denoted by p ∣ q and p ↓ q, respec- obtained by replacing each ∨ by ∧, each ∧ by ∨, each T tively. (The operators | and ↓ are called the Sheffer stroke and by F, and each F by T. The dual of s is denoted by s∗. the Peirce arrow after H. M. Sheffer and C. S. Peirce, respec- 38. Find the dual of each of these compound propositions. tively.) a) p ∨ ¬q b) p ∧ (q ∨ (r ∧ T)) 50. Construct a truth table for the logical operator NAND. c) (p ∧ ¬q) ∨ (q ∧ F) 51. Show that p ∣ q is logically equivalent to ¬(p ∧ q). 39. Find the dual of each of these compound propositions. 52. Construct a truth table for the logical operator NOR. a) p ∧ ¬q ∧ ¬r b) (p ∧ q ∧ r) ∨ s 53. Show that p ↓ q is logically equivalent to ¬(p ∨ q). c) (p ∨ F) ∧ (q ∨ T) 54. In this exercise we will show that {↓} is a functionally 40. When does s∗ = s, where s is a compound proposition? complete collection of logical operators. 41. Show that (s∗ )∗ = s when s is a compound proposition. a) Show that p ↓ p is logically equivalent to ¬p. b) Show that (p ↓ q) ↓ (p ↓ q) is logically equivalent to 42. Show that the logical equivalences in Table 6, except for p ∨ q. the double negation law, come in pairs, where each pair c) Conclude from parts (a) and (b), and Exercise 49, that contains compound propositions that are duals of each {↓} is a functionally complete collection of logical other. operators. ∗∗ 43. Why are the duals of two equivalent compound propo- ∗ 55. Find a compound proposition logically equivalent to sitions also equivalent, where these compound proposi- p → q using only the logical operator ↓. tions contain only the operators ∧, ∨, and ¬? 56. Show that {∣} is a functionally complete collection of log- 44. Find a compound proposition involving the propositional ical operators. variables p, q, and r that is true when p and q are true and r is false, but is false otherwise. [Hint: Use a con- 57. Show that p ∣ q and q ∣ p are equivalent. junction of each propositional variable or its negation.] 58. Show that p ∣ (q ∣ r) and (p ∣ q) ∣ r are not equivalent, so 45. Find a compound proposition involving the propositional that the logical operator ∣ is not associative. variables p, q, and r that is true when exactly two of p, q, ∗ 59. How many different truth tables of compound proposi- and r are true and is false otherwise. [Hint: Form a dis- tions are there that involve the propositional variables p junction of conjunctions. Include a conjunction for each and q? combination of values for which the compound proposi- 60. Show that if p, q, and r are compound propositions such tion is true. Each conjunction should include each of the that p and q are logically equivalent and q and r are log- three propositional variables or its negations.] ically equivalent, then p and r are logically equivalent. 46. Suppose that a truth table in n propositional variables is 61. The following sentence is taken from the specification of specified. Show that a compound proposition with this a telephone system: “If the directory database is opened, truth table can be formed by taking the disjunction of then the monitor is put in a closed state, if the sys- conjunctions of the variables or their negations, with one tem is not in its initial state.” This specification is hard conjunction included for each combination of values for to understand because it involves two conditional state- which the compound proposition is true. The resulting ments. Find an equivalent, easier-to-understand specifi- compound proposition is said to be in disjunctive nor- cation that involves disjunctions and negations but not mal form. conditional statements. A collection of logical operators is called functionally com- 62. How many of the disjunctions p ∨ ¬q, ¬p ∨ q, q ∨ r, plete if every compound proposition is logically equivalent q ∨ ¬r, and ¬q ∨ ¬r can be made simultaneously true by to a compound proposition involving only these logical oper- an assignment of truth values to p, q, and r? ators. 63. How many of the disjunctions p ∨ ¬q ∨ s, ¬p ∨ ¬r ∨ s, 47. Show that ¬, ∧, and ∨ form a functionally complete col- ¬p ∨ ¬r ∨ ¬s, ¬p ∨ q ∨ ¬s, q ∨ r ∨ ¬s, q ∨ ¬r ∨ ¬s, lection of logical operators. [Hint: Use the fact that ev- ¬p ∨ ¬q ∨ ¬s, p ∨ r ∨ s, and p ∨ r ∨¬s can be made si- ery compound proposition is logically equivalent to one multaneously true by an assignment of truth values to p, in disjunctive normal form, as shown in Exercise 46.] q, r, and s? ∗ 48. Show that ¬ and ∧ form a functionally complete col- 64. Show that the negation of an unsatisfiable compound lection of logical operators. [Hint: First use a De Mor- proposition is a tautology and the negation of a com- gan law to show that p ∨ q is logically equivalent to pound proposition that is a tautology is unsatisfiable. ¬(¬p ∧ ¬q).] 65. Determine whether each of these compound propositions ∗ 49. Show that ¬ and ∨ form a functionally complete collec- is satisfiable. tion of logical operators. a) (p ∨ ¬q) ∧ (¬p ∨ q) ∧ (¬p ∨ ¬q) We now present a group of exercises that involve the logical b) (p → q) ∧ (p → ¬q) ∧ (¬p → q) ∧ (¬p → ¬q) operators NAND and NOR. The proposition p NAND q is true c) (p ↔ q) ∧ (¬p ↔ q) 40 1 / The Foundations: Logic and Proofs 66. Determine whether each of these compound propositions used to find all solutions of the n-queens problem where is satisfiable. the queen in the first column is in an odd-numbered row. a) (p ∨ q ∨ ¬r) ∧ (p ∨ ¬q ∨ ¬s) ∧ (p ∨ ¬r ∨ ¬s) ∧ 69. Show how the solution of a given 4 × 4 Sudoku puzzle (¬p ∨ ¬q ∨ ¬s) ∧ (p ∨ q ∨ ¬s) can be found by solving a satisfiability problem. b) (¬p ∨ ¬q ∨ r) ∧ (¬p ∨ q ∨ ¬s) ∧ (p ∨ ¬q ∨ ¬s) ∧ (¬p ∨ ¬r ∨ ¬s) ∧ (p ∨ q ∨ ¬r) ∧ (p ∨ ¬r ∨ ¬s) 70. Construct a compound proposition that asserts that ev- c) (p ∨ q ∨ r) ∧ (p ∨ ¬q ∨ ¬s) ∧ (q ∨ ¬r ∨ s) ∧ (¬p ∨ ery cell of a 9 × 9 Sudoku puzzle contains at least one r ∨ s) ∧ (¬p ∨ q ∨ ¬s) ∧ (p ∨ ¬q ∨ ¬r) ∧ (¬p ∨ number. ¬q ∨ s) ∧ (¬p ∨ ¬r ∨ ¬s) 71. Explain the steps in the construction of the com- 67. Find the compound proposition Q constructed in Exam- pound proposition given in the text that asserts that ple 10 for the n-queens problem, and use it to find all the every column of a 9 × 9 Sudoku puzzle contains ways that n queens can be placed on an n × n chessboard, every number. so that no queen can attack another when n is ∗ 72. Explain the steps in the construction of the compound a) 2. b) 3. c) 4. proposition given in the text that asserts that each of 68. Starting with the compound proposition Q found in Ex- the nine 3 × 3 blocks of a 9 × 9 Sudoku puzzle contains ample 10, construct a compound proposition that can be every number. 1.4 Predicates and Quantifiers 1.4.1 Introduction Propositional logic, studied in Sections 1.1–1.3, cannot adequately express the meaning of all statements in mathematics and in natural language. For example, suppose that we know that “Every computer connected to the university network is functioning properly.” No rules of propositional logic allow us to conclude the truth of the statement “MATH3 is functioning properly,” where MATH3 is one of the computers connected to the university network. Likewise, we can- not use the rules of propositional logic to conclude from the statement “CS2 is under attack by an intruder,” where CS2 is a computer on the university network, to conclude the truth of “There is a computer on the university network that is under attack by an intruder.” In this section we will introduce a more powerful type of logic called predicate logic. We will see how predicate logic can be used to express the meaning of a wide range of statements in mathematics and computer science in ways that permit us to reason and explore relationships between objects. To understand predicate logic, we first need to introduce the concept of a predicate. Afterward, we will introduce the notion of quantifiers, which enable us to reason with statements that assert that a certain property holds for all objects of a certain type and with statements that assert the existence of an object with a particular property. 1.4.2 Predicates Statements involving variables, such as “x > 3,” “x = y + 3,” “x + y = z,”  1.4 Predicates and Quantifiers 41 and “Computer x is under attack by an intruder,” and “Computer x is functioning properly,” are often found in mathematical assertions, in computer programs, and in system specifications. These statements are neither true nor false when the values of the variables are not specified. In this section, we will discuss the ways that propositions can be produced from such statements. The statement “x is greater than 3” has two parts. The first part, the variable x, is the subject of the statement. The second part—the predicate, “is greater than 3”—refers to a property that the subject of the statement can have. We can denote the statement “x is greater than 3” by P(x), where P denotes the predicate “is greater than 3” and x is the variable. The statement P(x) is also said to be the value of the propositional function P at x. Once a value has been assigned to the variable x, the statement P(x) becomes a proposition and has a truth value. Consider Examples 1 and 2. EXAMPLE 1 Let P(x) denote the statement “x > 3.” What are the truth values of P(4) and P(2)? Solution: We obtain the statement P(4) by setting x = 4 in the statement “x > 3.” Hence, P(4), which is the statement “4 > 3,” is true. However, P(2), which is the statement “2 > 3,” is false. ◂ EXAMPLE 2 Let A(x) denote the statement “Computer x is under attack by an intruder.” Suppose that of the computers on campus, only CS2 and MATH1 are currently under attack by intruders. What are truth values of A(CS1), A(CS2), and A(MATH1)? Solution: We obtain the statement A(CS1) by setting x = CS1 in the statement “Computer x is under attack by an intruder.” Because CS1 is not on the list of computers currently under attack, we conclude that A(CS1) is false. Similarly, because CS2 and MATH1 are on the list of computers under attack, we know that A(CS2) and A(MATH1) are true. ◂ We can also have statements that involve more than one variable. For instance, consider the statement “x = y + 3.” We can denote this statement by Q(x, y), where x and y are variables and Q is the predicate. When values are assigned to the variables x and y, the statement Q(x, y) has a truth value. EXAMPLE 3 Let Q(x, y) denote the statement “x = y + 3.” What are the truth values of the propositions Extra Q(1, 2) and Q(3, 0)? Examples Solution: To obtain Q(1, 2), set x = 1 and y = 2 in the statement Q(x, y). Hence, Q(1, 2) is the statement “1 = 2 + 3,” which is false. The statement Q(3, 0) is the proposition “3 = 0 + 3,” which is true. ◂ EXAMPLE 4 Let A(c, n) denote the statement “Computer c is connected to network n,” where c is a variable representing a computer and n is a variable representing a network. Suppose that the computer MATH1 is connected to network CAMPUS2, but not to network CAMPUS1. What are the values of A(MATH1, CAMPUS1) and A(MATH1, CAMPUS2)? 42 1 / The Foundations: Logic and Proofs Solution: Because MATH1 is not connected to the CAMPUS1 network, we see that A(MATH1, CAMPUS1) is false. However, because MATH1 is connected to the CAMPUS2 network, we see that A(MATH1, CAMPUS2) is true. ◂ Similarly, we can let R(x, y, z) denote the statement “x + y = z.” When values are assigned to the variables x, y, and z, this statement has a truth value. EXAMPLE 5 What are the truth values of the propositions R(1, 2, 3) and R(0, 0, 1)? Solution: The proposition R(1, 2, 3) is obtained by setting x = 1, y = 2, and z = 3 in the state- ment R(x, y, z). We see that R(1, 2, 3) is the statement “1 + 2 = 3,” which is true. Also note that R(0, 0, 1), which is the statement “0 + 0 = 1,” is false. ◂ In general, a statement involving the n variables x1 , x2 , … , xn can be denoted by P(x1 , x2 , … , xn ). A statement of the form P(x1 , x2 , … , xn ) is the value of the propositional function P at the n-tuple (x1 , x2 , … , xn ), and P is also called an n-place predicate or an n-ary predicate. Propositional functions occur in computer programs, as Example 6 demonstrates. EXAMPLE 6 Consider the statement if x > 0 then x := x + 1. Links CHARLES SANDERS PEIRCE (1839–1914) Many consider Charles Peirce, born in Cambridge, Mas- sachusetts, to be the most original and versatile American intellect. He made important contributions to an amazing number of disciplines, including mathematics, astronomy, chemistry, geodesy, metrology, engineer- ing, psychology, philology, the history of science, and economics. Peirce was also an inventor, a lifelong student of medicine, a book reviewer, a dramatist and an actor, a short story writer, a phenomenologist, a logician, and a metaphysician. He is noted as the preeminent system-building philosopher competent and productive in logic, mathematics, and a wide range of sciences. He was encouraged by his father, Benjamin Peirce, a professor of mathematics and natural philosophy at Harvard, to pursue a career in science. Instead, he decided to study logic Bettmann/Getty c Images and scientific methodology. Peirce attended Harvard (1855–1859) and received a Harvard master of arts degree (1862) and an advanced degree in chemistry from the Lawrence Scientific School (1863). In 1861, Peirce became an aide in the U.S. Coast Survey, with the goal of better understanding scientific methodology. His service for the Survey exempted him from military service during the Civil War. While working for the Survey, Peirce did astro- nomical and geodesic work. He made fundamental contributions to the design of pendulums and to map projections, applying new mathematical developments in the theory of elliptic functions. He was the first person to use the wavelength of light as a unit of measurement. Peirce rose to the position of Assistant for the Survey, a position he held until forced to resign in 1891 when he disagreed with the direction taken by the Survey’s new administration. While making his living from work in the physical sciences, Peirce developed a hierarchy of sciences, with mathematics at the top rung, in which the methods of one science could be adapted for use by those sciences under it in the hierarchy. During this time, he also founded the American philosophical theory of pragmatism. The only academic position Peirce ever held was lecturer in logic at Johns Hopkins University in Baltimore (1879–1884). His mathematical work during this time included contributions to logic, set theory, abstract algebra, and the philosophy of mathematics. His work is still relevant today, with recent applications to artificial intelligence. Peirce believed that the study of mathematics could develop the mind’s powers of imagination, abstraction, and generalization. His diverse activities after retiring from the Survey included writing for periodicals, contributing to scholarly dictionaries, translating scientific papers, guest lecturing, and textbook writing. Unfortunately, his income from these pursuits was insufficient to protect him and his second wife from abject poverty. He was supported in his later years by a fund created by his many admirers and administered by the philosopher William James, his lifelong friend. Although Peirce wrote and published voluminously in a vast range of subjects, he left more than 100,000 pages of unpublished manuscripts. Because of the difficulty of studying his unpublished writings, scholars have only recently started to understand some of his varied contributions. A group of people is devoted to making his work available over the Internet to bring a better appreciation of Peirce’s accomplishments to the world.  1.4 Predicates and Quantifiers 43 When this statement is encountered in a program, the value of the variable x at that point in the execution of the program is inserted into P(x), which is “x > 0.” If P(x) is true for this value of x, the assignment statement x := x + 1 is executed, so the value of x is increased by 1. If P(x) is false for this value of x, the assignment statement is not executed, so the value of x is not changed. ◂ PRECONDITIONS AND POSTCONDITIONS Predicates are also used to establish the correctness of computer programs, that is, to show that computer programs always produce the desired output when given valid input. (Note that unless the correctness of a computer program is established, no amount of testing can show that it produces the desired output for all input values, unless every input value is tested.) The statements that describe valid input are known as preconditions and the conditions that the output should satisfy when the program has run are known as postconditions. As Example 7 illustrates, we use predicates to describe both preconditions and postconditions. We will study this process in greater detail in Section 5.5. EXAMPLE 7 Consider the following program, designed to interchange the values of two variables x and y. temp := x x := y y := temp Find predicates that we can use as the precondition and the postcondition to verify the correct- ness of this program. Then explain how to use them to verify that for all valid input the program does what is intended. Solution: For the precondition, we need to express that x and y have particular values before we run the program. So, for this precondition we can use the predicate P(x, y), where P(x, y) is the statement “x = a and y = b,” where a and b are the values of x and y before we run the program. Because we want to verify that the program swaps the values of x and y for all input values, for the postcondition we can use Q(x, y), where Q(x, y) is the statement “x = b and y = a.” To verify that the program always does what it is supposed to do, suppose that the pre- condition P(x, y) holds. That is, we suppose that the statement “x = a and y = b” is true. This means that x = a and y = b. The first step of the program, temp := x, assigns the value of x to the variable temp, so after this step we know that x = a, temp = a, and y = b. After the second step of the program, x := y, we know that x = b, temp = a, and y = b. Finally, after the third step, we know that x = b, temp = a, and y = a. Consequently, after this program is run, the postcondition Q(x, y) holds, that is, the statement “x = b and y = a” is true. ◂ 1.4.3 Quantifiers When the variables in a propositional function are assigned values, the resulting statement be- comes a proposition with a certain truth value. However, there is another important way, called quantification, to create a proposition from a propositional function. Quantification expresses the extent to which a predicate is true over a range of elements. In English, the words all, some, Assessment many, none, and few are used in quantifications. We will focus on two types of quantification here: universal quantification, which tells us that a predicate is true for every element under consideration, and existential quantification, which tells us that there is one or more element under consideration for which the predicate is true. The area of logic that deals with predicates and quantifiers is called the predicate calculus. 44 1 / The Foundations: Logic and Proofs THE UNIVERSAL QUANTIFIER Many mathematical statements assert that a property is Assessment true for all values of a variable in a particular domain, called the domain of discourse (or the universe of discourse), often just referred to as the domain. Such a statement is expressed us- ing universal quantification. The universal quantification of P(x) for a particular domain is the proposition that asserts that P(x) is true for all values of x in this domain. Note that the domain specifies the possible values of the variable x. The meaning of the universal quantification of P(x) changes when we change the domain. The domain must always be specified when a uni- versal quantifier is used; without it, the universal quantification of a statement is not defined. Definition 1 The universal quantification of P(x) is the statement “P(x) for all values of x in the domain.” The notation ∀xP(x) denotes the universal quantification of P(x). Here ∀ is called the universal quantifier. We read ∀xP(x) as “for all xP(x)” or “for every xP(x).” An element for which P(x) is false is called a counterexample to ∀xP(x). The meaning of the universal quantifier is summarized in the first row of Table 1. We illus- trate the use of the universal quantifier in Examples 8–12 and 15. EXAMPLE 8 Let P(x) be the statement “x + 1 > x.” What is the truth value of the quantification ∀xP(x), where Extra the domain consists of all real numbers? Examples Solution: Because P(x) is true for all real numbers x, the quantification ∀xP(x) is true. ◂ Remark: Generally, an implicit assumption is made that all domains of discourse for quantifiers are nonempty. Note that if the domain is empty, then ∀xP(x) is true for any propositional function P(x) because there are no elements x in the domain for which P(x) is false. Remember that the truth Besides “for all” and “for every,” universal quantification can be expressed in many other value of ∀xP(x) depends on the domain! ways, including “all of,” “for each,” “given any,” “for arbitrary,” “for each,” and “for any.” Remark: It is best to avoid using “for any x” because it is often ambiguous as to whether “any” means “every” or “some.” In some cases, “any” is unambiguous, such as when it is used in negatives: “There is not any reason to avoid studying.” A statement ∀xP(x) is false, where P(x) is a propositional function, if and only if P(x) is not always true when x is in the domain. One way to show that P(x) is not always true when x is in the domain is to find a counterexample to the statement ∀xP(x). Note that a single counterexample is all we need to establish that ∀xP(x) is false. Example 9 illustrates how counterexamples are used. TABLE 1 Quantifiers. Statement When True? When False? ∀xP(x) P(x) is true for every x. There is an x for which P(x) is false. ∃xP(x) There is an x for which P(x) is true. P(x) is false for every x.  1.4 Predicates and Quantifiers 45 EXAMPLE 9 Let Q(x) be the statement “x < 2.” What is the truth value of the quantification ∀xQ(x), where the domain consists of all real numbers? Solution: Q(x) is not true for every real number x, because, for instance, Q(3) is false. That is, x = 3 is a counterexample for the statement ∀xQ(x). Thus, ∀xQ(x) is false. ◂ EXAMPLE 10 Suppose that P(x) is “x2 > 0.” To show that the statement ∀xP(x) is false where the universe of discourse consists of all integers, we give a counterexample. We see that x = 0 is a counterex- ample because x2 = 0 when x = 0, so that x2 is not greater than 0 when x = 0. ◂ Looking for counterexamples to universally quantified statements is an important activity in the study of mathematics, as we will see in subsequent sections of this book. EXAMPLE 11 What does the statement ∀xN(x) mean if N(x) is “Computer x is connected to the network” and the domain consists of all computers on campus? Solution: The statement ∀xN(x) means that for every computer x on campus, that computer x is connected to the network. This statement can be expressed in English as “Every computer on campus is connected to the network.” ◂ As we have pointed out, specifying the domain is mandatory when quantifiers are used. The truth value of a quantified statement often depends on which elements are in this domain, as Example 12 shows. EXAMPLE 12 What is the truth value of ∀x(x2 ≥ x) if the domain consists of all real numbers? What is the truth value of this statement if the domain consists of all integers? Solution: The universal quantification ∀x(x2 ≥ x), where the domain consists of all real num- bers, is false. For example, ( 12 )2 ≱ 12. Note that x2 ≥ x if and only if x2 − x = x(x − 1) ≥ 0. Con- sequently, x2 ≥ x if and only if x ≤ 0 or x ≥ 1. It follows that ∀x(x2 ≥ x) is false if the domain consists of all real numbers (because the inequality is false for all real numbers x with 0 < x < 1). However, if the domain consists of the integers, ∀x(x2 ≥ x) is true, because there are no integers x with 0 < x < 1. ◂ THE EXISTENTIAL QUANTIFIER Many mathematical statements assert that there is an element with a certain property. Such statements are expressed using existential quantification. With existential quantification, we form a proposition that is true if and only if P(x) is true for at least one value of x in the domain. Definition 2 The existential quantification of P(x) is the proposition “There exists an element x in the domain such that P(x).” We use the notation ∃xP(x) for the existential quantification of P(x). Here ∃ is called the existential quantifier. 46 1 / The Foundations: Logic and Proofs A domain must always be specified when a statement ∃xP(x) is used. Furthermore, the meaning of ∃xP(x) changes when the domain changes. Without specifying the domain, the state- ment ∃xP(x) has no meaning. Besides the phrase “there exists,” we can also express existential quantification in many other ways, such as by using the words “for some,” “for at least one,” or “there is.” The existential quantification ∃xP(x) is read as “There is an x such that P(x),” “There is at least one x such that P(x),” or “For some xP(x).” The meaning of the existential quantifier is summarized in the second row of Table 1. We illustrate the use of the existential quantifier in Examples 13, 14, and 16. EXAMPLE 13 Let P(x) denote the statement “x > 3.” What is the truth value of the quantification ∃xP(x), Extra where the domain consists of all real numbers? Examples Solution: Because “x > 3” is sometimes true—for instance, when x = 4—the existential quan- tification of P(x), which is ∃xP(x), is true. ◂ Observe that the statement ∃xP(x) is false if and only if there is no element x in the domain for which P(x) is true. That is, ∃xP(x) is false if and only if P(x) is false for every element of the domain. We illustrate this observation in Example 14. EXAMPLE 14 Let Q(x) denote the statement “x = x + 1.” What is the truth value of the quantification ∃xQ(x), where the domain consists of all real numbers? Solution: Because Q(x) is false for every real number x, the existential quantification of Q(x), which is ∃xQ(x), is false. ◂ Remember that the truth value of ∃xP(x) depends on the domain! Remark: Generally, an implicit assumption is made that all domains of discourse for quantifiers are nonempty. If the domain is empty, then ∃xQ(x) is false whenever Q(x) is a propositional function because when the domain is empty, there can be no element x in the domain for which Q(x) is true. THE UNIQUENESS QUANTIFIER We have now introduced universal and existential quan- tifiers. These are the most important quantifiers in mathematics and computer science. However, there is no limitation on the number of different quantifiers we can define, such as “there are exactly two,” “there are no more than three,” “there are at least 100,” and so on. Of these other quantifiers, the one that is most often seen is the uniqueness quantifier, denoted by ∃! or ∃1. The notation ∃!xP(x) [or ∃1 xP(x)] states “There exists a unique x such that P(x) is true.” (Other phrases for uniqueness quantification include “there is exactly one” and “there is one and only one.”) For instance, ∃!x(x − 1 = 0), where the domain is the set of real numbers, states that there is a unique real number x such that x − 1 = 0. This is a true statement, as x = 1 is the unique real number such that x − 1 = 0. Observe that we can use quantifiers and propositional logic to express uniqueness (see Exercise 52 in Section 1.5), so the uniqueness quantifier can be avoided. Generally, it is best to stick with existential and universal quantifiers so that rules of inference for these quantifiers can be used.  1.4 Predicates and Quantifiers 47 1.4.4 QUANTIFIERS OVER FINITE DOMAINS When the domain of a quantifier is finite, that is, when all its elements can be listed, quantified statements can be expressed using propositional logic. In particular, when the elements of the domain are x1 , x2 , …, xn , where n is a positive integer, the universal quantification ∀xP(x) is the same as the conjunction P(x1 ) ∧ P(x2 ) ∧ ⋯ ∧ P(xn ), because this conjunction is true if and only if P(x1 ), P(x2 ), … , P(xn ) are all true. EXAMPLE 15 What is the truth value of ∀xP(x), where P(x) is the statement “x2 < 10” and the domain consists of the positive integers not exceeding 4? Solution: The statement ∀xP(x) is the same as the conjunction P(1) ∧ P(2) ∧ P(3) ∧ P(4), because the domain consists of the integers 1, 2, 3, and 4. Because P(4), which is the statement “42 < 10,” is false, it follows that ∀xP(x) is false. ◂ Similarly, when the elements of the domain are x1 , x2 , … , xn , where n is a positive integer, the existential quantification ∃xP(x) is the same as the disjunction P(x1 ) ∨ P(x2 ) ∨ ⋯ ∨ P(xn ), because this disjunction is true if and only if at least one of P(x1 ), P(x2 ), … , P(xn ) is true. EXAMPLE 16 What is the truth value of ∃xP(x), where P(x) is the statement “x2 > 10” and the universe of discourse consists of the positive integers not exceeding 4? Solution: Because the domain is {1, 2, 3, 4}, the proposition ∃xP(x) is the same as the disjunction P(1) ∨ P(2) ∨ P(3) ∨ P(4). Because P(4), which is the statement “42 > 10,” is true, it follows that ∃xP(x) is true. ◂ CONNECTIONS BETWEEN QUANTIFICATION AND LOOPING It is sometimes helpful to think in terms of looping and searching when determining the truth value of a quantification. Suppose that there are n objects in the domain for the variable x. To determine whether ∀xP(x) is true, we can loop through all n values of x to see whether P(x) is always true. If we encounter a value x for which P(x) is false, then we have shown that ∀xP(x) is false. Otherwise, ∀xP(x) is true. To see whether ∃xP(x) is true, we loop through the n values of x searching for a value for which P(x) is true. If we find one, then ∃xP(x) is true. If we never find such an x, then we have determined that ∃xP(x) is false. (Note that this searching procedure does not apply if there are infinitely many values in the domain. However, it is still a useful way of thinking about the truth values of quantifications.) 48 1 / The Foundations: Logic and Proofs 1.4.5 Quantifiers with Restricted Domains An abbreviated notation is often used to restrict the domain of a quantifier. In this nota- tion, a condition a variable must satisfy is included after the quantifier. This is illustrated in Example 17. We will also describe other forms of this notation involving set membership in Section 2.1. EXAMPLE 17 What do the statements ∀x < 0 (x2 > 0), ∀y ≠ 0 (y3 ≠ 0), and ∃z > 0 (z2 = 2) mean, where the domain in each case consists of the real numbers? Solution: The statement ∀x < 0 (x2 > 0) states that for every real number x with x < 0, x2 > 0. That is, it states “The square of a negative real number is positive.” This statement is the same as ∀x(x < 0 → x2 > 0). The statement ∀y ≠ 0 (y3 ≠ 0) states that for every real number y with y ≠ 0, we have y3 ≠ 0. That is, it states “The cube of every nonzero real number is nonzero.” This statement is equivalent to ∀y(y ≠ 0 → y3 ≠ 0). Finally, the statement ∃z > 0 (z2 = 2) states that there exists a real number z with z > 0 such that z2 = 2. That is, it states “There is a positive square root of 2.” This statement is equivalent to ∃z(z > 0 ∧ z2 = 2). ◂ Note that the restriction of a universal quantification is the same as the universal quantifi- cation of a conditional statement. For instance, ∀x < 0 (x2 > 0) is another way of expressing ∀x(x < 0 → x2 > 0). On the other hand, the restriction of an existential quantification is the same as the existential quantification of a conjunction. For instance, ∃z > 0 (z2 = 2) is another way of expressing ∃z(z > 0 ∧ z2 = 2). 1.4.6 Precedence of Quantifiers The quantifiers ∀ and ∃ have higher precedence than all logical operators from propositional calculus. For example, ∀xP(x) ∨ Q(x) is the disjunction of ∀xP(x) and Q(x). In other words, it means (∀xP(x)) ∨ Q(x) rather than ∀x(P(x) ∨ Q(x)). 1.4.7 Binding Variables When a quantifier is used on the variable x, we say that this occurrence of the variable is bound. An occurrence of a variable that is not bound by a quantifier or set equal to a particular value is said to be free. All the variables that occur in a propositional function must be bound or set equal to a particular value to turn it into a proposition. This can be done using a combination of universal quantifiers, existential quantifiers, and value assignments. The part of a logical expression to which a quantifier is applied is called the scope of this quantifier. Consequently, a variable is free if it is outside the scope of all quantifiers in the formula that specify this variable. EXAMPLE 18 In the statement ∃x(x + y = 1), the variable x is bound by the existential quantification ∃x, but the variable y is free because it is not bound by a quantifier and no value is assigned to this variable. This illustrates that in the statement ∃x(x + y = 1), x is bound, but y is free. In the statement ∃x(P(x) ∧ Q(x)) ∨ ∀xR(x), all variables are bound. The scope of the first quantifier, ∃x, is the expression P(x) ∧ Q(x), because ∃x is applied only to P(x) ∧ Q(x) and not to the rest of the statement. Similarly, the scope of the second quantifier, ∀x, is the expression R(x). That is, the existential quantifier binds the variable x in P(x) ∧ Q(x) and the universal quantifier ∀x binds the variable x in R(x). Observe that we could have written our statement using two different variables x and y, as ∃x(P(x) ∧ Q(x)) ∨ ∀yR(y), because the scopes of the two quantifiers do not overlap. The reader should be aware that in common usage, the same  1.4 Predicates and Quantifiers 49 letter is often used to represent variables bound by different quantifiers with scopes that do not overlap. ◂ 1.4.8 Logical Equivalences Involving Quantifiers In Section 1.3 we introduced the notion of logical equivalences of compound propositions. We can extend this notion to expressions involving predicates and quantifiers. Definition 3 Statements involving predicates and quantifiers are logically equivalent if and only if they have the same truth value no matter which predicates are substituted into these statements and which domain of discourse is used for the variables in these propositional functions. We use the notation S ≡ T to indicate that two statements S and T involving predicates and quantifiers are logically equivalent. Example 19 illustrates how to show that two statements involving predicates and quantifiers are logically equivalent. EXAMPLE 19 Show that ∀x(P(x) ∧ Q(x)) and ∀xP(x) ∧ ∀xQ(x) are logically equivalent (where the same do- main is used throughout). This logical equivalence shows that we can distribute a universal quantifier over a conjunction. Furthermore, we can also distribute an existential quantifier over a disjunction. However, we cannot distribute a universal quantifier over a disjunction, nor can we distribute an existential quantifier over a conjunction. (See Exercises 52 and 53.) Solution: To show that these statements are logically equivalent, we must show that they always take the same truth value, no matter what the predicates P and Q are, and no matter which domain of discourse is used. Suppose we have particular predicates P and Q, with a common domain. We can show that ∀x(P(x) ∧ Q(x)) and ∀xP(x) ∧ ∀xQ(x) are logically equivalent by doing two things. First, we show that if ∀x(P(x) ∧ Q(x)) is true, then ∀xP(x) ∧ ∀xQ(x) is true. Second, we show that if ∀xP(x) ∧ ∀xQ(x) is true, then ∀x(P(x) ∧ Q(x)) is true. So, suppose that ∀x(P(x) ∧ Q(x)) is true. This means that if a is in the domain, then P(a) ∧ Q(a) is true. Hence, P(a) is true and Q(a) is true. Because P(a) is true and Q(a) is true for every element a in the domain, we can conclude that ∀xP(x) and ∀xQ(x) are both true. This means that ∀xP(x) ∧ ∀xQ(x) is true. Next, suppose that ∀xP(x) ∧ ∀xQ(x) is true. It follows that ∀xP(x) is true and ∀xQ(x) is true. Hence, if a is in the domain, then P(a) is true and Q(a) is true [because P(x) and Q(x) are both true for all elements in the domain, there is no conflict using the same value of a here]. It follows that for all a, P(a) ∧ Q(a) is true. It follows that ∀x(P(x) ∧ Q(x)) is true. We can now conclude that ∀x(P(x) ∧ Q(x)) ≡ ∀xP(x) ∧ ∀xQ(x). ◂ 1.4.9 Negating Quantified Expressions We will often want to consider the negation of a quantified expression. For instance, consider the negation of the statement “Every student in your class has taken a course in calculus.” This statement is a universal quantification, namely, ∀xP(x), 50 1 / The Foundations: Logic and Proofs Assessment where P(x) is the statement “x has taken a course in calculus” and the domain consists of the students in your class. The negation of this statement is “It is not the case that every student in your class has taken a course in calculus.” This is equivalent to “There is a student in your class who has not taken a course in calculus.” And this is simply the existential quantification of the negation of the original propositional function, namely, ∃x ¬P(x). This example illustrates the following logical equivalence: ¬∀xP(x) ≡ ∃x ¬P(x). To show that ¬∀xP(x) and ∃xP(x) are logically equivalent no matter what the propositional function P(x) is and what the domain is, first note that ¬∀xP(x) is true if and only if ∀xP(x) is false. Next, note that ∀xP(x) is false if and only if there is an element x in the domain for which P(x) is false. This holds if and only if there is an element x in the domain for which ¬P(x) is true. Finally, note that there is an element x in the domain for which ¬P(x) is true if and only if ∃x ¬P(x) is true. Putting these steps together, we can conclude that ¬∀xP(x) is true if and only if ∃x ¬P(x) is true. It follows that ¬∀xP(x) and ∃x ¬P(x) are logically equivalent. Suppose we wish to negate an existential quantification. For instance, consider the proposi- tion “There is a student in this class who has taken a course in calculus.” This is the existential quantification ∃xQ(x), where Q(x) is the statement “x has taken a course in calculus.” The negation of this statement is the proposition “It is not the case that there is a student in this class who has taken a course in calculus.” This is equivalent to “Every student in this class has not taken calculus,” which is just the universal quantification of the negation of the original propositional function, or, phrased in the language of quantifiers, ∀x ¬Q(x). This example illustrates the equivalence ¬∃xQ(x) ≡ ∀x ¬Q(x). To show that ¬∃xQ(x) and ∀x ¬Q(x) are logically equivalent no matter what Q(x) is and what the domain is, first note that ¬∃xQ(x) is true if and only if ∃xQ(x) is false. This is true if and only if no x exists in the domain for which Q(x) is true. Next, note that no x exists in the domain for which Q(x) is true if and only if Q(x) is false for every x in the domain. Finally, note that Q(x) is false for every x in the domain if and only if ¬Q(x) is true for all x in the domain, which holds if and only if ∀x¬Q(x) is true. Putting these steps together, we see that ¬∃xQ(x) is true if and only if ∀x¬Q(x) is true. We conclude that ¬∃xQ(x) and ∀x ¬Q(x) are logically equivalent. The rules for negations for quantifiers are called De Morgan’s laws for quantifiers. These rules are summarized in Table 2. Remark: When the domain of a predicate P(x) consists of n elements, where n is a positive integer greater than one, the rules for negating quantified statements are exactly the same as De Morgan’s laws discussed in Section 1.3. This is why these rules are called De Morgan’s laws for quantifiers. When the domain has n elements x1 , x2 , … , xn , it follows that ¬∀xP(x) is the same as ¬(P(x1 ) ∧ P(x2 ) ∧ ⋯ ∧ P(xn )), which is equivalent to ¬P(x1 ) ∨ ¬P(x2 ) ∨ ⋯ ∨ ¬P(xn ) by De Morgan’s laws, and this is the same as ∃x¬P(x). Similarly, ¬∃xP(x) is the same as ¬(P(x1 ) ∨  1.4 Predicates and Quantifiers 51 TABLE 2 De Morgan’s Laws for Quantifiers. Negation Equivalent Statement When Is Negation True? When False? ¬∃xP(x) ∀x¬P(x) For every x, P(x) is false. There is an x for which P(x) is true. ¬∀xP(x) ∃x¬P(x) There is an x for which P(x) is true for every x. P(x) is false. P(x2 ) ∨ ⋯ ∨ P(xn )), which by De Morgan’s laws is equivalent to ¬P(x1 ) ∧ ¬P(x2 ) ∧ ⋯ ∧ ¬P(xn ), and this is the same as ∀x¬P(x). We illustrate the negation of quantified statements in Examples 20 and 21. EXAMPLE 20 What are the negations of the statements “There is an honest politician” and “All Americans eat cheeseburgers”? Solution: Let H(x) denote “x is honest.” Then the statement “There is an honest politician” is rep- resented by ∃xH(x), where the domain consists of all politicians. The negation of this statement is ¬∃xH(x), which is equivalent to ∀x¬H(x). This negation can be expressed as “Every politician is dishonest.” (Note: In English, the statement “All politicians are not honest” is ambiguous. In common usage, this statement often means “Not all politicians are honest.” Consequently, we do not use this statement to express this negation.) Extra Let C(x) denote “x eats cheeseburgers.” Then the statement “All Americans eat cheeseburg- Examples ers” is represented by ∀xC(x), where the domain consists of all Americans. The negation of this statement is ¬∀xC(x), which is equivalent to ∃x¬C(x). This negation can be expressed in sev- eral different ways, including “Some American does not eat cheeseburgers” and “There is an American who does not eat cheeseburgers.” ◂ EXAMPLE 21 What are the negations of the statements ∀x(x2 > x) and ∃x(x2 = 2)? Solution: The negation of ∀x(x2 > x) is the statement ¬∀x(x2 > x), which is equivalent to ∃x¬(x2 > x). This can be rewritten as ∃x(x2 ≤ x). The negation of ∃x(x2 = 2) is the statement ¬∃x(x2 = 2), which is equivalent to ∀x¬(x2 = 2). This can be rewritten as ∀x(x2 ≠ 2). The truth values of these statements depend on the domain. ◂ We use De Morgan’s laws for quantifiers in Example 22. EXAMPLE 22 Show that ¬∀x(P(x) → Q(x)) and ∃x(P(x) ∧ ¬Q(x)) are logically equivalent. Solution: By De Morgan’s law for universal quantifiers, we know that ¬∀x(P(x) → Q(x)) and ∃x(¬(P(x) → Q(x))) are logically equivalent. By the fifth logical equivalence in Table 7 in Sec- tion 1.3, we know that ¬(P(x) → Q(x)) and P(x) ∧ ¬Q(x) are logically equivalent for every x. Because we can substitute one logically equivalent expression for another in a logical equiva- lence, it follows that ¬∀x(P(x) → Q(x)) and ∃x(P(x) ∧ ¬Q(x)) are logically equivalent. ◂ 1.4.10 Translating from English into Logical Expressions Translating sentences in English (or other natural languages) into logical expressions is a cru- cial task in mathematics, logic programming, artificial intelligence, software engineering, and many other disciplines. We began studying this topic in Section 1.1, where we used propositions 52 1 / The Foundations: Logic and Proofs to express sentences in logical expressions. In that discussion, we purposely avoided sentences whose translations required predicates and quantifiers. Translating from English to logical ex- pressions becomes even more complex when quantifiers are needed. Furthermore, there can be many ways to translate a particular sentence. (As a consequence, there is no “cookbook” approach that can be followed step by step.) We will use some examples to illustrate how to translate sentences from English into logical expressions. The goal in this translation is to pro- duce simple and useful logical expressions. In this section, we restrict ourselves to sentences that can be translated into logical expressions using a single quantifier; in the next section, we will look at more complicated sentences that require multiple quantifiers. EXAMPLE 23 Express the statement “Every student in this class has studied calculus” using predicates and quantifiers. Extra Examples Solution: First, we rewrite the statement so that we can clearly identify the appropriate quanti- fiers to use. Doing so, we obtain: “For every student in this class, that student has studied calculus.” Next, we introduce a variable x so that our statement becomes “For every student x in this class, x has studied calculus.” Continuing, we introduce C(x), which is the statement “x has studied calculus.” Consequently, if the domain for x consists of the students in the class, we can translate our statement as ∀xC(x). However, there are other correct approaches; different domains of discourse and other predi- cates can be used. The approach we select depends on the subsequent reasoning we want to carry out. For example, we may be interested in a wider group of people than only those in this class. If we change the domain to consist of all people, we will need to express our statement as “For every person x, if person x is a student in this class, then x has studied calculus.” If S(x) represents the statement that person x is in this class, we see that our statement can be expressed as ∀x(S(x) → C(x)). [Caution! Our statement cannot be expressed as ∀x(S(x) ∧ C(x)) because this statement says that all people are students in this class and have studied calculus!] Finally, when we are interested in the background of people in subjects besides calculus, we may prefer to use the two-variable quantifier Q(x, y) for the statement “Student x has stud- ied subject y.” Then we would replace C(x) by Q(x, calculus) in both approaches to obtain ∀xQ(x, calculus) or ∀x(S(x) → Q(x, calculus)). ◂ In Example 23 we displayed different approaches for expressing the same statement us- ing predicates and quantifiers. However, we should always adopt the simplest approach that is adequate for use in subsequent reasoning. EXAMPLE 24 Express the statements “Some student in this class has visited Mexico” and “Every student in this class has visited either Canada or Mexico” using predicates and quantifiers. Solution: The statement “Some student in this class has visited Mexico” means that “There is a student in this class with the property that the student has visited Mexico.” We can introduce a variable x, so that our statement becomes “There is a student x in this class having the property that x has visited Mexico.”  1.4 Predicates and Quantifiers 53 We introduce M(x), which is the statement “x has visited Mexico.” If the domain for x consists of the students in this class, we can translate this first statement as ∃xM(x). However, if we are interested in people other than those in this class, we look at the statement a little differently. Our statement can be expressed as “There is a person x having the properties that x is a student in this class and x has visited Mexico.” In this case, the domain for the variable x consists of all people. We introduce S(x) to represent “x is a student in this class.” Our solution becomes ∃x(S(x) ∧ M(x)) because the statement is that there is a person x who is a student in this class and who has visited Mexico. [Caution! Our statement cannot be expressed as ∃x(S(x) → M(x)), which is true when there is someone not in the class because, in that case, for such a person x, S(x) → M(x) becomes either F → T or F → F, both of which are true.] Similarly, the second statement can be expressed as “For every x in this class, x has the property that x has visited Mexico or x has visited Canada.” (Note that we are assuming the inclusive, rather than the exclusive, or here.) We let C(x) be “x has visited Canada.” Following our earlier reasoning, we see that if the domain for x consists of the students in this class, this second statement can be expressed as ∀x(C(x) ∨ M(x)). However, if the domain for x consists of all people, our statement can be expressed as “For every person x, if x is a student in this class, then x has visited Mexico or x has visited Canada.” In this case, the statement can be expressed as ∀x(S(x) → (C(x) ∨ M(x))). Instead of using M(x) and C(x) to represent that x has visited Mexico and x has visited Canada, respectively, we could use a two-place predicate V(x, y) to represent “x has visited country y.” In this case, V(x, Mexico) and V(x, Canada) would have the same meaning as M(x) and C(x) and could replace them in our answers. If we are working with many state- ments that involve people visiting different countries, we might prefer to use this two-variable approach. Otherwise, for simplicity, we would stick with the one-variable predicates M(x) and C(x). ◂ 1.4.11 Using Quantifiers in System Specifications In Section 1.2 we used propositions to represent system specifications. However, many system specifications involve predicates and quantifications. This is illustrated in Example 25. EXAMPLE 25 Use predicates and quantifiers to express the system specifications “Every mail message larger than one megabyte will be compressed” and “If a user is active, at least one network link will Extra be available.” Examples Solution: Let S(m, y) be “Mail message m is larger than y megabytes,” where the variable x has the domain of all mail messages and the variable y is a positive real number, and let C(m) denote “Mail message m will be compressed.” Then the specification “Every mail message larger than one megabyte will be compressed” can be represented as ∀m(S(m, 1) → C(m)). Remember the rules of precedence for Let A(u) represent “User u is active,” where the variable u has the domain of all users, quantifiers and logical let S(n, x) denote “Network link n is in state x,” where n has the domain of all network connectives! links and x has the domain of all possible states for a network link. Then the specifica- tion “If a user is active, at least one network link will be available” can be represented by ∃uA(u) → ∃nS(n, available). ◂ 54 1 / The Foundations: Logic and Proofs 1.4.12 Examples from Lewis Carroll Lewis Carroll (really C. L. Dodgson writing under a pseudonym), the author of Alice in Wonder- land, is also the author of several works on symbolic logic. His books contain many examples of reasoning using quantifiers. Examples 26 and 27 come from his book Symbolic Logic; other examples from that book are given in the exercises at the end of this section. These examples illustrate how quantifiers are used to express various types of statements. EXAMPLE 26 Consider these statements. The first two are called premises and the third is called the conclu- sion. The entire set is called an argument. “All lions are fierce.” “Some lions do not drink coffee.” “Some fierce creatures do not drink coffee.” (In Section 1.6 we will discuss the issue of determining whether the conclusion is a valid con- sequence of the premises. In this example, it is.) Let P(x), Q(x), and R(x) be the statements “x is a lion,” “x is fierce,” and “x drinks coffee,” respectively. Assuming that the domain consists of all creatures, express the statements in the argument using quantifiers and P(x), Q(x), and R(x). Solution: We can express these statements as ∀x(P(x) → Q(x)). ∃x(P(x) ∧ ¬R(x)). ∃x(Q(x) ∧ ¬R(x)). Notice that the second statement cannot be written as ∃x(P(x) → ¬R(x)). The reason is that P(x) → ¬R(x) is true whenever x is not a lion, so that ∃x(P(x) → ¬R(x)) is true as long as there is at least one creature that is not a lion, even if every lion drinks coffee. Similarly, the third statement cannot be written as ∃x(Q(x) → ¬R(x)). ◂ EXAMPLE 27 Consider these statements, of which the first three are premises and the fourth is a valid con- clusion. “All hummingbirds are richly colored.” “No large birds live on honey.” “Birds that do not live on honey are dull in color.” “Hummingbirds are small.” Links CHARLES LUTWIDGE DODGSON (1832–1898) We know Charles Dodgson as Lewis Carroll—the pseudonym he used in his literary works. Dodgson, the son of a clergyman, was the third of 11 children, all of whom stuttered. He was uncomfortable in the company of adults and is said to have spoken without stuttering only to young girls, many of whom he entertained, corresponded with, and photographed (sometimes in poses that today would be considered inappropriate). Although attracted to young girls, he was extremely puritan- ical and religious. His friendship with the three young daughters of Dean Liddell led to his writing Alice in Wonderland, which brought him money and fame. Dodgson graduated from Oxford in 1854 and obtained his master of arts degree in 1857. He was appointed Oscar c Gustav lecturer in mathematics at Christ Church College, Oxford, in 1855. He was ordained in the Church of England Rejlander/Hulton in 1861 but never practiced his ministry. His writings published under this real name include articles and books Archive/Getty Images on geometry, determinants, and the mathematics of tournaments and elections. (He also used the pseudonym Lewis Carroll for his many works on recreational logic.)  1.4 Predicates and Quantifiers 55 Let P(x), Q(x), R(x), and S(x) be the statements “x is a hummingbird,” “x is large,” “x lives on honey,” and “x is richly colored,” respectively. Assuming that the domain consists of all birds, express the statements in the argument using quantifiers and P(x), Q(x), R(x), and S(x). Solution: We can express the statements in the argument as ∀x(P(x) → S(x)). ¬∃x(Q(x) ∧ R(x)). ∀x(¬R(x) → ¬S(x)). ∀x(P(x) → ¬Q(x)). (Note we have assumed that “small” is the same as “not large” and that “dull in color” is the same as “not richly colored.” To show that the fourth statement is a valid conclusion of the first three, we need to use rules of inference that will be discussed in Section 1.6.) ◂ 1.4.13 Logic Programming An important type of programming language is designed to reason using the rules of predicate logic. Prolog (from Programming in Logic), developed in the 1970s by computer scientists working in the area of artificial intelligence, is an example of such a language. Prolog programs Links include a set of declarations consisting of two types of statements, Prolog facts and Prolog rules. Prolog facts define predicates by specifying the elements that satisfy these predicates. Prolog rules are used to define new predicates using those already defined by Prolog facts. Example 28 illustrates these notions. EXAMPLE 28 Consider a Prolog program given facts telling it the instructor of each class and in which classes students are enrolled. The program uses these facts to answer queries concerning the professors who teach particular students. Such a program could use the predicates instruc- tor(p, c) and enrolled(s, c) to represent that professor p is the instructor of course c and that student s is enrolled in course c, respectively. For example, the Prolog facts in such a program might include: instructor(chan,math273) instructor(patel,ee222) instructor(grossman,cs3