MATH 211 Exam 2 With Solution, Fall 2005

MATH 346-06S TEST I NAME: KEY (1) True/False Questions: Here A, B etc. denote sets while x, y, · · · denote elements, and P(A) denotes the power set of a set A. (a) T F φ ∈ {x, y}. False because φ is a set, not an element (b) T F {x} = {{x}, x}. False because the set {x} is not the same as the element x. (c) T F {x, y, {x, y}} ⊆ P({x, y}). False because x and y are elements of {x, y}, not subsets (d) T F A ∩ ¯B = B − A. False, it is actually A − B (e) T F |P({1, 2, 3, 4, 5})| = 52. False, it is 25 (f) T F f : N → N where f(n) = 2n − 1 is a bijection. False, not even a function because 0 has no image. (g) T F The proposition (p → ¬p) → p is a tautology. False, considering the assignment p = F you get (F → T) → F which is equivalent to (T) → F. But this is a false statement. (2) Fill in the blank. (You might want to use a Venn diagram). (a) A ∩ B = B ⇒ B ⊆ A................................. (b) A ∩ ( ¯A ∪ B) = A ∩ B................................. (c) The number of Boolean functions of three Boolean vari- ables is 28 = 256......................................... 1 2 (d) (n3 + n2 log n)(n2 + 2n) + (n! + 3n10) is O(n2..................). (3) Which of the following pairs of propositions are equivalent? Ex- plain. (a) (p ∨ q) → r and (p → r) ∨ (q → r) Not equivalent. Consider the truth assignment p = F, q = T, r = F: lhs is F but rhs is T. (In fact the lhs is equivalent to (p → r) ∧ (q → r). This is the underlying equivalence for the proof by cases.) (b) p ∨ (p ∧ q) and q Not equivalent: consider p = T and q = F. (c) ¬p → (q → r) and q → (p ∨ r) Equivalent: lhs is equivalent to p ∨ (¬q ∨ r). The rhs is equivalent to ¬q ∨ (p ∨ r). The last two are equivalent by the associativity and commutativity of the disjunction operator. (4) Express the following propositions using only complements and conjunction. (a) p ∨ q ∨ r ¬(¬p ∧ ¬q ∧ ¬r) by de Morgan’s law. (b) (p → ¬q) → p (¬p ∨ ¬q) → p ≡ ¬(¬p ∨ ¬q) ∨ p ≡ (p ∧ q) ∨ p ≡ p where the last one is by absorption. Note: if you end up with ¬(¬(p ∧ q) ∧ ¬p) you still get most of the grade, because you don’t get the simplest form. (5) Write the converse, the inverse, and the contrapositive of the following statement: “For it to be rainy, it is sufficient that it be cloudy”. Note that the sufficiency of being cloudy means that ” if it is cloudy then it will be rainy”. The converse: ”if it rains then it is cloudy”. The inverse: ”if it is not cloudy then it is not rainy”. The contraposition: ”if it is not rainy then it is not cloudy”. (6) Translate the following to a logical expression. Give necessary definitions. Use quantifiers when necessary. 3 (a) We go to the park if it is sunny. s: it is sunny g: we go to the park s → g. (b) No one is perfect. Domain: all people. P(x): ”person x is perfect”. ¬∃xP(x) (c) Not everyone is perfect. ¬∀xP(x) (d) There is exactly one person who is perfect. ∃x(P(x) ∧ ∀y(P(y) → y = x)). (7) Prove that if n2 is even then n is even. Proof by contraposition: Suppose n is not even. Then n is odd. So there exists an integer k such that n = 2k + 1. Therefore, n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1. Since 2k2 + 2k is an integer, it follows that n2 is odd. This finishes the proof. (8) Prove or disprove that the product of two irrational numbers is irrational. We disprove the statement using a counter example: Con- sider x = y = √ 2. Then we know that x and y are irrational. However, x × y = √ 2 × √ 2 = 2 which is rational. (9) Write down a function from N to N that is one to one but not onto. Consider the function f(n) = 2n. (Note: you should also prove that this function is one to one but not onto to get a perfect score.. not just list it!) (10) Prove that the function f(x) = 3x2 − 4x + 3 is O(x2). Make sure you carefully find a pair of witnesses to this relationship.