CVM University

ADIT GCET MBIT

102040405 Discrete Mathematics

Functions
1 For the function f if f(a) = f(b) implies that a = b for all a and b in the domain of f then f
is ---
(a) One-to-many (b) One-to-one (c) Many-to-many (d) Many-to-one
2 The function f(x) = x+1 from the set of integers to itself is ---
(a) injective but not surjective (b) bijective (c) not injective but surjective (d)
neither injective nor surjective
3 Which of the following function f: Z X Z → Z is not onto?
(a) f(a, b) = a + b (b) f(a, b) = a (c) f(a, b) = |b| (d) f(a, b) = a – b
4 Let f and g be the function from the set of integers to itself, defined by f(x) = 2x + 1 and
g(x) = 3x + 4. Then the composition of fog is ----
(a) 6x + 9 (b) 6x + 7 (c) 6x + 6 (d) 6x + 8
5 The inverse of function ( ) is
(a) ( ) ( ) (b) ( ) ( ) (c) ( ) ( )
(d) ( )
6 For the function ( ) ⌊ ⌋ the set ( ) is ---
(a) * + (b) * +
(c) * + (d) * +
7 Domain of the function ( ) √ is ---
(a) ( ) (b) ( ) (c) , ) (d)
8 Domain of the function ( ) is ---
(a) ( ) (b) ( ) (c) , ) (d)
9 Range of the function that assigns the last two bits of a bit string of length 2 or greater
to that string is ---
(a) {1, 0} (b) {10, 01} (C) {00, 01, 10, 11} (D) {11, 00}
10 Which one of the following is a function from to ?
(a) ( ) (b) ( ) √ (c) ( ) √ (d) ( ) √
11 Let f be a function from the set of all bit strings to the set of integers such that f(S) = the
number of 1 bits in S. What is the value of f(0000) is ---
(a) 0 (b) 4 (c) 2 (d) not a function
12 The function that assigns the next integer to a positive integer has the range ---
(a) (b) (c) (d)
13 The value of ⌊ ⌈ ⌉⌋
(a) 0 (b) 1 (c) 2 (d) -1
14 Let be the function from to defined by ( ) . The set (* +) = ---
(a) (b) {1} (c) {-1, 1} (d) {0, 1}
15 The number of bytes required to encode 1001 bits of data is ---
(a) 125 (b) 126 (c) 2 (d) 4
1 Let and be functions from to such that ( ) and ( ) . What
are the functions and ?
2 Why the function ( ) is not one-to-one?
3 Determine whether the function ( ) from the set of real numbers to itself is
one-to-one. Is it onto?
4 Let and be the functions from the set of integers to the set of integers defined by
( ) and ( ) . What is the composition of and ? What is the
composition of and ?
We have ( ) ( ( )) ( ) ( ) ( )
5 Data stored on a computer disk or transmitted over a data network are usually
represented by a string of bytes. Each byte is made up of 8 bits. How many bytes are
required to encode 100 bits of data?
⌈ ⌉ ⌈ ⌉ bytes are required.
6 In asynchronous transfer mode (ATM), 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?
In 1 minute, this connection can transmit 500,000 60 = 30,000,000 bits. Each ATM
cell is 53 bytes long, which means that is 53 8 = 424 bits long. Consequently,
⌊ ⌋ ATM cells can be transmitted in 1 minute over a 500 kilobit per
second connection.
7 Find the domain and the range of the following:
(1) the function that assigns to each nonnegative integer its last digit.
Some images to get an idea
f(0) = Last digit of 0 = 0, f(11) = 1, f(122) = 2, etc
Domain: Set of nonnegative integers = {0, 1, 2, 3, …} =
Range: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
(2) the function that assigns to each bit string the number of ones minus the number of
zeros
Some images to get an idea
f(10) = 1 – 1 = 0, f(001) = 1 – 2 = -1, f(110)= 2-1 = 1, f(111) = 3 – 0 = 3 etc
If S is a bit string having n one’s and no zero then f(S) = n – 0 = n
If S is a bit string having no one’s and n zeros then f(S) = 0 – n = -n
If S is a bit string having same number of one’s and zero’s then f(S) = 0
Therefore, every integer has a preimage.
Domain: Set of all bit strings
Range:
(3) the function that assigns the number of bits left over when a bit string is split into
bytes (which are blocks of 8 bits)
Some images to get an idea
f(10100011) = 0, f(101000001) = 1, f(000001111101) = 4 etc
Domain: Set of all bit strings
The number of leftover bits can be any whole number from 0 to 7 (if it were more, then
we could form another byte)
Range: {0, 1, 2, 3, 4, 5, 6, 7}
(4) the function that assigns to each positive integer the largest perfect square not
exceeding this integer.
Some images to get an idea
f(1) = 1, f(3) = 1, f(4) = 4, f(7) = 4, f(26) = 25, etc
Domain:
Only perfect squares can be function values, and clearly every positive perfect square is
 possible.
Range: {1, 4, 9, 16, 25, 36 …}
(5) the function that assigns to each pair of positive integers the maximum of these two
integers
Some images to get an idea
f(1,1) = 1, f(1,2) = 2, f(1,3) = 3, f(5,2) = 5, f(2,2) = 2, f(3,3) = 3 etc
Domain:
The maximum is again a positive integer, and all positive integers are possible
maximums (by letting the two elements of the pair be the same)
Range:
8 Determine whether each of the following functions from is one-to-one, onto
(1) ( )
It seems is one-to-one and onto (bijective). Let we prove it.
For integers
let ( ) ( )
is one-to-one
To check onto let then
Now, ( ) ( ) ( )
Therefore, every has a preimage in . Hence, is onto.

(2) ( )
Note that, ( ) and ( )
Thus, ( ) ( ) but
is not one-to-one
We can see that ( ) for any . Therefore, .
is not onto.

(3) ( )
For integers
let ( ) ( )
is one-to-one
We can see that ( ) for any . Therefore, .
is not onto.

(4) ( ) ⌈ ⌉
Note that ( ) ⌈ ⌉ ( ) ⌈ ⌉
Thus, ( ) ( ) but
is not one-to-one
To check onto let then
Now, ( ) ( ) ⌈ ⌉
Therefore, every has a preimage in . Hence, is onto.

9 Determine whether is onto if

(1) ( )
For we have ( )
Now, ( )
Therefore, every has a preimage in . Hence, is onto.
 (2) ( )
We can see that ( ) for any as 2 cannot be expressed as a
difference of two perfect square integers.
is not onto.

(3) ( )
For we have ( )
Now, ( )
Therefore, every has a preimage in . Hence, is onto.

(4) ( )
Here, ( )
( ) so, all positive integers as images
( ) so, all negative integers as images
Therefore, every has a preimage in . Hence, is onto.

(5) ( )
Show that is onto.

(6) ( )
Show that is not onto.
10 Let * +. Find ( ) if
( ) ⌈ ⌉
( ) ⌈ ⌉ ( ) ( ) ⌈ ⌉ ( ) ( ) .
So, ( ) * +

11 Suppose that is a function from to and is a function from to .

(a) Show that if both and are one-to-one, then is also one-to-one.
Here, . Let, be such that
( ) ( ) ( ( )) ( ( )). Since, is one-to-one we have
( ) ( ). Again, since is one-to-one we have . Hence, is one-to-
one.
(b) Show that if both and are onto, then is also onto.
Do it yourself!
12 Find and , where ( ) and ( ) , are functions from to .
( ) ( ( )) ( ) ( ) .
Find
13 Find and given in Example 12.
14 Show that the function ( ) from to is invertible where and are
constants, with , and find the inverse of .
Let we first prove that is bijective.
Let be such that
( ) ( )
is one-to-one
Let
( ) ( )
 Then, be such that ( ) ( ) ( )
Therefore, every y has a preimage in . Hence, is onto.
Thus, is one-to-one and onto. So, is bijective. Hence, is invertible.
From (*) we can write as ( ) .
15 Let be a function from the set to the set . Let be a subset of . We define the
inverse image of as the set of all pre images of elements of
( ) * ( ) +
(1) Let be the function from to defined by ( ) . Find
(a) (* +) (b) (* +)
(a) We need to check those elements of whose image under the given function is in the
set * +.
Therefore, (* +) * +
(b) There is no integer whose image under the given function lies in the set * +.
Therefore, (* +)

(2) Let be the function from to defined by ( ) ⌊ ⌋. Find

(a) (* +) (b) (* +) (c) (* +)
(a) We know that if then ( ) . Hence, (* +) , )
(c) We know that range of is . There is no element in whose image is in the set
( ). So, (* +)
(b) Find yourself!