Exam 1 A. Miller Spring 2002 Math 240 1Show all work. Circle your answer.No notes, no books, no calculator, no cell phones, no pagers, no electronic devicesat all.Solutions will be posted shortly after the exam: www.math.wisc.edu/∼miller/m240NameProblem Points Score1 62 63 64 65 66 67 68 59 510 811 812 813 814 815 8Total 100Exam 1 A. Miller Spring 2002 Math 240 21. (6 pts) Show that p → q and (¬q) → (¬p) are logically equivalent.2. (6 pts) Construct a truth table for the following propositional sentence:(p ∨ q) → (p ∧ r)Exam 1 A. Miller Spring 2002 Math 240 33. (6 pts) Find a statement which is logically equivalent to¬[ (∃x P (x)) → (∀y Q(y)) ]but in which the negation sign appears (if at all) only in front of the predicate symbols.4. (6 pts) Let A = {1, 2} and B = {1, 3, 5}. Find A × B.Exam 1 A. Miller Spring 2002 Math 240 45. (6 pts) Let A = {1, 3, 4}, B = {2, 4}, and C = {3, 4, 5, 6}. Find(a) |A|(b) B \ C(c) (A ∪ B) ∩ C6. (6 pts) Let f : R → R be defined byf(x) = bxcLet S = {2, 5}. Find f−1(S).Exam 1 A. Miller Spring 2002 Math 240 57. (6 pts) Compute the following double sum:2Xi=13Xj=1(i + j)8. (5 pts) How large a problem can be s olved in 10 seconds or less using an algorithmthat when input n requires f(n) = n2bit operations where each bit operation is carriedout in 10−9seconds?Exam 1 A. Miller Spring 2002 Math 240 69. (5 pts) The value of the Euler φ-function at the positive integer n is defined to bethe number of positive integers less than or equal to n that are relatively prime to n.Find φ(12).10. (8 pts) What is smallest positive integer k such that the functionf(n) = (n log(n) + 1)2is O(nk)?Exam 1 A. Miller Spring 2002 Math 240 711. (8 pts) Show that 2n> 2n + 1 for all integers n ≥ 3.12. (8 pts) Let fnbe the nthelement of the Fibonacci sequence. Prove thatf1+ f3+ f5+ · · · + f2n−1= f2nfor every positive integer n.Exam 1 A. Miller Spring 2002 Math 240 813. (8 pts) Find a 2 × 2 matrix A so thatA1 20 −1=1 03 2Hint: Solve a system of linear equations.Exam 1 A. Miller Spring 2002 Math 240 914. (8 pts) Let n = (. . . akak−1. . . a2a1a0)2be any positive integer written in binary.Let E be the set of even k such that ak= 1 andlet O be the set of odd k such that ak= 1.Show that n is divisible by 3 if and only if |E| + 2|O| is divisible by 3.Exam 1 A. Miller Spring 2002 Math 240 1015. (8 pts)(a) Find d =gcd(54, 17) using the Euclidean Algorithm.(b) Find integers a and b such that d = a 54 + b 17Exam 1 A. Miller Spring 2002 Math 240 11Answers1. p → q is false iff p is true and q is false.(¬q) → (¬p) is false iff ¬q is true and ¬p is false.Hence they have the same truth table.2.p q r (p ∨ q) → (p ∧ r)T T T T T TT T F T F FT F T T T TT F F T F FF T T T F FF T F T F FF F T F T FF F F F T F3. (∃x P (x)) ∧ (∃y ¬Q(x))4. {(1, 1), (1, 3), (1, 5), (2, 1), (2, 3), (2, 5)}5. |A| = 3, B \ C = {2}, (A ∪ B) ∩ C = {3, 4}6. {x : 2 ≤ x < 3 or 5 ≤ x < 6} = [2, 3) ∪ [5, 6)7. 218. n = 1059. 410. k = 3 because log(n) is O(n) for any real  > 0.11. This is proved by induction.Basis: n = 3 this true because 23= 8 > 7 = 2 ∗ 3 + 1 = 7Inductive step. Assume 2n> 2n + 1 and n ≥ 3. Then2n+1= 2 ∗ 2n= 2n+ 2n> 2n + 1 + 2n> 2n + 1 + 8 > 2(n + 1) + 1By inductive hypothesis and since 2n≥ 23= 8. Hence2n+1> 2(n + 1) + 1as we needed to show.Exam 1 A. Miller Spring 2002 Math 240 1212. This is proved by induction.Basis: f1= 1 = f2Inductive Step: Assume true for n. Thenf1+ f3+ f5+ · · · + f2n−1+ f2n+1= f2n+ f2n+1by inductive hypothesis. But by the definition of Fibonacci sequencef2n+ f2n+1= f2n+2= f2(n+1)and so noting that 2(n + 1) − 1 = 2n + 1f1+ f3+ f5+ · · · + f2(n+1)−1= f2(n+1)as was to be shown.13.A =1 23 414. If k is even, say k = 2l then2k= 22l= 4lBut 4 ≡31 so it follows that2k≡34l≡31l≡31If k is odd, then k − 1 is even and hence2k= 2 ∗ 2k−1≡32Now since n =Pk∈E2k+Pk∈O2kit follows from above thatn ≡3Xk∈E1 +Xk∈O2butXk∈E1 +Xk∈O2 = |E| + 2|O|so 3 divides n iff n ≡30 iff |E| + 2|O| ≡30 iff 3 divides |E| + 2|O|15.54, 17 54 = 3(17) + 33, 17 17 = 5(3) + 23, 2 and we see that gcd is 1.1 = −1(3) + 2(2) using 2 = 17 − 5(3) we get1 = −1(3) + 2(17 − 5(3)) = −11(3) + 2(17)1 = −11(3) + 2(17) using 3=54-3(17) we get1 = −11(54 − 3(17)) + 2(17) = −11(54) +