NYU, Tandon School Bridge HW 5 - Google Docs

Question 1: Solve the following questions from the discrete Math zybook: A. Exercise 4.1.3, sections b, c b) Solution: f(x) is not a well-defined function from R to R. x = +2 & -2. The function is not defined. c) Solution: f(x) is a function from R to R because for every , there is . Range: B. Exercise 4.1.5, sections b, d, h, i, l b) Let A = {2, 3, 4, 5}. f: A Z such that f(x) = x 2 Solution: f(x) = {4, 9, 16, 25} d) f: {0,1} 5 Z . For x ∈ {0,1} 5 , f(x) is the number of 1's that occur in x. For example f(01101) = 3, because there are three 1's in the string "01101". Solution: Range of f(x) = {0, 1, 2, 3, 4, 5} h) Let A = {1, 2, 3}. f: A × A Z × Z , where f(x,y) = (y, x). Solution: Range of f(x, y): {(1,1), (1, 2), (1, 3), (1, 4), (2,1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}

i) Let A = {1, 2, 3}. f: A × A Z × Z , where f(x,y) = (x,y+1). Solution: Range of f(x, y): {(1,2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)} l) Let A = {1, 2, 3}. f: P(A) P(A). For X ⊆ A, f(X) = X - {1}. Solution: Range of f(x): {{0}, {2}, {3}, {2, 3}}.

Question 2: Solve the following questions from the discrete Math zybook: A. Exercise 4.2.2, sections c, g, k c) Solution: One - to -One: Yes Onto: No Not Onto example: There is no such that h(x) = 3. Hence, the function is not onto. g) f: Z × Z Z × Z , f(x, y) = (x+1, 2y) Solution: One - to -One: Yes Onto: No Not Onto example: There is no such that 2y = 3. Hence, the function is not onto. k) f: Z + × Z + Z + , f(x, y) = 2 x + y. Solution: One - to -One: No Onto: No Not One to One example: = (1, 5), & = (2, 3), . Since, = when & one-to-one function requires that when . Hence, the function is not one-to-one. Not Onto example: There is no & such that . Hence, the function is not onto.

B. Exercise 4.2.4, sections b, c, d, g b) . The output of f is obtained by taking the input string and replacing the first bit by 1, regardless of whether the first bit is a 0 or 1. For example, f(001) = 101 and f(110) = 110. Solution: One - to -One: No Onto: No Not One to One example: f(000) = 100 & f(100) = 100, also f(010) = 110 &f(110) = 110, since multiple input string lead to the same output string, the function is not one-to-one. Not Onto example: Since 010 is in solution space, the range of solutions does not include any spring starting with 0. Hence, the function is not onto. c) . The output of f is obtained by taking the input string and reversing the bits. For example f(011) = 110. Solution: One - to -One: Yes Onto: Yes d) . The output of f is obtained by taking the input string and adding an extra copy of the first bit to the end of the string. For example, f(100) = 1001. Solution: One - to -One: Yes Onto: No Not Onto example: There is no input string in { } such that the input string = 1100. Hence, the function is not onto.

g) Let A be defined to be the set {1, 2, 3, 4, 5, 6, 7, 8} and let B = {1}. f: P(A) P(A). For X ⊆ A, f(X) = X - B. Recall that for a finite set A, P(A) denotes the power set of A which is the set of all subsets of A. Solution: One - to -One: No Onto: No Not One-to-one example: For X = {1, 2}, f(X) = X-B = {1, 2} - {1} = {2} & X = {2}, f(x) = X -B = {2} -{1} = {2}. Since both X = {1, 2} & X ={2}, which is = to {2}. Hence, the function is not one-to-one. Not Onto example: There is no such that f(X) = X-B = X -{1} = {1}. So, f(X) = {1} in P(A). Hence, the function is not onto.

Question 3: Give an example of a function from the set of integers to the set of positive integers that is: One-to one , but not Onto Solution: Onto, but not one-to-one Solution: One- to -one and onto Solution: Neither one-to-one nor onto Solution:

Question 4: Solve the following questions from the Discrete Math zyBook: A. Exercise 4.3.2, sections c, d, g, i c) Solution: Since the function is a bijection (both one-to-one and onto) , the inverse is well-defined and d) Let A be defined to be the set {1,2,3,4,5,6,7,8}. f:P(A) {0,1,2,3,4,5,6,7,8}. For X ⊆ A , f(X)=|X| . Recall that for a finite set A , P(A) denotes the power set of A which is the set of all subsets of A. Solution: Since the X = {1,2} & X ={1,3} both lead to f(x) = |{1,2}| = |{1,3}| = 2, the function is not one-to-one. Since the function is not bijection, is not well-defined. g) . The output of f is obtained by taking the input string and reversing the bits. For example, f(011)=110. Solution: The function is bijection. . The output of is obtained by taking the input string and reversing the bits. Example, (110) = 011. i) Solution: This function is a bijection. .

B. Exercise 4.4.2, sections b-d b) Evaluate (f ο h)(52) Solution: (f ο h)(52) = = 121. c) Evaluate (g ο h ο f)(4) Solution: (g ο h ο f)(4) = = 16. d) Give a mathematical expression for h ο f. Solution: h ο f =

Question 5: Solve the following questions from the Discrete Math zyBook: A. Exercise 4.4.6, sections c-e c) What is (h ο f)(010)? Solution: h ο f(010) = h(110) = 111 d) What is the range of h ο f? Solution: Range of f: {{110}, {110}, {101}, {111}} Range of h ο f: {{101}, {111}} e) What is the range of g ο f? Solution: Range of f: {{100}, {110}, {101}, {111}} Range of h ο f: {{001}, {011}, {101}, {111}}

B. Exercise 4.4.8, sections c, d c) f ο h Solution: f ο h = = d) h ο f Solution: h ο f = =