CMPS 211 Homework Assignment 6, Fall 2014

American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Spring 13/14 Assignment 6 1 Please solve the following exercises and submit BEFORE 8:00 am of Tuesday 28th, October. Exercise 1 (10 points) Let A, B, and C be sets. Show that a) (A∩B) ⊆ (A∪B∪C). b) (A∩B∩C) ⊆ (A∩B). c) (A−B)−C ⊆ A−C. d) (A∩C)∩(B−C) = ∅. e) (B−A)∪(A−C) = (B∪A)−C. Exercise 2 (10 points) Draw the Venn diagrams for each of these combinations of the sets A, B, and C. a) A∪ (B∩C) b) A∩B∩C c) (A−B)∪(B−C)∪(C−A) Exercise 3 (10 points) Can you conclude that A = B if A, B, and C are sets such that a) A∪C = B∪C? b) A∩C = B∩C? c) A∪C = B∪C and A∩C = B∩C? d) A-C = B-C and C-A = B-A ? American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Spring 13/14 Assignment 6 2 Exercise 4 (10 points) Find the domain and range of these functions. Note that in each case in order to find the domain, determine the set of elements assigned values by the function. a) The function that assigns the next smallest integer to a negative integer b) The function that assigns to each nonnegative integer its first digit c) The function that assigns to a bit string the number of bits in the string d) The function that assigns to a bit string the number of zero bits in the string Exercise 5 (10 points) Give an example of a function from N to N that is a) one-to-one but not onto. b) onto but not one-to-one. c) both onto and one-to-one (but different from the identity function). d) neither one-to-one nor onto. Exercise 6 (10 points) Determine whether each of these functions is a bijection from R to R. a) f(x)=((5x-3)2-(3x-5)2)/(4x+4) b) f(x)= (x+3)/(x+4) c) f(x)= −4x2+5 d) f(x)=x7+3 Exercise 7 (10 points) Let f(x) = ax+b and g(x) = cx+d, where a, b, c, d are constants and both f and g are from R to R. Determine the necessary and sufficient conditions on the constants a, b, c, and d so that f ◦ g = g ◦ f. American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 13/14 3 Exercise 8 (10 points) Let f be a function from A to B. Let R and S be subsets of B. Show that a) f−1(S∪R) = f−1(S)∪f−1(R). b) f−1(R∩S) = f−1(S)∩f−1(R). Exercise 9 (10 points) Show that if x is a real number and m is an integer, then ⌊ x + m ⌋= ⌊ x ⌋+ m. Exercise 10 (10 points) Prove or disprove each of these statements about the floor and ceiling functions. a) ⌈⌊x⌋⌉=⌊x⌋ for all real numbers x. b) ⌈x+y⌉=⌈x⌉+⌈y⌉ for all real numbers x and y. c) ⌈⌈x/3⌉/2⌉=⌈x/6⌉ all real numbers x. d) ⌊ ⌈x⌉⌋ = ⌊ 𝑥⌋ for all positive real numbers x. f) ⌈x⌉+⌈y⌉+⌈x+2y⌉≤⌈2x⌉+⌈3y⌉ for all real numbers x and y .