Function And Algorithms (chapter3)

Discrete Mathematics Chapter 3 Functions and Algorithms

Function: Definition 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 (x,y’) ∈ f, then y = y’ Example: 

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} 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.

f: R→R, f (x) = x

x f(-3)

f =9

f(√2) = 2 f(5)

2

= 25

x2

9 is the Image of -3 Some elements of the codomain are not images of 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}

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 Integer

Hash Function: H(n)

Index

Hash Function 132

0

1

2

102

15

5

3

4

5

32

6

7

8

Retrieve n= 102

H(n)= n mod 11

Index=3

Store n= 257

H(n)= n mod 11

Index=4

9

10

One-to-one functions 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 functions 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. 



Onto function = Surjective 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-to-

-One-to-

one -

one

Not onto

(C)

-Not one-toone -Onto

-Not onto

(D)

-One-to-one

-Onto

(E)

Not a function

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 g(a)

(f ○ g)(a)

f(g(a))

Compositions of functions Let f(x) = 2x+3

f○g

R

Let g(x) = 3x+2

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 g(f(x)) = 3(2x+3)+2 = 6x+11

Not equal!

Function composition is not commutative!

Composition of functions f ◦ g is defined as follows: f ◦ g (x) = f(g(x)) for every x ∈ X.





f

g

Example: g(x) = x2 -1, f(x) = 3x + 5. Then g◦ f(x) = g(f(x)) = g(3x + 5) = (3x + 5)2 - 1 x

g:

f:

x

x -1

3(x2 - 1 )+5

2

g

f

3x +5

f

(3x+5)2 - 1

g

Exponential and logarithmic functions 

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.

Modulo operator 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

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.

Different types of functions: (Please Use Handouts) 

            

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. Identity functions. Constant functions. Greatest Integer 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 Recursively Defined Functions Define a function f: N Z, which is one one and onto. Also Find its inverse

End of chapter 3.