Exam 1 A. Miller Spring 2008 Math 240 0Show all work on problems 5-9 for partial credit.No notes, no books, no calculators, no cell phones, no pagers, no electronicdevices of any kind.NameCircle your Discussion Section:DIS 301 9:55 T B305 VAN VLECKDIS 302 9:55 R 115 INGRAHAMDIS 305 1:20p T B105 VAN VLECKDIS 306 1:20p R B333 VAN VLECKProblem Points Score1 92 103 124 105 126 107 128 159 10Total 100Solutions will be posted shortly after the exam:www.math.wisc.edu/∼miller/m240Exam 1 A. Miller Spring 2008 Math 240 11. (9 pts) Match each of these with the statement which is closest to itsnegation.Circle the letter: (a) (b) (c) of the statement closest to the negation ofthe given statement.1. Today is Wednesday.(a) Tomorrow is Wednesday.(b) Yesterday was not Tuesday.(c) Today is never Wednesday.2. There is pollution in Lake Michigan.(a) There is no pollution in the Great Lakes.(b) Lake Erie is really polluted.(c) Lake Michigan is not polluted.3. In the summer in Wisconsin, there are many mosquitos.(a) It is too cold in the winter in Wisconsin to have mosquitos.(b) There are very few mosquitos in June, July, and August in Wis-consin.(c) The mosquito is not really the state bird of Wisconsin.Exam 1 A. Miller Spring 2008 Math 240 22. (10 pts) Enter the correct letter a,b,c,d,e in each blank:1. ≡ A \ B = A2. ≡ (A \ B) = (B \ A)3. ≡ A ∩ B = A \ B4. ≡ A ∩ B = B5. ≡ B ∪ A = B(a) A = B(b) A ⊆ B(c) A ∩ B = ∅(d) B ⊆ A(e) none of aboveExam 1 A. Miller Spring 2008 Math 240 33. (12 pts)The domain U for the variables and the relation C consists of the studentsin our class. The relation C(x, y) says that x has copied the homework of ywho is different from x.For each logical formula choose a the best match in English and put theletter A B C D E F in the blank provided.1. ≡ ∃x∃y C(x, y)2. ≡ ∀x∃y C(x, y)3. ≡ ∀y∃x C(x, y)4. ≡ ∃x∀y (C(x, y) ∨ x = y)5. ≡ ∀x∀y (C(x, y) ∨ x = y)6. ≡ ∃y∀x (x 6= y → C(x, y))(A) Everybody in class has cheated off somebody.(B) Somebody cheats off everybody else.(C) There is a genius that everybody else cheats off of.(D) There is at least one cheater.(E) Everybody does all there homework together.(F) Everybody’s homework is copied by somebody.Exam 1 A. Miller Spring 2008 Math 240 44. (10 pts) The set A = {a, b} has two elements.(a) List the set P(A) here:(b) How many elements does the set P(P(A)) have? Enter the numberhere:.Exam 1 A. Miller Spring 2008 Math 240 55. (12 pts) Determine which of the following sets are countable and whichare uncountable. Circle the word countable or uncountable.1. The negative integers. countable uncountable2. The real line, R. countable uncountable3. The plane, R2. countable uncountable4. Set of integers which are perfect squares. countable uncountable5. Power set of the natural numbers, P(N). countable uncountableFor each of the s ets that is countable exhibit a map from the natural numbersN onto the set.Exam 1 A. Miller Spring 2008 Math 240 66. (10 pts) Show that(p → q) ∨ (p → r)is logically equivalent top → (q ∨ r).Exam 1 A. Miller Spring 2008 Math 240 77. (12 pts) Suppose that the domain U of the predicate R(x, y) consists ofthe just two distinct objects U = {a, b}. Write out a propositional sentencewhich is equivalent to the predicate sentence:∀x ∃y R(x, y).Hint: Your answer can use disjunctions and conjunctions, but no quantifiers.Exam 1 A. Miller Spring 2008 Math 240 88. (15 pts) Use a proof by contradiction to show that there is no rationalnumber r such that r3+ 3r + 5 = 0.Hint: assume r = a/b is in lowest terms. Obtain an equation involvingintegers by multiplying by b3. Show that the three cases each lead to acontradiction:(1) a odd and b odd.(2) a even and b odd.(3) a odd and b even.Exam 1 A. Miller Spring 2008 Math 240 99. (10 pts) What is the difference between a constructive and nonconstructiveexistence proof? Give an example of each.Exam 1 A. Miller Spring 2008 Math 240 10Answers1. 1b 2c 3b The statement “Today is Wednesday” is the same as thestatement “Yesterday was Tuesday”.2. 1c 2a 3e 4d 5b3. 1D 2A 3F 4B 5E 6C4. (a) {∅, {a}, {b}, {a, b}} (b) 165.(1) the set of negative integers is countable. The mapping defined byn 7→ −(n + 1) takes N onto the negative integers.(4) The set of integers which are perfect squares is countable. The map-ping defined by n 7→ n2takes N onto it.The other sets are uncountable.6. They have the same truth table. All lines are true except p true, qfalse, r false.7. (R(a, a) ∨ R(a, b)) ∧ (R(b, a) ∨ R(b, b))8. First we prove aLemma The product of two integers is odd iff both are odd. Similarly,the sum of two integers is even iff both are even or both odd.proof: If a and b are odd then there are integers n and m such thata = 2n + 1 and b = 2m + 1. But thenab = (2n + 1)(2m + 1) = 4nm + 2n + 2m + 1 = 2(2nm + n + m) + 1and hence it is odd. Conversely if either a or b is even, say a is even, thenthere exists an integer n such that a = 2n and so ab = 2nb and so ab is even.The sums are proved similarly.QEDIt follows immediately that the product of three odd integers is odd.Now suppose that r3+3r +5 = 0 and for contradiction, that r is rational.Then let r = a/b where a and b are integers and not both of them are even.Then(ab)3+ 3(ab) + 5 = 0 so a3+ 3ab2+ 5b3= 0Exam 1 A. Miller Spring 2008 Math 240 11Case (1) a odd and b odd. In this case since the product of odd numbersis odd each of a3, 3ab2, 5b3is odd. Then since the sum of 3 odd numbers isodd, they cannot total 0 which is even.Case (2) a even and b odd. In this case a3and 3ab2are even and 5b3isodd. Hence the total is odd and cannot be 0.Case (3) a o dd and b even. In this case a3is odd and both 3ab2and 5b3are even. Hence, again the total is odd and so cannot add up to 0.QED9. A proof of a statement of the form ∃x P (x) is constructive if it actu-ally produces an x satisfying the statement P(x). A nonconstructive proofdoesn’t produce a particular x. An example, of a nonconstructive proof isthe proof given in the book on page 91 of the existence of two irrationalnumbers x and y such that xyis rational. An example of a constructiveproof is showing that 223 cannot be written as the sum of 36 fifth powers ofnonnegative integers, exercise 39 on page