TEST BANK FOR Discrete Mathematics And Its Applications 7th Edition By Kenneth H. Rosen And Jerrold W. Grossman

Exam (elaborations) TEST BANK FOR Discrete Mathematics and Its Applications 7th Edition By Kenneth H. Rosen and Jerrold W. Grossman (Student’s Solutions Guide) Student's Solutions Guide to accompany Discrete Mathematics and Its Applications Seventh Edition Kenneth H. Rosen Monmouth University (and formerly AT&T Laboratories) Prepared by Jerrold W. Grossman Oakland University ~~onnect Learn • Succeed" Contents Preface CHAPTER 1 The Foundations: Logic and Proofs 1.1 Propositional Logic 1 1.2 Applications of Propositional Logic 8 1.3 Propositional Equivalences 11 1.4 Predicates and Quantifiers 1 7 1.5 Nested Quantifiers 23 1.6 Rules of Inference 32 1. 7 Introduction to Proofs 36 1.8 Proof Methods and Strategy 40 Guide to Review Questions for Chapter 1 44 Supplementary Exercises for Chapter 1 45 Writing Projects for Chapter 1 48 CHAPTER 2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices 2.1 Sets 50 2.2 Set Operations 53 2 .3 Functions 59 2.4 Sequences and Summations 68 2.5 Cardinality of Sets 75 2.6 Matrices 79 Guide to Review Questions for Chapter 2 83 Supplementary Exercises for Chapter 2 84 Writing Projects for Chapter 2 87 CHAPTER 3 Algorithms 3.1 Algorithms 88 3.2 The Growth of Functions 97 3.3 Complexity of Algorithms 103 Guide to Review Questions for Chapter 3 Supplementary Exercises for Chapter 3 Writing Projects for Chapter CHAPTER 4 Number Theory and Cryptography 4.1 Divisibility and Modular Arithmetic 113 4.2 Integer Representations and Algorithms 116 4.3 Primes and Greatest Common Divisors 122 4.4 Solving Congruences 130 4.5 Applications of Congruences 137 4.6 Cryptography 140 Guide to Review Questions for Chapter 4 142 Supplementary Exercises for Chapter 4 143 Writing Projects for Chapter 4 147 v iii CHAPTER 5 Induction and Recursion 5.1 Mathematical Induction 149 5.2 Strong Induction and Well-Ordering 161 5.3 Recursive Definitions and Structural Induction 5.4 Recursive Algorithms 176 5.5 Program Correctness 182 Guide to Review Questions for Chapter 5 Supplementary Exercises for Chapter 5 Writing Projects for Chapter 5 195 CHAPTER 6 Counting 6.1 The Basics of Counting 197 6.2 The Pigeonhole Principle 206 6.3 Permutations and Combinations 6.4 Binomial Coefficients and Identities 6.5 Generalized Permutations and Combinations 220 6.6 Generating Permutations and Combinations 227 Guide to Review Questions for Chapter 6 230 Supplementary Exercises for Chapter 6 231 Writing Projects for Chapter 6 237 CHAPTER 7 Discrete Probability 7.1 An Introduction to Discrete Probability 239 7.2 Probability Theory 242 7.3 Bayes' Theorem 247 7.4 Expected Value and Variance 250 Guide to Review Questions for Chapter 7 255 Supplementary Exercises for Chapter 7 256 Writing Projects for Chapter 7 261 CHAPTER 8 Advanced Counting Techniques 8.1 Applications of Recurrence Relations 262 8.2 Solving Linear Recurrence Relations 272 8.3 Divide-and-Conquer Algorithms and Recurrence Relations 8.4 Generating Functions 286 8.5 Inclusion-Exclusion 298 8.6 Applications of Inclusion-Exclusion Guide to Review Questions for Chapter 8 Supplementary Exercises for Chapter 8 Writing Projects for Chapter 8 310 CHAPTER 9 Relations .1 Relations and Their Properties 312 9.2 n-ary Relations and Their Applications 9.3 Representing Relations 322 9.4 Closures of Relations 325 Vl 282 312 9.5 Equivalence Relations 329 9.6 Partial Orderings 337 Guide to Review Questions for Chapter 9 Supplementary Exercises for Chapter 9 Writing Projects for Chapter 9 351 CHAPTER 10 Graphs 10.1 Graphs and Graph Models .2 Graph Terminology and Special Types of Graphs 355 10.3 Representing Graphs and Graph Isomorphism 361 10.4 Connectivity 368 10.5 Euler and Hamilton Paths 375 10.6 Shortest-Path Problems 381 10.7 Planar Graphs 385 10.8 Graph Coloring 389 Guide to Review Questions for Chapter 10 393 Supplementary Exercises for Chapter 10 395 Writing Projects for Chapter 10 401 CHAPTER 11 Trees 11.1 Introduction to Trees 403 11.2 Applications of Trees 408 11.3 Tree Traversal 417 11.4 Spanning Trees 421 11.5 Minimum Spanning Trees 427 Guide to Review Questions for Chapter 11 Supplementary Exercises for Chapter 11 Writing Projects for Chapter 11 434 CHAPTER 12 Boolean Algebra 12.1 Boolean Functions .2 Representing Boolean Functions 440 12.3 Logic Gates 443 12.4 Minimization of Circuits 445 Guide to Review Questions for Chapter 12 453 Supplementary Exercises for Chapter 12 454 Writing Projects for Chapter 12 456 CHAPTER 13 Modeling Computation 13.1 Languages and Grammars 457 13.2 Finite-State Machines with Output 13.3 Finite-State Machines with No Output .4 Language Recognition 474 13.5 Turing Machines 478 Guide to Review Questions for Chapter 13 Supplementary Exercises for Chapter 13 Writing Projects for Chapter 13 487 Vll 457 APPENDIXES Appendix 1 Axioms for the Real Numbers and the Positive Integers 489 Appendix 2 Appendix 3 Exponential and Logarithmic Functions Pseudocode 491 A Guide to Proof-Writing References and Advice on Writing Projects Sample Chapter Tests with Solutions Common Mistakes in Discrete Mathematics Solving Problems in Discrete Mathematics List of Common Mistakes 541 Crib Sheets Vlll Section 1.1 Propositional Logic 1 CHAPTERl The Foundations: Logic and Proofs SECTION 1.1 Propositional Logic Manipulating propositions and constructing truth tables are straightforward. A truth table is constructed by finding the truth values of compound propositions from the inside out; see the solution to Exercise 31, for instance. This exercise set also introduces fuzzy logic. 1. Propositions must have clearly defined truth values, so a proposition must be a declarative sentence with no free variables. a) This is a true proposition. b) This is a false proposition (Tallahassee is the capital). c) This is a true proposition. d) This is a false proposition. e) This is not a proposition (it contains a variable; the truth value depends on the value assigned to x). f) This is not a proposition, since it does not assert anything. 3. a) Mei does not have an MP3 player. b) There is pollution in New Jersey. c) 2+1#3 d) It is not the case that the summer in Maine is hot and sunny. In other words, the summer in Maine is not hot and sunny, which means that it is not hot or it is not sunny. It is not correct to negate this by saying "The summer in Maine is not hot and not sunny." [For this part (and in a similar vein for part (b)) we need to assume that there are well-defined notions of hot and sunny; otherwise this would not be a proposition because of not having a definite truth value.] 5. a) Steve does not have more than 100 GB free disk space on his laptop. (Alternatively: Steve has less than or equal to 100 GB free disk space on his laptop.) b) Zach does not block e-mails and texts from Jennifer. (Alternatively, and more precisely: Zach does not block e-mails from Jennifer, or he does not block texts from Jennifer. Note that negating an "and" statement produces an "or" statement. It would not be correct to say that Zach does not block e-mails from Jennifer, and he does not block texts from Jennifer. That is a stronger statement than just the negation of the given statement.) c) 7·11·13#999. d) Diane did not ride her bike 100 miles on Sunday. 7. a) This is false, because Acme's revenue was larger. b) Both parts of this conjunction are true, so the statement is true. c) The second part of this disjunction is true, so the statement is true. d) The hypothesis of this conditional statement is false and the conclusion is true, so by the truth-table definition this is a true statement. (Either of those conditions would have been enough to make the statement true.) 2 Chapter 1 The Foundations: Logic and Proofs e) Both parts of this biconditional statement are true, so by the truth-table definition this is a true statement. 9. This is pretty straightforward, using the normal words for the logical operators. a) Sharks have not been spotted near the shore. b) Swimming at the New Jersey shore is allowed, and sharks have been spotted near the shore. c) Swimming at the New Jersey shore is not allowed, or sharks have been spotted near the shore. d) If swimming at the New Jersey shore is allowed, then sharks have not been spotted near the shore. e) If sharks have not been spotted near the shore, then swimming at the New Jersey shore is allowed. f) If swimming at the New Jersey shore is not allowed, then sharks have not been spotted near the shore. g) Swimming at the New Jersey shore is allowed if and only if sharks have not been spotted near the shore. h) Swimming at the New Jersey shore is not allowed, and either swimming at the New Jersey shore is allowed or sharks have not been spotted near the shore. Note that we were able to incorporate the parentheses by using the word "either" in the second half of the sentence. 11. a) Here we have the conjunction p A q. b) Here we have a conjunction of p with the negation of q, namely p A --.q. Note that "but" logically means the same thing as "and." c) Again this is a conjunction: --.p A --.q. d) Here we have a disjunction, p V q. Note that V is the inclusive or, so the "(or both)" part of the English sentence is automatically included. e) This sentence is a conditional statement, p -> q. f) This is a conjunction of propositions, both of which are compound: (p V q) A (p-> --.q). g) This is the biconditional p f-+ q. 13. a) This is just the negation of p, so we write --.p. b) This is a conjunction ("but" means "and"): p A --.q. c) The position of the word "if" tells us which is the antecedent and which is the consequence: p -> q. d) -ip -t --.q e) The sufficient condition is the antecedent: p -> q. f)qA--.p g) ''Whenever" means "if": q -> p. 15. a) "But" is a logical synonym for "and" (although it often suggests that the second part of the sentence is likely to be unexpected). So this is r A --.p. b) Because of the agreement about precedence, we do not need parentheses in this expression: --.p A q A r. c) The outermost structure here is the conditional statement, and the conclusion part of the conditional statement is itself a biconditional: r -> ( q f-+ --.p) . d) This is similar to part (b): --.q A --.p A r. e) This one is a little tricky. The statement that the condition is necessary is a conditional statement in one direction, and the statement that this condition is not sufficient is the negation of the conditional statement in the other direction. Thus we have the structure (safe -> conditions) A--.( conditions -> safe). Fleshing this out gives our answer: ( q -> (--.r A --.p)) A --.( (--.r A --.p) -> q). There are some logically equivalent correct answers as well. f) We just need to remember that "whenever" means "if" in logic: (p A r) -> --.q. 17. In each case, we simply need to determine the truth value of the hypothesis and the conclusion, and then use Section 1.1 Propositional Logic 3 the definition of the truth value of the conditional statement. The conditional statement is true in every case except when the hypothesis (the "if" part) is true and the conclusion (the ''then" part) is false. a) Since the hypothesis is true and the conclusion is false, this conditional statement is false. b) Since the hypothesis is false and the conclusion is true, this conditional statement is true. c) Since the hypothesis is false and the conclusion is false, this conditional statement is true. Note that the conditional statement is false in both part (b) and part ( c); as long as the hypothesis is false, we need look no further to conclude that the conditional statement is true. d) Since the hypothesis is false, this conditional statement is true. 19. a) Presumably the diner gets to choose only one of these beverages, so this is an exclusive or. b) This is probably meant to be inclusive, so that long passwords with many digits are acceptable. c) This is surely meant to be inclusive. If a student has had both of the prerequisites, so much the better. d) At first glance one might argue that no one would pay with both currencies simultaneously, so it would seem reasonable to call this an exclusive or. There certainly could be cases, however, in which the patron would pay a portion of the bill in dollars and the remainder in euros. Therefore, an inclusive or seems better. 21. a) If this is an inclusive or, then it is allowable to take discrete mathematics if you have had calculus or computer science or both. If this is an exclusive or, then a person who had both courses would not be allowed to take discrete mathematics-only someone who had taken exactly one of the prerequisites would be allowed in. Clearly the former interpretation is intended; if anything, the person who has had both calculus and computer science is even better prepared for discrete mathematics. b) If this is an inclusive or, then you can take the rebate, or you can sign up for the low-interest loan, or you can demand both of these incentives. If this is an exclusive or, then you will receive one of the incentives but not both. Since both of these deals are expensive for the dealer or manufacturer, surely the exclusive or was intended. c) If this is an inclusive or, you can order two items from column A (and none from B), or three items from column B (and none from A), or five items (two from A and three from B). If this is an exclusive or, which it surely is here, then you get your choice of the two A items or the three B items, but not both. d) If this is an inclusive or, then lots of snow, or extreme cold, or a combination of the two will close school. If this is an exclusive or, then one form of bad weather would close school but if both of them happened then school would meet. This latter interpretation is clearly absurd, so the inclusive or is intended. 23. a) If the wind blows from the northeast, then it snows. ["Whenever" means ''if."] b) If it stays warm for a week, then the apple trees will bloom. [Sometimes word order is flexible in English, as it is here. Other times it is not-"The man bit the dog" does not have the same meaning as "The dog bit the man."] c) If the Pistons win the championship, then they beat the Lakers. d) If you get to the top of Long's Peak, then you must have walked eight miles. [The necessary condition is the conclusion.] e) If you are world famous, then you will get tenure as a professor. [The sufficient condition is the antecedent.] f) If you drive more than 400 miles, then you will need to buy gasoline. [The word ''then" is sometimes omitted in English sentences, but it is still understood.] g) If your guarantee is good, then you must have bought your CD player less than 90 days ago. [Note that "only if" does not mean "if"; the clause following the "only if" is the conclusion, not the antecedent.] h) If the water is not too cold, then Jan will go swimming. [Note that "unless" really means "if not." It also can be taken to mean "or."] 4 Chapter 1 The Foundations: Logic and Proofs 25. In each case there will be two statements. It is being asserted that the first one holds true if and only if the second one does. The order doesn't matter, but often one order is more colloquial English. a) You buy an ice cream cone if and only if it is hot outside. b) You win the contest if and only if you hold the only winning ticket. c) You get promoted if and only if you have connections. d) Your mind will decay if and only if you watch television. e) The train runs late if and only if it is a day I take the train. 27. Many forms of the answers for this exercise are possible. a) One form of the converse that reads well in English is "I will ski tomorrow only if it snows today." We could state the contrapositive as ''If I don't ski tomorrow, then it will not have snowed today." The inverse is "If it does not snow today, then I will not ski tomorrow." b) The proposition as stated can be rendered "If there is going to be a quiz, then I will come to class." The converse is "If I come to class, then there will be a quiz." (Or, perhaps even better, "I come to class only if there's going to be a quiz.") The contrapositive is "If I don't come to class, then there won't be a quiz." The inverse is "If there is not going to be a quiz, then I don't come to class.'' c) There is a variable ("a positive integer") in this sentence, so technically it is not a proposition. Nevertheless, we can treat sentences such as this in the same way we treat propositions. Its converse is "A positive integer is a prime if it has no divisors other than 1 and itself." (Note that this can be false, since the number 1 satisfies the hypothesis but not the conclusion.) The contrapositive of the original proposition is "If a positive integer has a divisor other than 1 and itself, then it is not prime." (We are simplifying a bit here, replacing ''does not have no divisors" by "has a divisor." Note that this is always true, assuming that we are talking about positive divisors.) The inverse is "If a positive integer is not prime, then it has a divisor other than 1 and itself." 29. A truth table will need 2n rows if there are n variables. a)21 =2 b)24 =16 c)26 =64 d)24 =16 31. To construct the truth table for a compound proposition, we work from the inside out. In each case, we will show the intermediate steps. In part ( d), for example, we first construct the truth table for p V q, then the truth table for p / q, and finally combine them to get the truth table for (p V q) -+ (p / q). For parts (a) and (b) we have the following table (column three for part (a), column four for part (b)). P 'P p/-ip pV-ip T F F T F T F T For part ( c) we have the following table. p q -iq p v -iq (p v -iq) -+ q T T F T T T F T T F F T F F T F F T T F For part ( d) we have the following table. p q pVq p / q (p v q) -+ (p / q) T T T T T T F T F F F T T F F F F F F T Section 1.1 Propositional Logic 5 For part ( e) we have the following table. This time we have omitted the column explicitly showing the negations of p and q. Note that this true proposition is telling us that a conditional statement and its contrapositive always have the same truth value. p q p-+ q •q -+ 'P (p-+ q) f--7 (•q -+ •p) T T T T T T F F F T F T T T T F F T T T For part ( f) we have the following table. The fact that this proposition is not always true tells us that knowing a conditional statement in one direction does not tell us that the conditional statement is true in the other direction. p q p --'> q q-+ p (p-+ q) -+ (q-+ p) T T T T T T F F T T F T T F F F F T T T 33. To construct the truth table for a compound proposition, we work from the inside out. In each case, we will show the intermediate steps. In part (a), for example, we first construct the truth table for p V q, then the truth table for p EB q, and finally combine them to get the truth table for (p V q) -+ (p EB q). For parts (a), (b), and ( c) we have the following table (column five for part (a), column seven for part (b), column eight for part ( c)). p q pVq pEB q (pV q) -+ (p EB q) p / q (p EB q) -+ (p / q) (pV q) EB (p/ q) T T T F F T T F T F T T T F F T F T T T T F F T F F F F T F T F For part ( d) we have the following table. p q 'P p f--7 q •P ,_. q (p ,_. q) EB ( •P ,_. q) --- T T F T F T T F F F T T F T T F T T F F T T F T For part ( e) we need eight rows in our truth table, because we have three variables. p q r 'P •r p f--7 q •P ,_. •r (p ,_. q) EB (•p ,_. •r) T T T F F T T F T T F F T T F T T F T F F F T T T F F F T F F F F T T T F F F F F T F T T F T T F F T T F T F T F F F T T T T F For part (f) we have the following table. p q •q p EB q p EB •q (p EB q) -+ (p EB •q) T T F F T T T F T T F F F T F T F F F F T F T T 6 Chapter 1 The Foundations: Logic and Proofs 35. The techniques are the same as in Exercises 31-34. For parts (a) and (b) we have the following table (column four for part (a), column six for part (b)). 37. p q •q p ---+ •q 'P -.p +-+ q T T F F F F T F T T F T F T F T T T F F T T T F For parts (c) and (d) we have the following table (columns six and seven, respectively). p q p ---+ q -.p 'P ---+ q (p---+ q) v ( •p---+ q) (p---+ q) / ( •p---+ q) T T T F T T T T F F F T T F F T T T T T T F F T T F T F For parts ( e) and ( f) we have the following table (this time we have not explicitly shown the columns for negation). Column five shows the answer for part (e), and column seven shows the answer for part (f). p q p +-+ q 'P +-+ q (p +-+ q) v (•p +-+ q) •P +-+ •q ( •p +-+ -.q) +-+ (p +-+ q) T T T F T T T T F F T T F T F T F T T F T F F T F T T T The techniques are the same as in Exercises 31-36, except that there are now three variables and therefore eight rows. For part (a), we have p q r •q •q Vr p ---+ ( •q V r) T T T F T T T T F F F F T F T T T T T F F T T T F T T F T T F T F F F T F F T T T T F F F T T T For part (b), we have p q r -.p q ---+ r -.p ---+ ( q ---+ r) T T T F T T T T F F F T T F T F T T T F F F T T F T T T T T F T F T F F F F T T T T F F F T T T Parts ( c) and ( d) we can combine into a single table. Section 1.1 Propositional Logic 7 p q r p ____, q •p 'P ____, r (p ____, q) V (•p ____, r) (p ____, q) A ( •p ____, r) T T T T F T T T T T F T F T T T T F T F F T T F T F F F F T T F F T T T T T T T F T F T T F T F F F T T T T T T F F F T T F T F For part ( e) we have p q r p <,--+ q •q •q ,,._, r (p ,,._, q) V ( •q ,,._, r) T T T T F F T T T F T F T T T F T F T T T T F F F T F F F T T F F F F F T F F F T T F F T T T T T F F F T T F T Finally, for part ( f) we have p q r •P •q •p <,--+ •q q ,,._, r ( •P ,,__, •q) ,,__, (q ,,__, r) T T T F F T T T T T F F F T F F T F T F T F F T T F F F T F T F F T T T F F T F F T F T F F F T F F T T T T F F F F F T T T T T 39. This time the truth table needs 24 = 16 rows. Note the systematic order in which we list the possibilities. p q r s p <,--+ q r ,,._, s (p ,,._, q) ,,._, ( r ,,._, s) T T T T T T T T T T F T F F T T F T T F F T T F F T T T T F T T F T F T F T F F F T T F F T F F T T F F F F T F F T T T F T F F T T F F F T F T F T F F T F T F F F T F F F T T T T T F F T F T F F F F F T T F F F F F F T T T 41. The first clause (p V q V r) is true if and only if at least one of p, q, and r is true. The second clause ( •p V •q V •r) is true if and only if at least one of the three variables is false. Therefore both clauses are true, and therefore the entire statement is true, if and only if there is at least one T and one F among the truth values of the variables, in other words, that they don't all have the same truth value. 8 Chapter 1 The Foundations: Logic and Proofs 43. a) bitwise OR = 111 1111; bitwise AND= 000 0000; bitwise XOR = b) bitwise OR = ; bitwise AND= ; bitwise XOR = c) bitwise OR= 10 ; bitwise AND= ; bitwise XOR= 10 d) bitwise OR= 1; bitwise AND= ; bitwise XOR= 1 45. For "Fred is not happy," the truth value is 1 - 0.8 = 0.2. For "John is not happy,'' the truth value is 1- 0.4 = 0.6. 47. For "Fred is happy, or John is happy,'' the truth value is max(0.8, 0.4) = 0.8. For ''Fred is not happy, or John is not happy," the truth value is max(0.2, 0.6) = 0.6 (using the result of Exercise 45). 49. One great problem-solving strategy to try with problems like this, when the parameter is large ( 100 statements here) is to lower the parameter. Look at a simpler problem, with just two or three statements, and see if you can figure out what's going on. That was the approach used to discover the solution presented here. a) Some number of these statements are true, so in fact exactly one of the statements must be true and the other 99 of them must be false. That is what the 99th statement is saying, so it is true and the rest are false. b) The 10oth statement cannot be true, since it is asserting that all the statements are false. Therefore it must be false. That makes the first statement true. Now if the 99th statement were true, then we would conclude that statements 2 through 100 were false, which contradicts the truth of statement 99. So statement 99 must be false. That means that statement 2 is true. We continue in this way and conclude that statements 1 through 50 are all true and statements 51 through 100 are all false. c) If there are an odd number of statements, then we'd run into a contradiction when we got to the middle. If there were just three statements, for example, then statement 3 would have to be false, making statement 1 true, and now the truth of statement 2 would imply its falsity and its falsity would imply its truth. Therefore this situation cannot occur with three (or any odd number of) statements. It is a logical paradox, showing that in fact these are not statements after all. SECTION 1.2 Applications of Propositional Logic Applications of propositional logic abound in computer science, puzzles, and everyday life. For example, much of the operation of our legal system is based on conditional statements. Boolean searches are increasingly important in using the Web (see Exercises 13-14 for example). 1. Recall that '' q unless •p" is another way to state p _, q. In this problem, •P is a, so p is •a; and q is •e. Therefore the statement here is •a _, •e. This could also be stated equivalently as e _, a (if you can edit, then you must be an administrator). 3. Recall that p only if q means p _, q. In this case, if you can graduate then you must have fulfilled the three listed requirements. Therefore the statement is g _, (r / (•m) / (•b)). Notice that in everyday life one might actually say "You can graduate if you do these things," but logically that is not what the rules really say. 5. This is similar to Exercise 3. If you are eligible to be President, then you must satisfy the requirements: e _, (a/ (b V p) / r). Notice that it is only the requirement of being native-born that can be overridden by having parents who were citizens, so b V p is grouped as one of the three conditions. Section 1.2 Applications of Propositional Logic 9 7. a) Since "whenever" means "if," we have q---+ p. b) Since "but" means "and," we have q / 'P. c) This sentence is saying the same thing as the sentence in part (a), so the answer is the same: q---+ p. d) Again, we recall that "when" means "if" in logic: •q---+ •p. 9. Let m, n, k, and i represent the propositions ''The system is in multiuser state," "The system is operating normally," "The kernel is functioning,'' and "The system is in interrupt mode," respectively. Then we want to make the following expressions simultaneously true by our choice of truth values for m, n, k, and i: m ,,_.. n, n ---+ k, -,kV i, -im ---+ i, -,i In order for this to happen, clearly i must be false. In order for •m ---+ i to be true when i is false, the hypothesis •m must be false, so m must be true. Since we want m ,,_.. n to be true, this implies that n must also be true. Since we want n ---+ k to be true, we must therefore have k true. But now if k is true and i is false, then the third specification, •kV i is false. Therefore we conclude that this system is not consistent. 11. Let s be "The router can send packets to the edge system"; let a be "The router supports the new address space"; let r be "The latest software release is installed." Then we are told s ---+ a, a ---+ r, r ---+ s, and •a. Since a is false, the first conditional statement tells us that s must be false. From that we deduce from the third conditional statement that r must be false. If indeed all three propositions are false, then all four specifications are true, so they are consistent. 13. This is similar to Example 6, about universities in New Mexico. To search for beaches in New Jersey. we could enter NEW AND JERSEY AND BEACHES. If we enter (JERSEY AND BEACHES) NOT NEW, then we'll get websites about beaches on the isle of Jersey, except for sites that happen to use the word "new" in a different context (e.g., a recently opened beach there). If we were sure that the word "isle" was in the name of the location, then of course we could enter ISLE AND JERSEY AND BEACHES. 15. There are many correct answers to this problem, but all involve some sort of double layering, or combining a question about the kind of person being addressed with a question about the information being sought. One solution is to ask this question: "If I were to ask you whether the right branch leads to the ruins, would you say 'yes'?" If the villager is a truth-teller, then of course he will reply "yes" if and only if the right branch leads to the ruins. Now let us see what the liar says. If the right branch leads to the ruins, then he would say "no" if asked whether the right branch leads to the ruins. Therefore, the truthful answer to your convoluted question is "no." Since he always lies, he will reply "yes." On the other hand, if the right branch does not lead to the ruins, then he would say "yes'' if asked whether the right branch leads to the ruins; and so the truthful answer to your question is "yes"; therefore he will reply "no." Note that in both cases, he gives the same answer to your question as the truth-teller; namely, he says "yes" if and only if the right branch leads to the ruins. A more detailed discussion can be found in Martin Gardner's Scientific American Book of Mathematical Puzzles and Diversions (Simon and Schuster, 1959), p. 25; reprinted as Hexafiexagons and Other Mathematical Diversions: The First Scientific American Book of Puzzles and Games (University of Chicago Press, 1988). 17. The question was "Does everyone want coffee?" If the first professor did not want coffee, then he would know that the answer to the hostess's question was "no." Therefore we-and the hostess and the remaining professors-know that the first professor does want coffee. The same argument applies to the second professor, so she, too, must want coffee. The third professor can now answer the question. Because she said "no,'' we conclude that she does not want coffee. Therefore the hostess knows to bring coffee to the first two professors but not to the third. 10 Chapter 1 The Foundations: Logic and Proofs 19. If A is a knight, then he is telling the truth, in which case B must be a knave. Since B said nothing, that is certainly possible. If A is a knave, then he is lying, which means that his statement that at least one of them is a knave is false; hence they are both knights. That is a contradiction. So we can conclude that A is a knight and B is a knave. 21. If A is a knight, then he is telling the truth, in which case B must be a knight as well, since A is not a knave. (If p V q and •p are both true, then q must be true.) Since B said nothing, that is certainly possible. If A is a knave, then his statement is patently true, but that is a contradiction to the behavior of knaves. So we can conclude that A is a knight and B is a knight. 23. If A is a knight, then he should be telling the truth, but he is asserting that he is a knave. So that cannot be. If A is a knave, then in order for his statement to be false, B must be a knight. So we can conclude that A is a knave and B is a knight. 25. Neither the knight nor the knave would say that he is the knave, so B must be the spy. Therefore C is lying and must be the knave, and A is therefore the knight (and told the truth). 27. We know that B is not the knight, because if he were, then his assertion that A is telling the truth would mean that there were two knights. Clearly C is not the knight, because he claims he is the spy. Therefore A is the knight. That means that B was telling the truth, so he must be the spy. And C is the knave, who falsely asserts that he is the spy. 29. We can tell nothing here; each of the six permutations is possible. The knight will always say that he is the knight; the knave will always lie, so he might also say that he is the knight; and the spy may lie and say that he is the knight. 31. If there were a solution, then whoever is the knave here is speaking the truth when he says that he is not the spy. Because knaves always lie, we get a contradiction. Therefore there are no solutions. 33. Because of the first piece of information that Steve has, let's assume first that Fred is not the highest paid. Then Janice is. Therefore Janice is not the lowest paid, so by the second piece of information that Steve has, Maggie is the highest paid. But that is a contradiction. Therefore we know that Fred is the highest paid. Next let's assume that Janice is not the lowest paid. Then our second fact implies that Maggie is the highest paid. But that contradicts the fact that Fred is the highest paid. Therefore we know that Janice is the lowest paid. So it appears that the only hope of a consistent set of facts is to have Fred paid the most, Maggie next, and Janice the least. (We have just seen that any other assumption leads to a contradiction.) This assumption does not contradict either of our two facts, since in both cases, the hypothesis is false. 35. Let's use the letters B, C, G, and H for the statements that the butler, cook, gardner, and handyman are telling the truth, respectively. We can then write each fact as a true proposition: B -+ C; •(CA G), which is equivalent to ·CV --,Q (see the discussion of De Morgan's law in Section 1.3); •( •G A ·H), which is equivalent to G V H; and H -+ ·C. Suppose that B is true. Then it follows from the first of our propositions that C must also be true. This tells us (using the second proposition) that G must be false, whence the third proposition makes H true. But now the fourth proposition is violated. Therefore we conclude that B cannot be true. If fact, the argument we have just given also proves that C cannot be true. Therefore we know that the butler and the cook are lying. This much already makes the first, second, and fourth propositions true, regardless of the truth of G or H. Thus either the gardner or the handyman could be lying or telling the truth; all we know (from the third proposition) is that at least one of them is telling the truth. Section 1.3 Propositional Equivalences 11 37. If the first sign were true, then the second sign would also be true. In that case, we could not have one true sign and one false sign. Rather, the second sign is true and the first is false; there is a lady in the second room and a tiger in the first room. 39. The given conditions imply that there cannot be two honest senators. Therefore, since we are told that there is at least one honest senator, there must be exactly 49 corrupt senators. 41. a) The output of the OR gate is q V •r. Therefore the output of the AND gate is p / ( q V •r). Therefore the output of this circuit is •(P / ( q V •r)). b) The output of the top AND gate is ( •p) / ( •q). The output of the bottom AND gate is p / r. Therefore the output of this circuit is ( ( •p) / ( •q)) V (p / r). 43. We have the inputs come in from the left, in some cases passing through an inverter to form their negations. Certain pairs of them enter OR gates, and the outputs of these and other negated inputs enter AND gates. The outputs of these AND gates enter the final OR gate. SECTION 1.3 Propositional Equivalences 1. The solutions to Exercises 1-10 are routine; we use truth tables to show that a proposition is a tautology or that two propositions are equivalent. The reader should do more than this, however; think about what the equivalence is saying. See Exercise 11 for this approach. Some important topics not covered in the text are introduced in this exercise set, including the notion of the dual of a proposition, disjunctive normal form for propositions, functional completeness, satisfiability, and two other logical connectives, NAND and NOR. Much of this material foreshadows the study of Boolean algebra in Chapter 12. First we construct the following truth tables, for the propositions we are asked to deal with. p p/ T pVF pt F pVT pVp p / p T T T F T T T F F F F T F F The first equivalence, p / T = p, is valid because the second column p / T is identical to the first column p. Similarly, part (b) comes from looking at columns three and one. Since column four is a column of F's, and column five is a column of T's, part ( c) and part ( d) hold. Finally, the last two parts follow from the fact that the last two columns are identical to the first column. 12 Chapter 1 The Foundations: Logic and Proofs 3. We construct the following truth tables. p q pVq qVp p/ q q /p T T T T T T T F T T F F F T T T F F F F F F F F Part (a) follows from the fact that the third and fourth columns are identical; part (b) follows from the fact that the fifth and sixth columns are identical. 5. We construct the following truth table and note that the fifth and eighth columns are identical. p q r qVr p/(qVr) p / q p / r (p/q) V (p/r) T T T T T T T T T T F T T T F T T F T T T F T T T F F F F F F F F T T T F F F F F T F T F F F F F F T T F F F F F F F F F F F F 7. De Morgan's laws tell us that to negate a conjunction we form the disjunction of the negations, and to negate a disjunction we form the conjunction of the negations. a) This is the conjunction "Jan is rich, and Jan is happy." So the negation is "Jan is not rich, or Jan is not happy." b) This is the disjunction '"Carlos will bicycle tomorrow, or Carlos will run tomorrow." So the negation is ''Carlos will not bicycle tomorrow, and Carlos will not run tomorrow." We could also render this as ''Carlos will neither bicycle nor run tomorrow.'' c) This is the disjunction ''Mei walks to class, or Mei takes the bus to class." So the negation is ''Mei does not walk to class, and Mei does not take the bus to class." (Maybe she gets a ride with a friend.) We could also render this as ''Mei neither walks nor takes the bus to class." d) This is the conjunction ''Ibrahim is smart, and Ibrahim is hard working." So the negation is "Ibrahim is not smart, or Ibrahim is not hard working.'' 9. We construct a truth table for each conditional statement and note that the relevant column contains only T's. For parts (a) and (b) we have the following table (column four for part (a), column six for part (b)). E____!l_ p / q (p / q) --+ p p v q p --+ (p v q) T T T T T T T F F T T T F T F T T T F F F T F T For parts ( c) and ( d) we have the following table (columns five and seven, respectively). P q 'P P-+ q 'P -+ (p-+ q) P / q (p / q) -+ (p--+ q) TT F T T T T TF F F T F T F T F F T T T T T T F F T T For parts (e) and (f) we have the following table. Column five shows the answer for part (e), and column seven shows the answer for part ( f). Section 1.3 Propositional Equivalences 13 p q p ---'> q •(p ---'> q) •(p ---'> q) ---'> p •q •(p ---'> q) ---'> -,q T T T F T F T T F F T T T T F T T F T F T F F T F T T T 11. Here is one approach: Recall that the only way a conditional statement can be false is for the hypothesis to be true and the conclusion to be false; hence it is sufficient to show that the conclusion must be true whenever the hypothesis is true. An alternative approach that works for some of these tautologies is to use the equivalences given in this section and prove these "algebraically." We will demonstrate this second method in some of the solutions. a) If the hypothesis is true, then by the definition of / we know that p is true. Hence the conclusion is also true. For an algebraic proof, we exhibit the following string of equivalences, each one following from one of the laws in this section: (p / q) ---+ p = -, (p / q) V p = ( •p V •q) V p = ( •q V •p) V p = •q V ( •P V p) = •q V T = T. The first logical equivalence is the first equivalence in Table 7 (with p / q playing the role of p, and p playing the role of q ); the second is De Morgan's law; the third is the commutative law; the fourth is the associative law; the fifth is the negation law (with the commutative law); and the sixth is the domination law. b) If the hypothesis p is true, then by the definition of V, the conclusion p V q must also be true. c) If the hypothesis is true, then p must be false; hence the conclusion p ---+ q is true, since its hypothesis is false. Symbolicallays means "some" (existential quantifier), as in the statement "You will be suspended from school if you are found guilty of violating any of the plagiarism rules" (you don't have to violate all the rules to get into trouble-breaking one is sufficient). In positive contexts, however, it can mean either "some" (existential quantifier) or "every" (universal quantifier), depending on context. For example, in the sentence "The fraternity will be put on probation if any of its members is found intoxicated," the use is existential (one drunk brother is enough to cause the sanction); but in the sentence "Any member of the sorority will be happy to lead you on a tour of the house," the use is universal (every member is able to be the guide). Another interesting example is an exercise in a mathematics textbook that asks you to show that "the sum of any two odd numbers is even." The author clearly intends the universal interpretation here-you need to show that the sum of two odd numbers is always even. If you interpreted the question existentially, you might say, "Look, 3 + 5 = 8, so I've shown it is true--you said I could do it for any numbers, and those are the ones I chose.'' 1. a) T, since 0 :::; 4 b) T, since 4 :::; 4 c) F, since 6 i 4 3. a) This is true. b) This is false, since Lansing, not Detroit, is the capital. c) This is false (but Q(Boston, Massachusetts) is true). d) This is false, since Albany, not New York, is the capital. 5. a) There is a student who spends more than five hours every weekday in class. b) Every student spends more than five hours every weekday in class. c) There is a student who does not spend more than five hours every weekday in class. d) No student spends more than five hours every weekday in class. (Or, equivalently, every student spends less than or equal to five hours every weekday in class.) 7. a) This statement is that for every x, if x is a comedian, then x is funny. In English, this is most simply stated, "Every comedian is funny." b) This statement is that for every x in the domain (universe of discourse), x is a comedian and x is funny. In English, this is most simply stated, "Every person is a funny comedian." Note that this is not the sort of thing one wants to say. It really makes no sense and doesn't say anything about the existence of boring comedians; it's surely false, because there exist lots of x for which C(x) is false. This illustrates the fact that you rarely want to use conjunctions with universal quantifiers. c) This statement is that there exists an x in the domain such that if x is a comedian then x is funny. In English, this might be rendered, "There exists a person such that ifs/he is a comedian, then s/he is funny." Note that this is not the sort of thing one wants to say. It really makes no sense and doesn't say anything about the existence of funny comedians; it's surely true, because tbere exist lots of x for which C(x) is false (recall 18 Chapter 1 The Foundations: Logic and Proofs the definition of the truth value of p -+ q). This illustrates the fact that you rarely want to use conditional statements with existential quantifiers. d) This statement is that there exists an x in the domain such that x is a comedian and x is funny. In English, this might be rendered, ''There exists a funny comedian" or "Some comedians are funny" or "Some funny people are comedians." 9. a) We assume that this sentence is asserting that the same person has both talents. Therefore we can write 3x(P(x) / Q(x)). b) Since "but" really means the same thing as "and" logically, this is 3x(P(x) / •Q(x)) c) This time we are making a universal statement: Vx(P(x) V Q(x)) d) This sentence is asserting the nonexistence of anyone with either talent, so we could write it as -,::Jx(P(x) V Q(x)). Alternatively, we can think of this as asserting that everyone fails to have either of these talents, and we obtain the logically equivalent answer 'v'x•(P(x) V Q(x)). Failing to have either talent is equivalent to having neither talent (by De Morgan's law), so we can also write this as Vx((•P(x)) / (•Q(x)). Note that it would not be correct to write Vx((•P(x)) V (•Q(x)) nor to write 'v'x•(P(x) / Q(x)). 11. a) T, since 0 = 02 b) T, since 1 = 1 2 d) F, since -1-=/:- (-1) 2 e) T (let x = 1) c) F, since 2 f 22 f) F (let x = 2 ) 13. a) Since adding 1 to a number makes it larger, this is true. b) Since 2 · 0 = 3 · 0, this is true. c) This statement is true, since 0 = -0. d) This is true for the nonnegative integers but not for the negative integers. For example, 3(-2) 'f:_ 4(-2). Therefore the universally quantified statement is false. 15. Recall that the integers include the positive and negative integers and 0. a) This is the well-known true fact that the square of a real number cannot be negative. b) There are two real numbers that satisfy n2 = 2, namely ±J2, but there do not exist any integers with this property, so the statement is false. c) If n is a positive integer, then n2 ;:::: n is certainly true; it's also true for n = 0; and it's trivially true if n is negative. Therefore the universally quantified statement is true. d) Squares can never be negative; therefore this statement is false. 17. Existential quantifiers are like disjunctions, and universal quantifiers are like conjunctions. See Examples 11 and 16. a) We want to assert that P(x) is true for some x in the universe, so either P(O) is true or P(l) is true or P(2) is true or P(3) is true or P(4) is true. Thus the answer is P(O) V P(l) V P(2) V P(3) V P(4). The other parts of this exercise are similar. Note that by De Morgan's laws, the expression in part (c) is logically equivalent to the expression in part (f), and the expression in part (d) is logically equivalent to the expression in part (e). b) P(O) / P(l) / P(2) / P(3) / P(4) c) •P(O) V ·P(l) V ·P(2) V ·P(3) V ·P(4) d) ·P(O) / ·P(l) / ·P(2) / ·P(3) / ·P(4) e) This is just the negation of part (a): •(P(O) V P(l) V P(2) V P(3) V P(4)) f) This is just the negation of part (b): •(P(O) / P(l) / P(2) / P(3) / P(4)) Section 1.4 Predicates and Quantifiers 19 19. Existential quantifiers are like disjunctions, and universal quantifiers are like conjunctions. See Examples 11 and 16. a) We want to assert that P(x) is true for some x in the universe, so either P(l) is true or P(2) is true or P(3) is true or P(4) is true or P(5) is true. Thus the answer is P(l) V P(2) V P(3) V P(4) V