CMPS 211 Homework Assignment 06 Solution, Fall 2014

American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 2014 Assignment 6 Solution 1 Exercise 1 (10 points) Let A, B, and C be sets. Show that a) (A∩B) ⊆ (A∪B∪C). {x|xϵ(A ∩ 𝐵)} ( 𝐴𝑠𝑠𝑢𝑚𝑝𝑡𝑖𝑜𝑛) => {𝑥|𝑥ϵA xϵB} (Definition of intersection) => {𝑥|𝑥ϵA xϵB} => {𝑥|𝑥ϵA  xϵB  xϵC} => {𝑥|xϵ(A ∪ B ∪ C)} b) (A∩B∩C) ⊆ (A∩B). {x|xϵ(A ∩ 𝐵 ∩ 𝐶)} ( 𝐴𝑠𝑠𝑢𝑚𝑝𝑡𝑖𝑜𝑛) => {𝑥|𝑥ϵA xϵBxϵC} (Definition of intersection) => {𝑥|𝑥ϵA xϵB}(Simplification) => {x|xϵ(A ∩ 𝐵)} c) (A−B)−C ⊆ A−C. {𝑥|𝑥ϵ(𝐴 − 𝐵) − 𝐶}(𝐴𝑠𝑠𝑢𝑚𝑝𝑡𝑖𝑜𝑛) => {𝑥|𝑥ϵA  x ∉ B x ∉ C} (Definition of difference) => {𝑥|𝑥ϵA  x ∉ C} (Simplification) => {𝑥|𝑥ϵ (𝐴 − 𝐶)} d) (A∩C)∩(B−C) = ∅. (𝐴 ∩ 𝐶) ∩ (𝐵 − 𝐶) = (𝐴 ∩ 𝐶) ∩ (𝐵 ∩ 𝐶̅) = (𝐴 ∩ 𝐵) ∩ (𝐶 ∩ 𝐶̅) = (𝐴 ∩ 𝐵) ∩ (𝐶𝑜𝑚𝑝𝑙𝑒𝑚𝑒𝑛𝑡 𝑙𝑎𝑤) = (𝐷𝑜𝑚𝑖𝑛𝑎𝑡𝑖𝑜𝑛 𝑙𝑎𝑤) Exercise 2 (10 points) American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 2014 Assignment 6 Solution 2 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) American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 2014 Assignment 6 Solution 3 Can you conclude that A = B if A, B, and C are sets such that a) A∪C = B∪C? No, Counter example: Let A={1,2,3,4,5}, B={1,2,3,4}, C={5} AUC = {1,2,3,4,5} BUC = {1,2,3,4,5} We get, AUC=BUC but A does not equal B. b) A∩C = B∩C? No, Counter example: Let A={1,2,3} B={1,2} C={1} A∩C={1}= B∩C but A does not equal B. c) A∪C = B∪C and A∩C = B∩C? a. Yes, Suppose, x ϵ A: If x ϵ C, x ϵ A∩C => x ϵ B∩C => x ϵ B If x ∉ C, x ϵ AUC => x ϵ BUC => x ϵ B  A ⊆ B  Then, do the same starting form x ϵ B until you get B⊆ A Therefore, A=B. d) A-C = B-C and C-A = B-A ? No, Let A= {1,2,3}, B={1,4,3,6}, C={2,4,6} A-C=B-C= {1,3} C-A={4,6}= B-A But A and B are not equal. American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 2014 Assignment 6 Solution 4 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 Domain: - Range= -{-1} b) The function that assigns to each nonnegative integer its first digit Domain= Range={0,1,2,3,4,5,6,7,8,9} c) The function that assigns to a bit string the number of bits in the string Domain: set of binary strings Range= d) The function that assigns to a bit string the number of zero bits in the string Domain: set of binary strings Range= Exercise 5 (10 points) Give an example of a function from N to N that is a) one-to-one but not onto. F(n)=n+2 is one-to-one but not onto since 0 and 1 have no pre-images in . b) onto but not one-to-one. F(n)=⌊n/3⌋ is onto but not one-to-one since f(0)=f(1)=f(2). c) both onto and one-to-one (but different from the identity function). F(n)={𝑛 + 1 𝑖𝑓 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛 𝑛 − 1 𝑖𝑓 𝑛 𝑖𝑠 𝑜𝑑𝑑 d) neither one-to-one nor onto. F(n)=n! since prime numbers cannot have a pre-image and since f(0)=f(1)=1. Exercise 6 (10 points) American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 13/14 5 Determine whether each of these functions is a bijection from R to R. a) f(x)=((5x-3)2-(3x-5)2)/(4x+4) Not a bijection, since there is the condition x ≠ -1 b) f(x)= (x+3)/(x+4) Not a bijection, since there is the condition x ≠ -4 c) f(x)= −4x2+5 Not a bijection since neither one-to-one nor onto d) f(x)=x7+3 Bijection Exercise 7 (10 points) Let f(x) = ax2 +bx+c and g(x) = dx2 +ex+f, where a, b, c, d, e and f are constants. Determine necessary and sufficient conditions on the constants a, b, c, d, e and f so that f ◦ g = g ◦ f. f○g(x)= f(g(x))= a(cx+d)+b= acx+ad+b g○f(x)=g(f(x))=c(ax+b)+d=acx+bc+d Then, f○g(x)= g○f(x) if ad+b=bc+d… 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). Assume x ϵ f-1(S)Uf-1(R ) then f(x) ϵ S or f(x) ϵ R.  f(x) ϵ (SUR)  x ϵ F-1(SUR)  f-1(S)Uf-1(R ) ⊆ F-1(SUR) now, assume x ϵ F-1(SUR) ,then f(x) ϵ (SUR)  f(x) ϵ S or f(x) ϵ R  x ϵ f-1(S)Uf-1(R )  F-1(SUR) ⊆ f-1(S)Uf-1(R ) American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 13/14 6 Therefore, F-1(SUR)= f-1(S)Uf-1(R ) b) f−1(R∩S) = f−1(S)∩f−1(R). Assume ∈ 𝒇−𝟏(𝑺) ∩ 𝒇−𝟏(𝑹) , then 𝒇(𝒙) ∈ 𝑺 𝒂𝒏𝒅 𝒇(𝒙) ∈ 𝑹  𝒇(𝒙) ∈ (𝑺 ∩ 𝑹)𝒙  ∈ 𝒇−𝟏(𝑺 ∩ 𝑹)  𝒇−𝟏(𝑺) ∩ 𝒇−𝟏(𝑹) ⊆ 𝒇−𝟏(𝑺 ∩ 𝑹) Let 𝑺𝒖𝒑𝒑𝒐𝒔𝒆 𝒙 ∈ 𝒇−𝟏(𝑺 ∩ 𝑹), then 𝒕𝒉𝒆𝒏 𝒇(𝒙) ∈ 𝑺 ∩ 𝑹  𝒇(𝒙) ∈ 𝑺 ∩ 𝑹  𝒇(𝒙) ∈ 𝑺 𝒂𝒏𝒅 𝒇(𝒙) ∈ 𝑹  𝒙 ∈ 𝒇−𝟏(𝑺) 𝒂𝒏𝒅 𝒙 ∈ 𝒇−𝟏(𝑹)  𝒙 ∈ 𝒇−𝟏(𝑺) ∩ 𝒇−𝟏(𝑹)  𝒇−𝟏(𝑺 ∩ 𝑹) ⊆ 𝒇−𝟏(𝑺) ∩ 𝒇−𝟏(𝑹) Therefore, 𝒇−𝟏(𝑺 ∩ 𝑹) = 𝒇−𝟏(𝑺) ∩ 𝒇−𝟏(𝑹) 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. True Proof: Let n=⌊𝒙⌋, 𝒘𝒉𝒆𝒓𝒆 𝒏 ≤ 𝒙 < 𝒏 + 𝟏 such than n∈ Then ⌈⌊x⌋⌉=⌈n⌉=n American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 13/14 7 b) ⌈x+y⌉=⌈x⌉+⌈y⌉ for all real numbers x and y. False Counter example: Let x=0.5 and y=1.5 ⌈x+y⌉= ⌈0.5+1.5⌉= ⌈2⌉=2 ⌈x ⌉= ⌈0.5⌉=1 ⌈y⌉= ⌈1.5⌉=2 ⌈x ⌉+⌈y⌉=3 which is not equal to ⌈x+y⌉ c) ⌈⌈x/3⌉/2⌉=⌈x/6⌉ all real numbers x. a. ⌈⌈x/3⌉/2⌉=⌈x/6⌉ True Proof: Let x = 6n+k such that n is an integer and 0≤k<6 If k=0: We have x=6n  ⌈⌈x/3⌉/2⌉= n= ⌈x/6⌉ If 0<k≤3: ⌈x/3⌉=⌈(6n+k)/3⌉=⌈2n+k/3⌉=2n+1 (since 𝟎 <k/3≤ 𝟏 and 2n is an integer) ⌈⌈x/3⌉/2⌉=⌈(2n+1)/ 2⌉=⌈n+1/ 2⌉=n+1 =⌈x/6⌉ If 3<k<6: ⌈x/3⌉= 2n+2 ⌈⌈x/3⌉/2⌉=n+1=⌈x/6⌉ d) ⌊√⌈x⌉⌋ = ⌊√𝑥⌋ for all positive real numbers x. False Counter example: Let X=3.1 ⌊√ ⌈x⌉⌋ =⌊√ 4 ⌋=2 ⌊√ x⌋=⌊√3.1⌋=⌊1.76⌋=1 They are not equal American University of Beirut Department of Computer Science CMPS 211 – Discrete Mathematics – Fall 13/14 8 f) ⌈x⌉+⌈y⌉+⌈x+2y⌉≤⌈2x⌉+⌈3y⌉ for all real numbers x and y . False Counter example: Let x=2.1 Y=1.1  ⌈x⌉+⌈y⌉+⌈x+2y⌉=⌈2.1⌉+⌈1.1⌉+⌈2.1+2*1.1⌉=3+2+⌈4.3⌉=3+2+5=10 And ⌈2x⌉+⌈3y⌉=⌈2*2.1⌉+⌈3*1.1⌉=⌈4.2⌉+⌈3.3⌉=5+4=9 <⌈x⌉+⌈y⌉+⌈x+2y⌉