Discrete Mathematics

Chapter 3
Functions and Algorithm
 Let A= { 1, 2,3} and B= {4, 5},
R= {(1, 4), (1,5), (3, 5),
Dom (R)= {1,3} and
Range (R)={4, 5}. There are *
relations between A and B.
• A function f from X to Y (in
symbols f : X  Y) is a relation
from X to Y such that Dom(f) =
X and if two pairs (x,y) and 6

(x,y’)  f, then y = y’ 2

Example: f={(a,3),(b,3),(c,5),
(d,1)}
Dom(f) = X = {a, b, c, d},
Range (f) = {1, 3, 5}
f(a) = f(b) = 3, f(c) = 5, f(d) = 1.
 Domain and Range

– Domain of f = X
– Range of f =
{ y | y = f(x) for some x X}  Y
– A function f : X  Y assigns to
each x in Dom(f) = X a unique
element y in Range (f)  Y.
– Therefore, no two pairs in f have
the same first coordinate.
– Y is called Co-domain of f.
 f: R→R, f (x) = x 2

x x2
f
f(-3) = 9 9 is the Image of -3
f(√2) = 2 Some elements of the
codomain are not images of
f(5) = 25 the elements of the domain.
E.g. -1 is an element of the
codomain but is never used.
The range is a subset of the
codomain.
 Examples
1. Let A = {1, 2, 3} and B = {1, 2, 3,
4}. Let f be the function defined in
the following way:
f: A→B, f(1) = 3, f(2) = 2, f(3)
=2
Domain = A ={1 , 2, 3}
Codomain = B = { 1, 2, 3, 4}
Range = subset of B = { 2, 3}
 One-to-one function (Injective)

A function is one-to-one if no two distinct

elements of the domain have the same image.
• A function f : X  Y is one-to-one  for each
y  Y there exists at most one x  X with f(x) = y.

One-to-one= Injective
 Onto function (Surjective)
A function is onto if its range is equal to
its codomain
A function f : X  Y is onto  for each y  Y there
exists at least one x  X with f(x) = y, i.e.
Range(f) = Y.
– Example: The function f(x) = ex from the set of
real numbers to itself is not onto, where
Y = the set of all real numbers.
– However, if Y is restricted to Range(f) = R +, the
set of positive real numbers, then f(x) is onto.
 Bijective functions
A function f : X Y is bijective 
f is one-to-one and onto
– Examples:
• 1. A linear function f(x) = ax + b is a bijective
function from the set of real numbers to itself

• 2. The function f(x) = x3 is bijective from the

set of real numbers to itself.
 (A) (B)
-Not one- -One-to-
to- one one
- Not onto -Not onto

(C) (D)
(E)

-Not one-to- -One-to-one Not a

one function
-Onto
-Onto
 Inverse function
• Given a function y = f(x), the inverse f -1 is
the set {(y, x) | y = f(x)}.

• The inverse f -1 of f is not necessarily a

function.
– Example: if f(x) = x2, then f -1 (4) = 4 = ± 2, not
a unique value and therefore f is not a
function.
• However, if f is a bijective function, it can
be shown that f -1 is a function.
 Composition of functions
• Since functions are special kinds of
relations it is possible to form the
composition of two functions.
• Given that
– g is a function from X to Y, g : X  Y
– f is a function from Y to Z, f: Y  Z
– The function which is the composition of f
with g is denoted by f o g, is a function
from X to Z.
 Compositions of functions
f○g

A B C
g f

g(a) f(a)

a f(g(a))
g(a)

(f ○ g)(a)
 Compositions of functions
Let f(x) = 2x+3 f○g
Let g(x) = 3x+2
R R R
g f

g(1) f(5)
f(g(1))=13
1
g(1)=5

(f ○ g)(1)

f(g(x)) = 2(3x+2)+3 = 6x+7

 Compositions of functions

Does f(g(x)) = g(f(x))?

Let f(x) = 2x+3 Let g(x) = 3x+2

f(g(x)) = 2(3x+2)+3 = 6x+7

Not equal!
g(f(x)) = 3(2x+3)+2 = 6x+11

Function composition is not commutative!

 Composition of functions
• f ◦ g is defined as follows:
f ◦ g (x) = f(g(x)) for every x  X.
Example: g(x) = x2 -1, f(x) = 3x + 5. Then
g◦ f(x) = g(f(x)) = g(3x + 5) = (3x + 5) 2 - 1
3(x2 - 1 )+5
f x x -1
2

g f
g:

x 3x +5 (3x+5)2 - 1
g f: f g
 Properties of Compositions:
1. Composition of functions is associative:
f ◦ (g ◦h) = (f ◦ g) ◦ h,
But, in general, it is not commutative:
f ◦ g  g ◦ f.
2. If f and g are one - one and onto mapping then
their composition is also one - one and onto.

Let f(x) = 2x and g(x) = log 2 x = lg x

f ◦ g(x) = f(g(x)) = f(lg x) = 2 lg x = x

g ◦ f(x) = g(f(x)) = g(2x) = lg 2x = x

Therefore, the exponential and logarithmic functions

are inverses of each other.
 Different types of functions:
• The exponential and logarithmic functions.
• Trigonometric functions
• Trigonometric inverse functions.
• Identity functions.
• Constant functions.
• Floor and Ceiling Functions
• Integer and Absolute Value Functions
• Remainder function
• Arithmetic modulo M
• Hamming distance Function
• Characteristic Function
• Generating function and Recurrence relation
• Hash Functions
• Recursively Defined Functions
 Functions (Continued)
Floor and Ceiling Functions
Let x be any real number, then x lies between two
integers called floor and ceiling of x.
 x  is called floor of x and

 x  is called ceiling of x


In case integer, these are equal.

Absolute value of a function is defined
|x| is x when x  0 and –x when x < 0.
 Remainder Function
• Let x be a nonnegative integer and y a
positive integer
• r = x mod y is the remainder when x is
divided by y
Examples:
1 = 13 mod 3
6 = 234 mod 19
4 = 2002 mod 111
• mod is called the modulo operator
 Modulo Operator
• Let k be any integer and M be any positive
integer, then k (mod M) is the unique integer r
such that k= M q +r where
0 r<M. If k is negative, divide

|k| by M to obtain r’,
then k (mod M)=M-r’ where r’  0 and
k (mod M)=0 if r’= 0.
-26(mod7)=7-5=2, -39(mod 3)=0 and
-371(mod 8) = 8-3=5.
 Modular Arithmetic Operations
We have also used ‘mod’ for congruence
relation in set Z defined as a ~ b (mod M) iff
M/a-b, here M is called Modulus.
0~M (mod M) and a + M or a-M ~a (mod M)
Let us consider {0, 1,……,m-1} under Mod M
Then arithmetic operations addition,
multiplication and subtraction are called
Modular arithmetic operations.
e.g. {0,1,2, 3, 4} mod 5
2+4 ~1, 3x4=2, 3-4=-1 ~ 4, 2+3 ~0 ~5.
 Hamming Distance Function

Let x=(x1, x2,…..xn) and y= (y1, y2,….yn)

be n-tuple representing messages x1x2….xn
and y1y2…yn respectively, where xi, yi є{0,1} for all i.
The hamming distance between x and y is the
number of coordinates for which all x and y are
different and is denoted by H (x, y).
Example: Hamming distance between (1, 1,1,0, 1)
and (0,1,1,1,0) is 3.
 Hash Function
• Suppose That we have cells in computer
memory indexed from 0 to 10. We wish to
store and retrieval integers in these cells.
• Format of Hash function is H(n) = n mod (m)
where m is the number of available memory
locations.
• Here m = 11
Input Index
Hash Function: H(n)
Integer
 Hash Function
132 102 15 5 558 32
0 1 2 3 4 5 6 7 8 9 10

Retrieve

n= 102 Index=3
H(n)= n mod 11

Store

n= 257 Index=4
H(n)= n mod 11
Suppose that we want to store 257. Since h (257) = 4, therefore 257
should be stored at 4; but this position is already occupied and we say
that a collision has occurred.

Collision Resolution Policy: One simple collision resolution policy is

to find the next highest (10 followed by 0) unoccupied cell. Thus we
would store 257 at location 6.

If want to locate a stored value n, we compare m = h (n) = n mod 11.

And begin looking at location m. If n is not in this position, we look in
the next higher position; if n is not in this position, we in the next
higher
Position and so on. If we reach an empty cell or return to our original
position, we conclude that n is not present; otherwise, we obtain the
position. We conclude that n is not present the stored data.

Application: Personal data are frequently stored and retrieved by

hashing on employee’s identification numbers.
 Recursively Defined Function
A function is said to be recursively defined if the
function definition refers to itself. Further a
recursively defined function is said to be well
defined or not be circular
• If there are certain arguments, called base
values, for which the function does not refer to
itself and
• If each time the function does refer to itself, the
argument of the function must be going closer
to a base value.
e.g. factorial function (a) if n=0, then n! = 1
(b) if n> 0, then n!= n(n-1).
We see this definition of n! is recursive, since it
refers to itself when it uses (n-1)!.
• Further the value of n! is explicitly given
when n = 0. Thus 0 is a base value.
The value of n! for arbitrary n is defined in
terms of n which is closer to the base value 0
• Hence the definition is not circular or the
function is well defined.
Example: Let a and b be integers and suppose
Q (a,b) is defined recursively by
Q (a , b ) = 5 if a< b,
Q(a-b), b+2) + a, a>or=b .
• Find Q (2, 7), Q (5, 3) and Q (15, 2).
• Sol. (i) Q (2, 7) = 5, since 2 < 7.
• (ii) Q (5, 3) = Q ( 5-3, 5) + 5
• = Q ( 2, 5) + 5 = 5+ 5 = 10.
• Q( 15, 20) = Q( 15-2, 4) + 15
• = Q (13, 4) + 15 = Q( 9, 6) + 28
• = Q(3, 8) + 37 = 5 + 37 = 42
End of Functions