CMPS 211 Homework 3 with Solution, Spring 2016

American University of Beirut Department of Computer Science CMPS 211 - Spring 2015-16 Assignment 3 - Solution Key Exercise 1 (10 Points) Let A, B, and C be sets. Show that: (a) (A ∪ B) ⊆ (A ∪ B ∪ C) Solution: {x|x ∈ (A ∪ B)} (Assumption) → {x|x ∈ A ∨ x ∈ B} (Definition of Union) → {x|x ∈ A ∨ x ∈ B ∨ x ∈ C} (Addition) → {x|x ∈ (A ∪ B ∪ C)} (Definition of Union) (b) (A ∩ B ∩ C) ⊆ (A ∩ B) Solution: {x|x ∈ (A ∩ B ∩ C)} (Assumption) → {x|x ∈ A ∧ x ∈ B ∧ x ∈ C} (Definition of Intersection) → {x|x ∈ A ∧ x ∈ B} (Simplification) → {x|x ∈ A ∩ B} (Definition of Intersection) (c) (A − B) − C ⊆ A − C Solution: {x|x ∈ ((A − B) − C)} (Assumption) → {x|((x ∈ A ∧ x ̸∈ B) ∧ x ̸∈ C)} (Definition of Difference) → {x|((x ∈ A ∧ x ̸∈ C)} (Simplification - After use of commut. and Assoc. Laws on ∧) → {x|x ∈ (A − C)} (Definition of Difference) (d) (A − C) ∩ (C − B) = φ Solution: {x|x ∈ (A − C) ∩ (C − B)} (Assumption) → {x|((x ∈ A ∧ x ̸∈ C) ∧ (x ∈ C ∧ x ̸∈ B)} (Definition of Difference and Intersection) → {x|(x ∈ A ∧ (x ̸∈ C ∧ x ∈ C) ∧ x ̸∈ B} (Commutativity) → {x|x ̸∈ C ∧ x ∈ C} (Simplification) Contradiction, Therefore the logical expression is unsatisfiable (always has truth value “false”), which means that (A − C) ∩ (C − B) has no elements. Hence, (A − C) ∩ (C − B) = φ (e) (B − A) ∪ (C − A) = (B ∪ C) − A {x|x ∈ (B − A) ∪ (C − A)} (Assumption) ↔ {x|(x ∈ B ∧ x ̸∈ A) ∨ (x ∈ C ∧ x ̸∈ A)} (Definition of Difference and Union) ↔ {x|(x ∈ B ∨ x ∈ C) ∧ x ̸∈ A} (Distribution) ↔ {x|x ∈ (B ∪ C) − A} (Definition of Difference and Union) Since every step is an equivalence then (B − A) ∪ (C − A) = (B ∪ C) − A 1 Exercise 2 (10 Points) Draw The Venn Diagrams for each of these combinations of the sets A, B, and C. (a) (A ∩ B) ∪ (A − C) {the solution is the shaded areas} (b) (A ∩ B ∪ (A − B)) ∩ C {the solution is the shaded areas} Note that A ∩ B ∪ (A − B) is equal to A. 2 Exercise 3 (15 Points) Give an example of two uncountable sets A and B such that A − B is: (a) Finite A = IR, B = IR − {0}. A − B = {0}(Finite) (b) Countable infinite A = IR, B = IR − IN. A − B = IN(CountablyInfinite) (c) Uncountable infinite A = IR, B = IR − [0, 1]. A − B = [0, 1](Uncountable) Exercise 4 (15 Points) Prove that if A is uncountable and A ⊆ B, then B is uncountable. Solution 1: Proof by contradiction Assume A is uncountable and A ⊆ B. For the sake of contradiction, assume B is countable. if B is countable then there exists a bijection (one-to-one and onto) (f) between B and IN. f : B → IN Construct the function f|A by restricting the domain of f to A ⊆ B, i.e: f|A : A → IN : f|A (x) = f(x) f|A is defined the same was as f but with a smaller domain. Since f is injective (one-to-one), then f|A is also one-to-one (note that f|A may no longer be onto). However, since A is uncountable, then there does not exist any injective function from it to IN. Contradiction, B must be uncountable. Solution 2: Assume that B is countable. Then the elements of B can be listed as b1, b2, b3 Because A is a subset of B, taking the subsequence of {bn} that contains the terms that are in A only gives a listing of the elements of A. Because A is uncountable, this is impossible, and therefore B can’t be countable Exercise 5 (15 Points) Determine whether each of these sets is finite, countably infinite, or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set. (a) The negative integers. Countably infinite: f(x) = −x (b) The even integers. Countably infinite: f(x) = � x if x is even −x − 1 if x is odd (c) The real numbers between 0 and 1. Uncountable (d) The positive integers less than 1,000,000,000. Countable, because they are finite (e) The integers that are multiples of 7. Countably infinite: f(x) = � 7 × x 2 if x is even 7 × −x−1 2 if x is odd 3 (f) The odd negative integers. Countably infinite: f(x) = −2x + 1 (g) The integers with absolute value less than 1,000,000. Countable, because they are finite (h) The set A × Z+ where A = 2, 3. Countably infinite: f(x) = � (2, x 2) if x is even (3, x+1 2 ) if x is odd (i) All bit strings not containing the bit 0. Countable: for any integer n, the corresponding bit string would be a string formed of n 0s Exercise 6 (15 Points) Prove that the set of all polynomials of degree ≤ 2 with integer coefficients is countable. [Hint: use the proof that Q is countable shown in the slides] Solution: Let P2 be the set of all polynomials of degree ≤ 2 with integer coefficients. Thus P2 = {ax2 + bx + c | a, b, c are integers}. Since the set N × N is countable, therefore Z × Z is countable also countable (|N| = |Z| since there is a bijection between the two sets, and therefore we can substitute N by Z). Again, Z2 is countable, Z2 × Z = Z3 is also countable. Define a function f: Z3 → P2 by the formula: F(a, b, c) = ax2 + bx + c where a, b, c ∈ Z By construction the function f is a one-to-one correspondence. Hence P2 is countable. Exercise 7 (10 Points) Can you conclude that A = B if A, B, and C are sets such that: (a) A ∪ C = B ∪ C. Solution: No, Counter example: A = {1, 2}, C = {1, 2, 3}, B = {3}. A ∪ C = B ∪ C = {1, 2, 3} (b) A ∩ C = B ∩ C. Solution: No, Counter example: A = {1, 2, 3}, C = {1, 2}, B = {1, 2, 4}. A ∩ C = B ∩ C = {1, 2} (c) A − C = B − C. Solution: No, Counter example: A = {1, 2, 3}, C = {3, 4}, B = {1, 2, 4}. A − C = B − C = {1, 2} 4 Exercise 8 (10 Points) Find the domain and range of these functions. (a) The function that assigns to each non-negative integer its first digit. Domain is the set of non-negative integers (naturals). Range = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} (Note that non-negative integers contain the integer 0, and the first digit of 0 is 0, so 0 is in the range). (b) The function that assigns to a bit string the number of one bits in the string. Domain is all bit strings. Range is the naturals. (c) The function that assigns to each non-negative integer its 2nd power and returns the last digit Domain is the set of non-negative integers (naturals). Range = {0, 1, 4, 9, 6, 5}. You can find the set by taking all possible last digits (0 to 9), getting the square of the digit, and finding its unit digit. Recall the expansion of (10a + b)2, where a and b are integers, and 0 ≤ b < 10 (d) The function that raises 2 to the non-negative integer assigned to the function Domain is the set of non-negative integers (naturals). Range is the powers of 2 (1, 2, 4, 8 ...). Exercise 9 (10 Points) Give an example of a function from Z to N that is (a) One-to-one but not onto. f : Z → N : f(x) = � 2x + 2 if x ≥ 0 −2x − 1 if x < 0 0 has no preimage (b) Onto but not One-to-One. f : Z → N : f(x) = |x| for anyx, f(x) = f(−x) (c) Both onto and one-to-one (but different from the identity function). f : Z → N : f(x) = � 2x if x ≥ 0 −2x − 1 if x < 0 (d) Neither one-to-one nor onto. f : Z → N : f(x) = 0 5 Exercise 10 (10 Points) Let f(x) = ax2 + bx + c and g(x) = 3dx − 2e, where a, b, c, d and e are constants. Determine necessary and sufficient conditions on the constants a, b, c, d and e so that f ◦ g = g ◦ f. Solution: f ◦ g = a(3dx − 2e)2 + b(3dx − 2e) + c = 9ad2x2 + (3bd − 12ade)x + (4ae2 − 2be + c) g ◦ f = 3d(ax2 + bx + c) − 2e = 3adx2 + 3bdx + (3cd − 2e) Therefore, if f ◦ g = g ◦ f, then the following should be equal: • 9ad2 = 3ad → (3d = 1 ∨ a = 0 ∨ d = 0) • 3bd − 12ade = 3bd → (12ade = 0) ↔ (a = 0 ∨ d = 0 ∨ e = 0) • (4ae2 − 2be + c) = (3cd − 2e) → 2e(2ae − b + 1) = c(3d − 1) Exercise 11 (10 Points) Determine whether the symmetric difference is associative; that is, if A, B, and C are sets, does it follow that A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C? Note: The symmetric difference of A and B, denoted by A⊕B, is the set containing those elements in either A or B, but not in both A and B. Solution: A B C A ⊕ B B ⊕ C A ⊕ (B ⊕ C) (A ⊕ B) ⊕ C 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 1 1 0 1 1 1 0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 0 0 1 1 0 0 1 0 0 1 1 1 0 0 1 1 Exercise 12 (10 Points) Write a closed form notation for the following summations (a) 2n � i=1 (1 − 1i) = 2n � i=1 (1 − 1) = 2n � i=1 0 = 0 (b) n � i=1 (3i − 2i) = n � i=1 3i − n � i=1 2i = 3 · 3n − 1 2 − 2 · (2n − 1) 6 (c) n � i=1 m � j=1 ij = n � i=1 i m � j=1 j = n(n + 1) 2 m(m + 1) 2 = n(n + 1)m(m + 1) 4 (d) n � i=1 m � j=1 (2i + 3j) = n � i=1   m � j=1 2i + m � j=1 3j   = n � i=1  2i m � j=1 1 + 3 m � j=1 j   = n � i=1 � 2im + 3m(m + 1) 2 � = n � i=1 (2im) + n � i=1 �3m(m + 1) 2 � = 2m n � i=1 i + �3m(m + 1) 2 � n � i=1 1 = 2mn(n + 1) 2 + 3m(m + 1)n 2 = 2mn(n + 1) 2 + 3m(m + 1)n 2 = mn(n + 1) + 3m(m + 1)n 2 (e) Compact solution - Can be expanded step by step as in part (d) n � i=1 m � j=1 (2i3 + 3j2) = m n � i=1 2i3 + n m � j=1 3j2 = 2m n � i=1 i3 + 3n m � j=1 j2 = 2m(n2(n + 1)2 4 ) + 3n(m(m + 1)(2m + 1) 6 ) 7 Exercise 13 (10 Points) Write the product notation of C(n, r) = n! r!×(n−r)! Solution: C(n, r) = n! r! × (n − r)! = n · (n − 1) · ... · (n − r + 1) r! �n i=1 i �r j=1 j × �n−r k=1 k = �n i=n−r+1 i �r j=1 j = r � i=1 n − i + 1 i Exercise 14 (10 Points) Prove or disprove each of these statements about the floor and ceiling functions. (a) ⌊⌈x⌉⌋ = ⌈x⌉ for all real numbers x. We have ⌈x⌉ ∈ Z By definition. Also, ⌊z⌋ = z for any z ∈ Z Therefore ⌊⌈x⌉⌋ = ⌈x⌉ for all reals. (b) ⌊x + y⌋ = ⌊x⌋ + ⌊y⌋ for all real numbers x and y. Take x = 1.5, y = 1.8. ⌊x + y⌋ = 3. ⌊x⌋ + ⌊y⌋ = 2. Disproved by counter-example. (c) � ⌈ x 2⌉ 2 � = � x 4 � for all real numbers x. Every real number can be written as 4q + r where q ∈ Z and 0 ≤ r < 4 (r ∈ R).   � 4q+r 2 � 2   = �� 2q + r 2 � 2 � = � 2q + � r 2 � 2 � = � q + � r 2 � 2 � = q + �� r 2 � 2 � since q ∈ Z Also: �4q + r 4 � = � q + r 4 � = q + �r 4 � Therefore, the property holds for all real numbers if and only if � ⌈ r 2⌉ 2 � = � r 4 � holds for the real numbers in [0, 4). Take the case where x = 0. Both sides will be 0, so it holds. Take the case 0 < x ≤ 2: �� x 2 � 2 � = �1 2 � = 1 and �x 4 � = 1 8 Finally, take the case where 2 < x < 4: �� x 2 � 2 � = �2 2 � = 1 and �x 4 � = 1 Therefore, it holds for all real numbers in [0, 4) (Exhaustive Proof), implying that the original statement holds for all real numbers. (d) ⌊ � ⌈x⌉⌋ = ⌊√x⌋ for all real numbers x. Take x = 3.1. ⌊ � ⌈x⌉⌋ = ⌊ � ⌈3.1⌉⌋ = ⌊ √ 4⌋ = 2. Note that 1.82 = 3.24 > 3.1. Therefore √ 3.1 < 1.8, ⌊ √ 1.8⌋ ≤ 1 < 2. Disproved by a Counter example. (e) ⌊x⌋ + ⌊y⌋ + ⌊x + y⌋ ≤ ⌊2x⌋ + ⌊2y⌋ for all real numbers x and y. Take x = a + α, and y = b + β, where a, b ∈ Z and 0 ≤ α, β < 1 ⌊x⌋ + ⌊y⌋ + ⌊x + y⌋ ≤ ⌊2x⌋ + ⌊2y⌋ ↔ ⌊a + α⌋ + ⌊b + β⌋ + ⌊a + α + b + β⌋ ≤ ⌊2a + 2α⌋ + ⌊2b + 2β⌋ ↔ a + ⌊α⌋ + ⌊β⌋ + a + b + ⌊α + β⌋ ≤ 2a + ⌊2α⌋ + 2b + ⌊2β⌋ since a, b ∈ Z ↔ ⌊α⌋ + ⌊β⌋ + ⌊α + β⌋ ≤ +⌊2α⌋ + ⌊2β⌋ Now we can use proof by cases (6 cases, but can be reduced to 4 without loss of generality): 1. (0 ≤ α < 0.5) ∧ (0 ≤ β < 0.5) → • ⌊α⌋ = ⌊β⌋ = 0 • 0 ≤ α + β < 1 → ⌊α + β⌋ = 0 • 0 ≤ 2α, 2β < 1 → ⌊2α⌋ = ⌊2β⌋ = 0 And therefore 0 ≤ 0 which is true 2. (0.5 ≤ α < 1) ∧ (0.5 ≤ β < 1) → • ⌊α⌋ = ⌊β⌋ = 0 • 1 ≤ α + β < 2 → ⌊α + β⌋ = 1 • 1 ≤ 2α, 2β < 2 → ⌊2α⌋ = ⌊2β⌋ = 1 And therefore 0 + 1 ≤ 1 + 1 → 1 ≤ 2 which is true 3. w.l.o.g, (0 ≤ α < 0.5) ∧ (0.5 ≤ β < 1) ∧ (α + β ≥ 1) → • ⌊α⌋ = ⌊β⌋ = 0 • 1 ≤ α + β < 2 → ⌊α + β⌋ = 1 • 0 ≤ 2α < 1 → ⌊2α⌋ = 0 • 1 ≤ 2β < 2 → ⌊2β⌋ = 1 And therefore 0 + 1 ≤ 0 + 1 → 1 ≤ 1 which is true 9 4. w.l.o.g, (0 ≤ α < 0.5) ∧ (0.5 ≤ β < 1) ∧ (α + β < 1) → • ⌊α⌋ = ⌊β⌋ = 0 • 0 ≤ α + β < 1 → ⌊α + β⌋ = 0 • 0 ≤ 2α < 1 → ⌊2α⌋ = 0 • 1 ≤ 2β < 2 → ⌊2β⌋ = 1 And therefore 0 + 0 ≤ 0 + 1 → 0 ≤ 1 which is true Therefore, it has been proven by cases that ⌊x⌋ + ⌊y⌋ + ⌊x + y⌋ ≤ ⌊2x⌋ + ⌊2y⌋ for all real numbers x and y 10