1 Lecturer: Dr Nguyen Hieu Thao Email: thao.nguyenhieu@rmit.edu.vn
Tutorial Solutions: Functions
(2024C, Week 4)1
1. Determine whether each of the sets is a function from X = {1, 2, 3, 4} to Y = {a, b, c, d}. If it is a function, find its domain and range, draw its arrow diagram, and determine if it is one-to-one, onto, or both.
(a) {(1, a), (2, a), (3, c), (4, b)} is a function.
(i) It is not injective since two distin-
guished elements 1 and 2 in X have the same value a in Y .
(ii) It is not surjective since d does not
belong to its range.
(iii) The diagram of this function is beside.
(b) {(1, c), (2, a), (3, b), (4, c), (2, d)} is not a function since there are two correspondences for the input 2 (a and d).
2. Draw the graph of the function f (x) = x − bxc, whose domain and codomain are the set of real numbers.
Solution. Note that the function f (x) = x − bxc is periodic with period 1. Consider, for example, the interval [0, 1), we have f (x) = x. Duplicating the graph of f on [0, 1) to all the periodic intervals, we obtain the graph of f as below.
1 Most of the content of this document is taken from the book [1]. 2
3. Determine whether each function is one-to-one, onto, or both. The domain and codomain are the set of integers. Justify your answers.
(a) The function f (n) = dn/2e is surjective, but not injective.
(i) It is surjective because for any integer n, we have f (2n) = d2n/2e = n. That is, the range of f contains all integers. (ii) It is not injective because 1 6= 2, but f (1) = d1/2e = 1 = d1e = f (2). (b) The function f (n) = 2n is injective, but not surjective. (i) It is injective because whenever n 6= m, we have f (n) = 2n 6= 2m = f (m). (ii) It is not surjective because odd integers do not belong to the range of f which contains only even integers (2n, n ∈ Z).
4. The function f (x) = 3 log2 x is one-to-one on its domain X - the set of positive real numbers. By letting Y = range(f ), we obtain a bijection from X to Y . Find its inverse.
Solution. The inverse function is f −1 (y) = 2y/3 . Justify the result for yourself.
5. Given g = {(1, b), (2, c), (3, a)}, a function from X = {1, 2, 3} to Y = {a, b, c, d}, and f = {(a, x), (b, x), (c, z), (d, w)}, a function from Y to Z = {w, x, y, z}, write f ◦ g as a set of ordered pairs and draw the arrow diagram of f ◦ g.
Solution. The composition function f ◦ g as a set of
ordered pairs is
f ◦ g = {(1, x), (2, z), (3, x)} .
The arrow diagram of f ◦ g is beside.
6. Let f (n) = 2n + 1 and g(n) = 3n − 1 be functions from the set of positive integers to itself. Find the compositions f ◦ f , g ◦ g, f ◦ g, and g ◦ f . Solution. The composition functions are below.
(i) f ◦ f (n) = 2(2n + 1) + 1 = 4n + 3 (iii) f ◦ g(n) = 2(3n − 1) + 1 = 6n − 1
(ii) g ◦ g(n) = 3(3n − 1) − 1 = 9n − 4 (iv) g ◦ f (n) = 3(2n + 1) − 1 = 6n + 2
7. Decompose the function f (x) = log2 (x2 + 2) into simpler functions.
Solution. It can be decomposed as f = f1 ◦ f2 ◦ f3 , where
f3 (x) = x2 , f2 (y) = y + 2, and f1 (z) = log2 (z).
Justify the result for yourself.
3
8. Consider the function f (x) = 4x( mod 5) from X = {0, 1, 2, 3, 4} to X. Write f as a set of ordered pairs and draw the arrow diagram of f . Is f one-to-one? Is f onto? Explain your answers.
Solution.
(i) As a set of ordered pairs:
f = {(0, 0), (1, 4), (2, 3), (3, 2), (4, 1)} .
(ii) The arrow diagram of f is beside.
(iii) f is both one-to-one and onto. Explain the
answers to yourself.
9. For the following hash function, show how the data would be inserted in initially empty cells in the given order. Use the collision resolution policy mentioned in Notes Week 4.
h(x) = x mod 11; cells indexed 0 to 10; data: 53, 13, 281, 743, 377, 20, 10, 796.
Solution. Recall that the collision resolution policy is to look for the next unoccupied cell. The hash values are below.
53 13 281 743 377 20 10 796
9 2 6 7 3 10 0 4
10. Let g be a function from X to Y and let f be a function from Y to Z. For each statement, if the statement is true, prove it; otherwise, give a counterexample.
(a) If f and g are onto, then f ◦ g is onto. The statement is True.
Proof. Take any z ∈ Z. Since f is onto, there is y ∈ Y such that f (y) = z. Since g is onto and y ∈ Y , there is x ∈ X such that g(x) = y. That is, f ◦ g(x) = z. Thus, for every z ∈ Z, there is x ∈ X such that f ◦ g(x) = z. That is, f ◦ y is onto.
(b) If f ◦ g is one-to-one, then f is one-to-one. The statement is False.
Counterexample. Consider the function g : {1} → {a, b} given by g(1) = a and the function f : {a, b} → {α} given by f (a) = f (b) = α. Then the composition function f ◦ g : {1} → {α} with f ◦ g(1) = α is one-to-one, but f is not one-to-one. 4
11. In asynchronous transfer mode (ATM) (a communication protocol used on backbone net- works), data are organized into cells of 53 bytes. How many ATM cells can be transmitted in 1 minute over a connection that transmits data at the rate of 500 kilobits per second? Solution.
(i) 53 bytes/cell = 53 · 8 = 424 bits/cell.
(ii) In 60 seconds, 60 · 500, 000 = 30, 000, 000 bits can be transmitted.
(iii) Thus, b30, 000, 000/424c = b70, 754.717c = 70, 754 cells can be transmitted.
12. A JPEG file stores image data in blocks of 8 × 8 pixels. How many blocks are needed to store a JPEG image whose dimensions are 4753 × 3747 pixels? Solution.
(ii) Vertically, it requires ceiling(3, 747/8) = ceiling(468.375) = 469 blocks.
(iii) Total number of blocks required is 595 · 469 = 279, 055 blocks.
13. Consider the set X = {1, 2, . . . , 10}. Define the function f from the power set of X to the set of positive integers. For each subset A of X, the function f returns the cardinality of A. Justify yours answers.
(a) f is not injective. For example, {A} = {1} 6= {B} = {2}, but f (A) = f (B) = 1.
(b) f is not surjective since 11 ∈
/ range(f ) which ranges from 0 to 10.
(c) X is a proper subset of range(f ) since X ⊂ range(f ) and 0 ∈ range(f ) \ X.
14. Define the function f : R2 → R2 by f (x) = Ax for every x ∈ R2 , where
1 2 A= . 2 4
(a) Calculate f (x), where x = (−3, −6)T (column vector).
Solution. f (x) = Ax = (−15, −30)T .
(b) Is f an injective, surjective, bijective function? Explain/prove your answers.
Solution. f is not injective since f ((2, 1)T ) = f ((0, 2)T ) while (2, 1)T 6= (0, 2)T . f is not surjective since f −1 ((1, 1)T ) = ∅. As a consequence, f is not bijective. 5
15. Define the function f : R3 → R3 by f (a) = Aa (matrix-vector multiplication) for every
a ∈ R3 , where 1 2 3
A = 0 −1 1 . 0 0 1 (a) Calculate f (a) and f −1 (a), where a = (1, 1, 1)T (column vector). 1 2 3 1 6 f (a) = Aa = 0 −1 1 1 = 0 . 0 0 1 1 1 To compute f −1 (a), we solve the equation f (x) = a for the unknown x. Indeed, 1 2 3 x1 1 f (x) = Ax = a ⇐⇒ 0 −1 1 x2 = 1 0 0 1 x3 1 x1 + 2x2 +3x3 = 1 x1 = −2 ⇐⇒ −x2 +x3 = 1 ⇐⇒ x2 = 0 . x3 = 1 x3 = 1
