MATH 211 Exam 2, Fall 2006

Math 211 — Fall 2006–07 Discrete Structures Quiz 1, October 30 — Duration: 1 hour GRADES (each problem is worth 12 points): 1 2 3 4 5 6 TOTAL/72 YOUR NAME: YOUR AUB ID#: PLEASE CIRCLE YOUR SECTION: Section 1 Section 2 Section 3 Section 4 Recitation W 4 Recitation W 11 Recitation Th 12:30 Recitation Th 3:30 Professor Makdisi Ms. Karam Ms. Karam Ms. Karam INSTRUCTIONS: 1. Write your NAME and AUB ID number, and circle your SECTION above. 2. Solve the problems inside the booklet. Explain your reasoning precisely and clearly to ensure full credit. Partial solutions will receive partial credit. Each problem is worth 12 points. 3. You may use the back of each page for scratchwork OR for solutions. There are two extra blank sheets at the end, for extra scratchwork or solutions. If you need to continue a solution on another page, INDICATE CLEARLY WHERE THE GRADER SHOULD CONTINUE READING. 4. Open book and notes. NO CALCULATORS ALLOWED. Turn OFF and put away any cell phones. GOOD LUCK! i An overview of the exam problems. Each problem is worth 12 points. Take a minute to look at all the questions, THEN solve each problem on its corresponding page INSIDE the booklet. 1. (total 12 pts) Let A = {1, 2, 3} and B = {1, 2, 5, 10}. a) (2 pts) Find A∪B. b) (2 pts) Find A∩B. (The answer does not depend on the choice of universal set.) c) (4 pts) Write the following sentence using symbols, and determine whether it is true or false (briefly say why): “Every element of A is a divisor of some element of B” d) (4 pts) Write the following sentence using symbols, and determine whether it is true or false (briefly say why): “Some element of A is a divisor of every element of B” 2. (total 12 pts) Let f : Z → Z be the function defined by f(n) = �n 3 � . a) (2 pts) Find the image set f({1, 3, 4, 100}). b) (2 pts) Find the inverse image set f −1({−1, 10}). c) (4 pts) Is f an injection? Why or why not (give a brief explanation)? d) (4 pts) Is f a surjection? Why or why not (give a brief explanation)? 3. (total 12 pts) Show that p → (q → r) is logically equivalent to (p ∧ q) → r in two different ways, (a) and (b+c): a) (4 pts) Use a truth table. b) (4 pts) Give a direct proof that if p → (q → r), then (p ∧ q) → r. c) (4 pts) Give a direct proof of the converse of the statement in (b). 4. (total 12 pts) Given the sequence a1, a2, a3, . . . of real numbers, defined (recursively) by: a1 = √ 2, ∀n ≥ 1, an+1 = 1 + 1 an . a) (6 pts) Show that ∀n ≥ 1, 1 < an < 2. b) (6 pts) Show that ∀n ≥ 1, an is irrational. (You already know that √ 2 is irrational, so just prove the inductive step.) 5. (total 12 pts) Given sets X, Y , and a function f : X → Y . Prove the following statements FROM THE DEFINITION of the image set and inverse image sets. I.e., you are NOT ALLOWED to use identities such as f −1(S∩T) = f −1(S)∩f −1(T), unless you include a proof of the identities you use. (It is possible to give a short solution that does not involve proving these identities first.) a) (6 pts) Assume that A, B, C ⊆ X satisfy A ⊆ C and B ⊆ C. Show that f(A)∪f(B) ⊆ f(C). b) (6 pts) Assume that S, T ⊆ Y satisfy S∩T = ∅. Show that f −1(S)∩f −1(T) = ∅. 6. (12 pts) Let A = {a, b, c, d} and B = {1, 2, 3, 4}. How many functions f : A → B are there such that EITHER � f(a) = 1 � OR � f(a) = 2 AND f is injective � ? ii