P.161.14.f) If I did not buy a lottery ticket this week, then I did not win the million dollar jackpot on Friday.g) I did not buy a lottery ticket this week, and I did not win the million dollar jackpot on Friday.h ) Either I did not buy a lottery ticket this week, or else I did buy one and won the million dollar jackpot on Friday.10.a) r ∧┐q b) p ∧ q∧ r c)r → pd) p ∧┐q ∧ r e) (p ∧q) → r f) r↔ ( q ∨ p)20.a) If I am to remember to send you the address, then you will have to send me ane-mail message.(This has been slightly reworded so that the tenses make more sense.)b) If you were born in the United States, then you are a citizen of this country.c) If you keep your textbook, then it will be a useful reference in your future courses.(The word "then" is understood in English, even if omitted.)d) If their goaltender plays well, then the Red Wings will win the Stanley Cup.e) If you get the job, then you had the best credentials.f) If there is a storm, then the beach erodes.g) If you log on to the server, then you have a valid password.h) If you don’t begin your climb too late, then you will reach the summit.33.c)P.261.28.a) Kwame will not take a job in industry and he will not go to graduate school.b) Yoshiko doesn’t know Java or she doesn’t know calculus.c) James is not young or he is not strong.d) Rita will not move to Oregon and she will not move to Washington.10.a)c)12.a) Assume the hypothesis is true. Then p is false. Since p∨q is true, we conclude that q must be true.Here is a more "algebraic" solution:[┐p∧(p ∨q)]→q <=> ┐[┐p∧(p ∨q)]∨q <=> ┐┐p∨┐(p∨q)∨q <=> p∨┐(p∨q)∨q <=> (p ∨q)∨┐(p∨q) <=> Tc) Assume the hypothesis is true. Then p is true, and since the second part of the hypothesis is ture, we conclude that q is also true, as desired.51.((p ↓ p) ↓ q )↓((p ↓ p) ↓ q )7.The graph is planar.20.The graph is not homeomorphic to K3,3, since by rerouting the edge between a and h we seethat it is planar.22.Replace each vertex of degree two and its incident edges by a single edge. Then the result isK3,3 : the parts are {a,e,i} and {c,g,k}. Therefore this graph is homeomorphic to K3,3.23.The graph is planar.25. The graph is not planar.9.83. 3F E8. 310.417. time slot 1: Math 115, Math 185; time slot 2: Math 116, CS 473;time slot 3: Math 195, CS 101; time slot 4: CS 102time slot 5: CS 273P.461.33. a) true b) false c) false d) false5. a) There is a student who spends more than 5 hours every weekday in class.b) Every student spends more than 5 hours every weekday in class.c) There is a student who does not spend more than 5 hours every weekday in class.d) No student spends more than 5 hours every weekday in class.9. a) x(P(x)∧Q(x)) b) x(P(x)∧﹁Q(x))c) x(P(x)∨Q(x)) d) x﹁(P(x)∨Q(x))16. a) true b) false c) true d) false24. Let C(x) be the propositional function “x is in your class.”a)x P(x) and x(C(x)→P(x)), where P(x) is “x has a cellular phone.”b) x F(x) and x(C(x)∧F(x)), where F(x) is “x has seen a foreign movie.”c)x﹁S(x) and x(C(x)∧﹁S(x)), where S(x) is “x can swim.”d)x E(x) and x(C(x)→E(x)), where E(x) is “x can solve quad ratic equations.”e)x﹁R(x) and x(C(x)∧﹁R(x)), where R(x) is “x wants to be rich.”62.a) x (P(x)→﹁S(x)) b)x(R(x)→S(x))c) x (Q(x)→P(x))d)x(Q(x)→﹁R(x))e) Yes. If x is one of my poultry, then he is a duck (by part(c)), hence not willing to waltz (part (a)). Since officers are always willing to waltz (part (b)), x is not an officer.1.412.d)x┐C(x, Bob)h)x y (I(x) ∧((x≠y) →┐ I(y)))k)x y( I(x) ∧┐C(x, y))n)x y z ((x≠y) ∧┐ (C(x, z) ∧ C(y, z)))14.a) x H(x), where H(x) is “x can speak Hindi”and the universe of the discourse consists of all students in this class.b) x y P(x, y), where P(x, y) is “x plays y.” and the universe of the discourse for x consists of all students in this class, and the universe of the discourse for y consists of all sports.c) x A(x) ∧┐H(x) , where A(x) is “x has visited Alaska.” , H(x) is “x has visited Hawaii” and the universe of the discourse for x consists of all students in this class.d) x y L(x, y), where L(x, y) is “x has learned programming language y” and the universe of the discourse for x consists of all students in this class, and the universe of the discourse for y consists of all programming languages.e) x z y (Q(y,z) →P(x, y)), where P(x, y) is“x has taken course y.”, Q(y, z) is “course y is offered by department z.”, and the universe of the discourse for x consists of all students in this class, the universe of the discourse for y consists of all courses in this school, and the universe of the discourse for z consists of all departments in this school.f)x y z ( (x≠y) ∧P(x, y)∧ ((x≠y≠z) →┐P(x, z))), where P(x, y) is “x and y grew up in the same town.” and the universe of the discourse for x, y, z consists of all students in this class.g) x y z C(x, y) ∧G(y, z), where C(x, y) is “x has chatted with y”, G(y, z) is “y is in chat group z”, the universe of the discourse for x, y consists of all students in this class, and the universe of the discourse for z consists of all chat group in this class.a) There is an additive identity for the real numbers.d) The product of two nonzero numbers is nonzero for the real numbers.38.b) There are no students in this class who have never seen a computer.d) There are no students in this class who have taken been in at least one room of every building on campus.1.5(1)(┐r∧(q→p))→(p→(q∨r)) <=> ┐(┐r∧(┐q∨p))∨(┐p∨(q∨r)) <=>(q∧┐p)∨(┐p∨q∨r)<=> (┐p∨q∨r∨q)∧(┐p∨q∨r∨┐p) <=> (┐p∨q∨r) <=> ∏3 <=> ∑0,1,2,4,5,6,7 (2) P.726. Let r be the proposition "It rains", let f be the proposition "It is foggy", let s be the proposition "The sailing race will be held", let l be the proposition "The lifesaving demonstration will go on", and let t be the proposition "The trophy will be awarded". We are given premises (┐r∨┐f)→(s∧l), s→t, and ┐t. We want to conclude r. We set up the proof in two columns, with reasons. Note that it is valid to replace subexpressions by other expressions logically equivalent to them.Step Reason1. ┐t Hypothesis2. s→t Hypothesis3. ┐s Modus tollens using Steps 1 and 24. (┐r∨┐f)→(s∧l) Hypothesis5. (┐(s∧l))→┐(┐r∨┐f) Contrapositive of step 46. (┐s∨┐l)→(r∧f) De Morgan's law and double negative7. ┐s∨┐l Addition, using Step 38. r∧f Modus ponens using Step 6 and 79. r Simplification using Step 8First, using the conclusion of Exercise 11, we should show that the argument form with premises (p ∧t) → (r ∨s), q→ (u ∧t), u→p, ┐s, q, and conclusion r is valid. Then, we use rules of inference from Table 1.Step Reason1. q Premise2. q→ (u ∧t)P remise3. u ∧t Modus ponens using Steps 1 and 24. u Simplification using Step 35. u→p Premise6. p Modus ponens using Steps 3 and 47. t Simplification using Step 38. p ∧t Conjunction using Steps 6 and 79. (p ∧t) → (r ∨s) Premise10. r ∨s Modus ponens using Steps 8 and 911. ┐s Premise12. r Disjunctive syllogism using Steps 10 and 11 14．b)Let R(x) be “x is one of the five roommates,” D(x) be “x has taken a course in discrete mathematics,” and A(x) be “x can take a course in algorithms.” The premises are x (R(x) → D(x)), x (D(x) → A(x)) and R(Melissa). Using the first premise and Universal Instantiation, R(Melissa) → D(Melissa) follows. Using the third premise and Modus Ponens, D(Melissa) follows. Using the second premise and Universal Instantiation, A(Melissa) follows. So do the other roommates.d) Let C(x) be “x is in the class,”F(x) be “x has been to France,” and L(x) be “x has visited Louvre.” The premises are x(C(x) ∧F(x)) and x (F(x) → L(x)). From the first premise and Existential Instantiation imply that C(y) ∧F(y) for a particularperson y. Using Simplification, F(y) follows. Using the second premise and Universal Instantiation F(y) → L(y) follows. Using Modus Ponens, L(y) follows. Using Existential Generalization, x(C(x) ∧L(x)) follows.24. The errors occur in steps (3), (5) and (7).For steps (3) and (5), we cannot assume, as is being done here, that the c that makes P(x) true is the same as the c that makes Q(x) true at the same time. For step (7), it is not a conjunction and there is no such disjunction rule.29.Step Reason1. x ┐P(x) Premise2. ┐P(c) Existential instantiation from (1)3. x (P(x) ∨Q(x)) Premise4. P(c) ∨Q(c) Universal instantiation from (3)5. Q(c) Disjunctive syllogism from (2) and (4)6. x (┐Q(x) ∨S(x)) Premise7. ┐Q (c) ∨S(c) Universal instantiation from (6)8. S(c) Disjunctive syllogism from (5) and (7)9. x (R(x) →┐S(x)) Premise10. R(c) →┐S(c) Universal instantiation from (9)11. ┐R(c) Modus tollens from (8) and (10)12. x ┐R(x) Existential generalization from (11)P.861.637.Suppose that P1→P4→P2→P5→P3→P1. To prove that one of these propositions implies any of the others, just use hypothetical syllogism repeatedly.P.1031.713.a) This statement asserts the existence of x with a certain property. If we let y=x, then we see that P(x) is true. If y is anything other than x, then P(x) is not true. Thus, x is the unique element that makes P true.b) The first clause here says that there is an element that makes P true. The second clause says that whenever two elements both make P true, they are in fact the same element. Together these say that P is satisfied by exactly one element.c) This statement asserts the existence of an x that makes P true and has the further property that whenever we find an element that makes P true, that element is x. In other words, x is the unique element that makes P true.P.1202.19.T T F T T F16. Since the empty set is a subset of every set, we just need to take a set B that contains Φ as an element. Thus we can let A = Φ and B = {Φ} as the simplest example.20 .The union of the sets in the power set of a set X must be exactly X. In other words, we can recover X from its power set, uniquely. Therefore the answer is yes.22.a) The power set of every set includes at least the empty set, so the power set cannot be empty. Thus Φ is not the power set of any set.b) This is the power set of {a}c) This set has three elements. Since 3 is not a power of 2, this set cannot be the power set of any set.d) This is the power set of {a,b}.28.a) {(a,x,0), (a,x,1), (a,y,0), (a,y,1), (b,x,0), (b,x,1), (b,y,0), (b,y,1), (c,x,0), (c,x,1), (c,y,0), (c,y,1)}c) {(0,a,x), (0,a,y), (0,b,x), (0,b,y), (0,c,x), (0,c,y), (1,a,x), (1,a,y), (1,b,x), (1,b,y), (1,c,x), (1,c,y)}P.1302.214. Since A = (A - B)∪(A∩B), we conclude that A = {1,5,7,8}∪{3,6,9} ={1,3,5,6,7,8,9}. Similarly B = (B - A)∪(A ∩ B) = {2,10}∪{3,6,9} = {2,3,6,9,10}.24. First suppose x is in the left-hand side. Then x must be in A but in neither B nor C. Thus x∈A - C, but x B - C, so x is in the right-hand side. Next suppose that x is in the right-hand side. Thus x must be in A - C and not in B - C. The first of these implies that x∈A and x C. But now it must also be the case that x B, since otherwise we would have x∈B - C. Thus we have shown that x is in A but in neither B nor C, which implies that x is in the left-hand side.40. This is an identity; each side consists of those things that are in an odd number of the sets A,B,and C.P147.2.335a) This really has two parts. First suppose that b is in f(S∪T). Thus b=f(a) for somea∈S∪T. Either a ∈S, in which case b∈f(S), or a∈T, in which case b∈f(T). Thus in either case b∈ f(S) ∪f(T). This shows that f(S∪T) ⊆f(S) ∪f(T), Conversely, suppose b∈f(S) ∪f(T). Then either b∈f(S) or b∈f(T). This means either that b=f(a) for some a∈S or that b=f(a) for some a ∈T. In either case, b=f(a) for some a∈S∪T, so b∈f(S∪T). This shows that f(S) ∪f(T) ⊆f(S∪T), and our proof is complete. b)Suppose b∈f(S∩T). Then b=f(a) for some a∈S∩T. This implies that a∈S anda∈T , so we have b∈f(S) and b∈f(T). Therefore b∈f(S)∩f(T), as desired.52In some sense this question is its own answer—the number of integers between a and b, inclusive, is the number of integers between a and b, inclusive. Presumably we seek an express involving a, b, and the floor and/or ceiling function to answer this question. If we round a up and round b down to integers, then we will be looking at the smallest and largest integers just inside the range of the integers we want to count, respectively. These values are of course ⎡⎤a and ⎣⎦b, respectively. Then the answer isb-+1 (just think of counting all the integers between these two values, ⎣⎦⎡⎤aincluding both ends—if a row of fenceposts one foot apart extends for k feet, then there are k +1 fenceposts). Note that this even works when, for example, a=0.3 and b=0.7 .P1622.434.a) This is countable. The integers in the set are ±1,±2,±4,±5,±7,andso on. We can listthese numbers in the order 1, -1 , 2, -2, 4, -4,…, thereby establishing the desired correspondence. In other words, the correspondence is given by 1↔1，2↔-1，3↔2，4↔-2，5↔4，and so on.b) This is similar to part(a);we can simply list the elements of the set in order ofincreasing absolute value, listing each positive term before its correspondingnegative:5,-5,10,-10,15,-15,20,-20,30,-30,40,-40,45,-45,50,-50,……c) This is countable but a little tricky. We can arrange the numbers in a 2-dimensionaltable as follows:1..1 0.11 0.111 0.1111 0.11111 ……1.1 1 1.1 1.11 1.111 1.1111 ……1.1111 11.1 11.11 11.111 11.1111 ……1111.111 111.1 111.11 111.111 111.1111 ……………………………………d) This set is not countable. We can prove it by the same diagonalization argument aswas used to prove that the set of all reals is uncountable in Example 21.All we need to do is choose d i=1 when d ii=9 and choose d i=9 when d ii=1 or d ii is blank(if the decimal expansion is finite)46.We know from Example 21 that the set of real numbers between 0 and 1 is uncountable. Let us associate to each real number in this range(including 0 but excluding 1) a function from the set of positive integers to the set {0,1,2,3,4,5,6,7,8,9} as follows: If x is a real number whose decimal representation is 0.d1d2d3…(with ambiguity resolved by forbidding the decimal to end with an infinite string of9's),then we associate to x the function whose rule is given by f(n)=d n. clearly this is a one-to-one function from the set of real numbers between 0 and 1 and a subset of the set of all functions from the set of positive integers the set {0,1,2,3,4,5,6,7,8,9}.Two different real numbers must have different decimal representations, so the corresponding functions are different.(A few functions are left out, because of forbidding representations such as 0.239999…)Since the set of real numbers between 0 and 1 is uncountable, the subset of functions we have associated with them must be uncountable. But the set of all such functions has at least this cardinality, so it, too, must be uncountable.P1913.21. The choices of C and k are not unique.a) Yes C = 1, k = 10 b) Yes C = 4, k = 7 c) Nod) Yes C = 5, k = 1 e) Yes C = 1, k = 0 f) Yes C = 1, k = 29. x2+4x+17 ≤ 3x3 for all x＞17, so x2+4x+17 is O(x3), with witnesses C = 3, k=17. However, if x3 were O(x2+4x+17), then x3≤C(x2+4x+17) ≤ 3Cx2for some C, for all sufficiently large x, which implies that x≤ 3C, for all sufficiently large x, which is impossible.P2093.419.a) no b) no c) yes d) no31.a) GR QRW SDVV JRb) QB ABG CNFF TBc) QX UXM AHJJ ZXP2183.513.a) Yes b) No c) Yes d) Yes17a) 2 b) 4 c) 12P2804.122.A little computation convinces us that the answer is that n2 ≤ n! for n= 0, 1, and all n≥ 4. (clearly the inequality doesn’t hold for n=2 or n=3) We will prove by mathematical induction that the inequality holds for all n≥ 4. The base case is clear, since 16 ≤ 24. Now suppose that n2 ≤ n! for a given n≥ 4. We m ust show that (n+1)2≤ (n+1)!. Expanding the left-hand side, applying the inductive hypothesis, and then invoking some valid bounds shows this:n2 + 2n+ 1 ≤ n! + 2n + 1≤ n! + 2n + 1 = n! + 3n≤ n! + n·n≤ n! + n·n!≤ (n+1)n! = (n+1)!P2934.231.Assume that the well-ordering property holds. Suppose that P(1) is true and that the conditional statement [P(1)∧P(2) ∧···∧P(n)] →P(n+1) is true for every positive integer n. Let S be the set of positive integers n for which P(n) is false. We will show S=Ø. Assume that S≠Ø, then by the well-ordering property there is a least integer m in S. We know that m cannot be 1 because P(1) is true. Because n=m is the least integer such that P(n) is false, P(1), P(2),…,P(m-1) are true, and m-1 ≥1. Because [P(1)∧P(2) ∧···∧P(m-1)] →P(m) is true, it follows that P(m) must also be true, which is a contradiction. Hence, S= Ø.P3084.310.The base case is that S m(0)=m. The recursive part is that S m(n+1) is the successor of S m(n)(i.e., S m(n)+1)12.The base case n=1 is clear, since f12=f1f2=1. Assume the inductive hypothesis. Thenf12+f22+…+f n2+f n+12 = f n+12+f n f n+1= f n+1(f n+1+f n)= f n+1f n+2, as desired.31.If x is a set or variable representing set, then x is well-formed formula. if x and y are all well-formed formulas, then x, (x∪y), (x∩y) and (x-y) are all well-formed formulas.50.Let P(n) be “A(1, n) = 2n .”BASIC STEP: P(1) is true, because P(1) = A(1, 1) = 2 = 21.INDCUTIVE STEP: Assume that P(m) is true, that is A(1, m) = 2m and m≥1. Then P(m+1) = A(1, m+1) = A(0, A(1, m))= A(0, 2m)=2·2m=2m+1.So A(1, n) = 2n whenever n≥159.b) Not well defined. F(2) is not defined since F(0) isn’t.Also, F(2) is ambiguous.d) Not well defined. The definition is ambiguous about n=1.P3445.13.a) 104b) 10512.We use the sum rule, adding the number of bit strings of each length up to 6. If we include the empty string, then we get 20 + 21 + 22 + 23 + 24 + 25 + 26= 27–1=12720.a) Every seventh number is divisible by 7. Therefore there are 999 / 7=142such numbers. Note that we use the floor function, because the k th multiple of 7 does not occur until the number 7k has been reached.b) For solving this part and the next four parts, we need to use the principle of inclusion-exclusion. Just as in part(a), there are 999/11=90 numbers in our range divisible by 11, and there are 999/77=12 numbers in our range divisible by both 7 and 11 (the multiples of 77 are the numbers we seek). If we take these 12 numbers are away from the 142 numbers divisible by 7, we see that there are 130 numbers in our range divisible by 7 but not by 11.c) as explained in part(b), the answer is 12.d) By the principle of inclusion-exclusion, the answer, using the data from part (b), is 142+90-12=220.e) If we subtract from the answer to part(d) the number of numbers divisible by neither of them; so the answer is 220-12=208.f) If we subtract the answer to part(d) from the total number of positive integers less than 1000, we will have the number of numbers divisible by exactly one of them; so the answer is 999-220=779.g) If we assume that numbers are written without leading 0s, then we should break the problem down into three cases-one-digit numbers, two-digit numbers. Clearly there are 9 one-digit numbers, and each of them has distinct digits. There are 90 two-digit numbers (10 through 99), and all but 9 of them have distinct digits. An alternativeway to compute this is to note that the first digit must be 1 through 9 (9 choices) and the second digit must be something different from the first digit (9 choices out of the 10 possible digits), so by the product rule, we get 9*9=81 choices in all. This approach also tells us that there are 9*9*8=648 three-digit numbers with distinct digits (again, work from left to right-in the ones place, one 8 digits are left to choose from). 80 the final answer is 9+81+648=738.h) It turns out to be easier to count the odd numbers with distinct digits and subtract from our answer to part(g), so let us proceed that way. There are 5 odd one-digit numbers. For two-digit numbers, first choose the one digit (5 choices), then choose the tens digits (8 choices), since neither the ones digit value not 0 is available); therefore there are 40 such two-digit numbers. (Note that this is not exactly half of 81.) For the three-digit numbers, first choose the ones digit (5 choices), then the hundreds digit (8 choices), then the tens digit (8 choices), giving us 320 in all. So there are 5+40+320=365 odd numbers with distinct digits. Thus the final answer is 738-365=373.35.a) 若n=1, 为2；若n=2, 为2; 若n>=3, 为0b) 对于n>1, 为22 n；若n=1, 为1；c) 2(n-1) (注：n可映射到0，1两种可能)44.First we count the number of bit strings of length 10 that contain five consecutive 0’s. We will base the count on where the string of five or more consecutive 0’s starts. If it starts in the first bit, then the first five bits are all 0’s, but there is free choice for the last five bits; therefore there are 25 = 32 such strings. If it starts in the second bit, then the first bit must be a 1, the next five bits are all 0’s, but there is free choice for the last four bits; therefore there are 24 = 16 such strings. If it starts in the third bit, then the second bit must be a 1 but the first bit and the last three bits are arbitrary; therefore there are 24= 16 such strings. Similarly, there are 16 such strings that have the consecutive 0’s starting in each of positions four, five ,and six. This gives us a total of 32+5×16=112 strings that contain five consecutive 0’s. Symmetrically, there are 112 strings that contain five consecutive 1’s. Clearly there are exactly two strings that contain both (0000011111,1111100000). Therefore by the inclusion-exclusion principle, the answer is 2*(112)-2=222.52.We draw the tree, with its root at the top. We show a branch for each of the possibilities 0 and 1, for each bit in order, except that we do not allow three consecutive 0’s. Since there are 13 leaves, the answer is 13.second bitthird bitfourth bitP3535.26.There are only d possible remainders when an integer is divided by d, namely 0, 1, …, d-1. By the pigeonhole principle, if we have d+1 remainders, then at least two must be the same.10.The midpoint of the segment whose endpoints are (a,b) and (c,d) is ( ( a + c ) / 2, ( b + d ) / 2). We are concerned only with integer values of the original coordinates. Clearly the coordinates of these fractions will be integers as well if and only if a and c have the same parity (both odd or both even) and b and d have the same parity. Thus what matters in this problem is the parities of coordinates. There are four possible pairs of parities: (odd,odd), (odd, even), (even, even) and (even,odd). Since we are given five points, the pigeonhole principle guarantees that at least two of them will have the same pair of parties. The midpoint of the segment joining these two points will therefore have integer coordinates.38.a) T b) Tc) T1 ≤a1< a2 < …< a75≤ 125 , and 26 ≤a1 + 25 < a2 + 25 < …< a75 + 25 ≤ 150.Now either of these 150 numbers are precisely all the number from 1 to 150, or else by the pigeonhole principle we get, as in Exercise 37, a i = a j + 25 for some i and j and we are done. In the former case, however, since each of the number a i + 25 is greater than or equal to 26, the numbers 1, 2, … , 25 must all appear among the a i’s. But since the a i’s are increasing, the only way this can happen is if a1=1, a2 =2 , …, a25=25. Thus there were exactly 25 matches in the first25 hours.d) TWe need a different approach for this part, an approach, incidentally, that works for many numbers besides 30 in this setting. Let a1, a2 , …a75 be as before, and note that 1 ≤a1< a2 < …< a75≤ 125. By the pigeonhole principle two of the numbers among a1, a2 , …a 31 are congruent modulo 30. If they differ by 30, then we have our solution. Otherwise they differ by 60 or more, so a 31 ≥ 61. Similarly, among a 31through a 61 ,either we find a solution, or two numbers must differ by 60 or more; therefore we assume that a 61 ≥ 121. But this means that a 66 ≥ 126, a contradiction.注：38题d 因为30大于25，不能用解决a，b，c的方法解决，所以适用一种新的方法（这种方法对前面3问同样适用的）。
