المحاضرة التاسعة هياكل متقطعة

Functions II
Functions
• Definition: Let A and B be two sets. A function from A to B,
denoted f : A ? B , is an assignment of exactly one element of
B to each element of A. We write f(a) = b to denote the
assignment of b to an element a of A by the function f.
A f: A ?B B
Not allowed !!!
CS 441 Discrete mathematics for CS M. Hauskrecht
Injective function
Definition: A function f is said to be one-to-one, or injective, if
and only if f(x) = f(y) implies x = y for all x, y in the domain of
f. A function is said to be an injection if it is one-to-one.
Alternative: A function is one-to-one if and only if f(x) ? f(y),
whenever x ? y. This is the contrapositive of the definition.
A f: A ? B B A f: A ? B B
Not injective function Injective function
3
M. Hauskrecht
Surjective function
Definition: A function f from A to B is called onto, or surjective,
if and only if for every b ? B there is an element a ? A such that
f(a) = b.
Alternative: all co-domain elements are covered
A f: A ?B B
M. Hauskrecht
Bijective functions
Definition: A function f is called a bijection if it is both one-toone
(injection) and onto (surjection).
A f: A ?B B
4
M. Hauskrecht
Bijective functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c}
– Define f as
• 1 ? c
• 2 ? a
• 3 ? b
• Is f a bijection?
• ?
M. Hauskrecht
Bijective functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c}
– Define f as
• 1 ? c
• 2 ? a
• 3 ? b
• Is f a bijection?
• Yes. It is both one-to-one and onto.
5
M. Hauskrecht
Bijective functions
Example 2:
• Define g : W ? W (whole numbers), where
g(n) = ? n/2 ? (floor function).
• 0 ? ? 0/2 ? = ? 0 ? = 0
• 1 ? ? 1/2 ? = ? 1/2 ? = 0
• 2 ? ? 2/2 ? = ? 1 ? = 1
• 3 ? ? 3/2 ? = ? 3/2 ? = 1
• ...
• Is g a bijection?
M. Hauskrecht
Bijective functions
Example 2:
• Define g : W ? W (whole numbers), where
g(n) = ? n/2 ? (floor function).
• 0 ? ? 0/2 ? = ? 0 ? = 0
• 1 ? ? 1/2 ? = ? 1/2 ? = 0
• 2 ? ? 2/2 ? = ? 1 ? = 1
• 3 ? ? 3/2 ? = ? 3/2 ? = 1
• ...
• Is g a bijection?
– No. g is onto but not 1-1 (g(0) = g(1) = 0 however 0 ? 1.
6
CS 441 Discrete mathematics for CS M. Hauskrecht
Bijective functions
Theorem: Let f be a function f: A ?A from a set A to itself,
where A is finite. Then f is one-to-one if and only if f is onto.
Assume
? A is finite and f is one-to-one (injective)
• Is f an onto function (surjection)?
CS 441 Discrete mathematics for CS M. Hauskrecht
Bijective functions
Theorem: Let f be a function f: A ?A from a set A to itself,
where A is finite. Then f is one-to-one if and only if f is onto.
Proof:
? A is finite and f is one-to-one (injective)
• Is f an onto function (surjection)?
• Yes. Every element points to exactly one element. Injection
assures they are different. So we have |A| different elements A
points to. Since f: A ? A the co-domain is covered thus the
function is also a surjection (and a bijection)
? A is finite and f is an onto function
• Is the function one-to-one?
7
CS 441 Discrete mathematics for CS M. Hauskrecht
Bijective functions
Theorem: Let f be a function f: A ?A from a set A to itself,
where A is finite. Then f is one-to-one if and only if f is onto.
Proof:
? A is finite and f is one-to-one (injective)
• Is f an onto function (surjection)?
• Yes. Every element points to exactly one element. Injection
assures they are different. So we have |A| different elements A
points to. Since f: A ? A the co-domain is covered thus the
function is also a surjection (and a bijection)
? A is finite and f is an onto function
• Is the function one-to-one?
• Yes. Every element maps to exactly one element and all
elements in A are covered. Thus the mapping must be one-toone
M. Hauskrecht
Bijective functions
Theorem. Let f be a function from a set A to itself, where A is
finite. Then f is one-to-one if and only if f is onto.
Please note the above is not true when A is an infinite set.
• Example:
– f : Z ? Z, where f(z) = 2 * z.
– f is one-to-one but not onto.
• 1 ? 2
• 2 ? 4
• 3 ? 6
– 3 has no pre-image.
8
CS 441 Discrete mathematics for CS M. Hauskrecht
Functions on real numbers
Definition: Let f1 and f2 be functions from A to R (reals). Then
f1 + f2 and f1 * f2 are also functions from A to R defined by
• (f1 + f2)(x) = f1(x) + f2(x)
• (f1 * f2)(x) = f1(x) * f2(x).
Examples:
• Assume
• f1(x) = x - 1
• f2(x) = x3 + 1
then
• (f1 + f2)(x) = x3 + x
• (f1 * f2)(x) = x4 - x3 + x - 1.
CS 441 Discrete mathematics for CS M. Hauskrecht
Increasing and decreasing functions
Definition: A function f whose domain and codomain are subsets
of real numbers is strictly increasing if f(x) > f(y) whenever x >
y and x and y are in the domain of f. Similarly, f is called
strictly decreasing if f(x) < f(y) whenever x > y and x and y are
in the domain of f.
Example:
• Let g : R ? R, where g(x) = 2x - 1. Is it increasing ?
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Increasing and decreasing functions
Definition: A function f whose domain and codomain are subsets
of real numbers is strictly increasing if f(x) > f(y) whenever x >
y and x and y are in the domain of f. Similarly, f is called
strictly decreasing if f(x) < f(y) whenever x > y and x and y are
in the domain of f.
Example:
• Let g : R ? R, where g(x) = 2x - 1. Is it increasing ?
• Proof .
For x>y holds 2x > 2y and subsequently 2x-1 > 2y-1
Thus g is strictly increasing.
CS 441 Discrete mathematics for CS M. Hauskrecht
Increasing and decreasing functions
Definition: A function f whose domain and codomain are subsets
of real numbers is strictly increasing if f(x) > f(y) whenever x >
y and x and y are in the domain of f. Similarly, f is called
strictly decreasing if f(x) < f(y) whenever x > y and x and y are
in the domain of f.
Note: Strictly increasing and strictly decreasing functions are oneto-
one.
Why?
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Increasing and decreasing functions
Definition: A function f whose domain and codomain are subsets
of real numbers is strictly increasing if f(x) > f(y) whenever x >
y and x and y are in the domain of f. Similarly, f is called
strictly decreasing if f(x) < f(y) whenever x > y and x and y are
in the domain of f.
Note: Strictly increasing and strictly decreasing functions are oneto-
one.
Why?
One-to-one function: A function is one-to-one if and only if f(x) ?
f(y), whenever x ? y.
CS 441 Discrete mathematics for CS M. Hauskrecht
Identity function
Definition: Let A be a set. The identity function on A is the
function iA: A ? A where iA (x) = x.
Example:
• Let A = {1,2,3}
Then:
• iA (1) = ?
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Identity function
Definition: Let A be a set. The identity function on A is the
function iA: A ? A where iA (x) = x.
Example:
• Let A = {1,2,3}
Then:
• iA (1) = 1
• iA (2) = 2
• iA (3) = 3.
CS 441 Discrete mathematics for CS M. Hauskrecht
Bijective functions
Definition: A function f is called a bijection if it is both one-toone
and onto.
A f: A ?B B
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Definition: Let f be a bijection from set A to set B. The inverse
function of f is the function that assigns to an element b from B
the unique element a in A such that f(a) = b. The inverse
function of f is denoted by f-1. Hence, f-1 (b) = a, when f(a) = b.
If the inverse function of f exists, f is called invertible.
A f: A ?B B A f -1: B ?A B
f is bijective Inverse of f
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Note: if f is not a bijection then it is not possible to define the
inverse function of f. Why?
Assume f is not one-to-one:
?
A f: A ?B B A f -1: B ?A B
f ‘Inverse’
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Note: if f is not a bijection then it is not possible to define the
inverse function of f. Why?
Assume f is not one-to-one:
Inverse is not a function. One element of B is mapped to two
different elements.
A f: A ?B B A f -1: B ?A B
f ‘Inverse’
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Note: if f is not a bijection then it is not possible to define the
inverse function of f. Why?
Assume f is not onto:
?
A f: A ?B B A f -1: B ?A B
f ‘Inverse’
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Note: if f is not a bijection then it is not possible to define the
inverse function of f. Why?
Assume f is not onto:
Inverse is not a function. One element of B is not assigned any
value in B.
A f: A ?B B A f -1: B ?A B
f ‘Inverse’
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 1:
• Let A = {1,2,3} and i A be the identity function
• iA(1) = 1 iA
-1 (1) = 1
• iA(2) = 2 iA
-1 (2) = 2
• iA(3) = 3 iA
-1 (3) = 3
• Therefore, the inverse function of iA is iA.
15
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 2:
• Let g : R ? R, where g(x) = 2x - 1.
• What is the inverse function g-1 ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 2:
• Let g : R ? R, where g(x) = 2x - 1.
• What is the inverse function g-1 ?
Approach to determine the inverse:
y = 2x - 1 => y + 1 = 2x
=> (y+1)/2 = x
• Define g-1(y) = x= (y+1)/2
Test the correctness of inverse:
• g(3) = ..
16
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 2:
• Let g : R ? R, where g(x) = 2x - 1.
• What is the inverse function g-1 ?
Approach to determine the inverse:
y = 2x - 1 => y + 1 = 2x
=> (y+1)/2 = x
• Define g-1(y) = x= (y+1)/2
Test the correctness of inverse:
• g(3) = 2*3 - 1 = 5
• g-1 (5) =
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 2:
• Let g : R ? R, where g(x) = 2x - 1.
• What is the inverse function g-1 ?
Approach to determine the inverse:
y = 2x - 1 => y + 1 = 2x
=> (y+1)/2 = x
• Define g-1(y) = x= (y+1)/2
Test the correctness of inverse:
• g(3) = 2*3 - 1 = 5
• g-1 (5) = (5+1)/2 = 3
• g(10) =
17
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 2:
• Let g : R ? R, where g(x) = 2x - 1.
• What is the inverse function g-1 ?
Approach to determine the inverse:
y = 2x - 1 => y + 1 = 2x
=> (y+1)/2 = x
• Define g-1(y) = x= (y+1)/2
Test the correctness of inverse:
• g(3) = 2*3 - 1 = 5
• g-1 (5) = (5+1)/2 = 3
• g(10) = 2*10 - 1 = 19
• g-1 (19) =
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 2:
• Let g : R ? R, where g(x) = 2x - 1.
• What is the inverse function g-1 ?
Approach to determine the inverse:
y = 2x - 1 => y + 1 = 2x
=> (y+1)/2 = x
• Define g-1(y) = x= (y+1)/2
Test the correctness of inverse:
• g(3) = 2*3 - 1 = 5
• g-1 (5) = (5+1)/2 = 3
• g(10) = 2*10 - 1 = 19
• g-1 (19) = (19+1)/2 = 10.
18
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Definition: Let f be a function from set A to set B and let g be a
function from set B to set C. The composition of the functions
g and f, denoted by g ? f is defined by
• (g ? f)(a) = g(f(a)).
A f: A ? B B g: B ? C C
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c,d}
g : A ? A, f: A ? B
1 ?3 1 ? b
2 ?1 2 ? a
3 ?2 3 ? d
f ? g : A ? B:
• 1 ?
19
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c,d}
g : A ? A, f: A ? B
1 ?3 1 ? b
2 ?1 2 ? a
3 ?2 3 ? d
f ? g : A ? B:
• 1 ? d
• 2 ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c,d}
g : A ? A, f: A ? B
1 ?3 1 ? b
2 ?1 2 ? a
3 ?2 3 ? d
f ? g : A ? B:
• 1 ? d
• 2 ? b
• 3 ?
20
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c,d}
g : A ? A, f: A ? B
1 ?3 1 ? b
2 ?1 2 ? a
3 ?2 3 ? d
f ? g : A ? B:
• 1 ? d
• 2 ? b
• 3 ? a
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 2:
• Let f and g be two functions from Z to Z, where
• f(x) = 2x and g(x) = x2.
• f ? g : Z ? Z
• (f ? g)(x) = f(g(x))
= f( x2 )
= 2(x2)
• g ? f : Z ? Z
• (g ? f)(x) = ?
21
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 2:
• Let f and g be two functions from Z to Z, where
• f(x) = 2x and g(x) = x2.
• f ? g : Z ? Z
• (f ? g)(x) = f(g(x))
= f( x2 )
= 2(x2)
• g ? f : Z ? Z
• (g ? f)(x) = g(f(x))
= g(2x)
= (2x) 2
= 4x2
Note that the order of
the function composition matters
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 3:
• (f ? f -1)(x) = x and (f -1 ? f)(x) = x, for all x.
• Let f : R ? R, where f(x) = 2x – 1 and f -1 (x) = (x+1)/2.
• (f ? f -1 )(x)= f(f -1 (x))
= f( (x+1)/2 )
= 2( (x+1)/2 ) - 1
= (x+1) - 1
= x
22
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 3:
• (f ? f -1)(x) = x and (f -1 ? f)(x) = x, for all x.
• Let f : R ? R, where f(x) = 2x – 1 and f -1 (x) = (x+1)/2.
• (f ? f -1 )(x)= f(f -1 (x))
= f( (x+1)/2 )
= 2( (x+1)/2 ) - 1
= (x+1) - 1
= x
• (f -1 ? f)(x) = f -1 (f(x))
= f -1 ( 2x - 1 )
= (2x)/2
= x
CS 441 Discrete mathematics for CS M. Hauskrecht
Functions
• Definition: Let A and B be two sets. A function from A to B,
denoted f : A ? B , is an assignment of exactly one element of
B to each element of A. We write f(a) = b to denote the
assignment of b to an element a of A by the function f.
A f: A ?B B
Not allowed !!!
CS 441 Discrete mathematics for CS M. Hauskrecht
Injective function
Definition: A function f is said to be one-to-one, or injective, if
and only if f(x) = f(y) implies x = y for all x, y in the domain of
f. A function is said to be an injection if it is one-to-one.
Alternative: A function is one-to-one if and only if f(x) ? f(y),
whenever x ? y. This is the contrapositive of the definition.
A f: A ? B B A f: A ? B B
Not injective function Injective function
3
M. Hauskrecht
Surjective function
Definition: A function f from A to B is called onto, or surjective,
if and only if for every b ? B there is an element a ? A such that
f(a) = b.
Alternative: all co-domain elements are covered
A f: A ?B B
M. Hauskrecht
Bijective functions
Definition: A function f is called a bijection if it is both one-toone
(injection) and onto (surjection).
A f: A ?B B
4
M. Hauskrecht
Bijective functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c}
– Define f as
• 1 ? c
• 2 ? a
• 3 ? b
• Is f a bijection?
• ?
M. Hauskrecht
Bijective functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c}
– Define f as
• 1 ? c
• 2 ? a
• 3 ? b
• Is f a bijection?
• Yes. It is both one-to-one and onto.
5
M. Hauskrecht
Bijective functions
Example 2:
• Define g : W ? W (whole numbers), where
g(n) = ? n/2 ? (floor function).
• 0 ? ? 0/2 ? = ? 0 ? = 0
• 1 ? ? 1/2 ? = ? 1/2 ? = 0
• 2 ? ? 2/2 ? = ? 1 ? = 1
• 3 ? ? 3/2 ? = ? 3/2 ? = 1
• ...
• Is g a bijection?
M. Hauskrecht
Bijective functions
Example 2:
• Define g : W ? W (whole numbers), where
g(n) = ? n/2 ? (floor function).
• 0 ? ? 0/2 ? = ? 0 ? = 0
• 1 ? ? 1/2 ? = ? 1/2 ? = 0
• 2 ? ? 2/2 ? = ? 1 ? = 1
• 3 ? ? 3/2 ? = ? 3/2 ? = 1
• ...
• Is g a bijection?
– No. g is onto but not 1-1 (g(0) = g(1) = 0 however 0 ? 1.
6
CS 441 Discrete mathematics for CS M. Hauskrecht
Bijective functions
Theorem: Let f be a function f: A ?A from a set A to itself,
where A is finite. Then f is one-to-one if and only if f is onto.
Assume
? A is finite and f is one-to-one (injective)
• Is f an onto function (surjection)?
CS 441 Discrete mathematics for CS M. Hauskrecht
Bijective functions
Theorem: Let f be a function f: A ?A from a set A to itself,
where A is finite. Then f is one-to-one if and only if f is onto.
Proof:
? A is finite and f is one-to-one (injective)
• Is f an onto function (surjection)?
• Yes. Every element points to exactly one element. Injection
assures they are different. So we have |A| different elements A
points to. Since f: A ? A the co-domain is covered thus the
function is also a surjection (and a bijection)
? A is finite and f is an onto function
• Is the function one-to-one?
7
CS 441 Discrete mathematics for CS M. Hauskrecht
Bijective functions
Theorem: Let f be a function f: A ?A from a set A to itself,
where A is finite. Then f is one-to-one if and only if f is onto.
Proof:
? A is finite and f is one-to-one (injective)
• Is f an onto function (surjection)?
• Yes. Every element points to exactly one element. Injection
assures they are different. So we have |A| different elements A
points to. Since f: A ? A the co-domain is covered thus the
function is also a surjection (and a bijection)
? A is finite and f is an onto function
• Is the function one-to-one?
• Yes. Every element maps to exactly one element and all
elements in A are covered. Thus the mapping must be one-toone
M. Hauskrecht
Bijective functions
Theorem. Let f be a function from a set A to itself, where A is
finite. Then f is one-to-one if and only if f is onto.
Please note the above is not true when A is an infinite set.
• Example:
– f : Z ? Z, where f(z) = 2 * z.
– f is one-to-one but not onto.
• 1 ? 2
• 2 ? 4
• 3 ? 6
– 3 has no pre-image.
8
CS 441 Discrete mathematics for CS M. Hauskrecht
Functions on real numbers
Definition: Let f1 and f2 be functions from A to R (reals). Then
f1 + f2 and f1 * f2 are also functions from A to R defined by
• (f1 + f2)(x) = f1(x) + f2(x)
• (f1 * f2)(x) = f1(x) * f2(x).
Examples:
• Assume
• f1(x) = x - 1
• f2(x) = x3 + 1
then
• (f1 + f2)(x) = x3 + x
• (f1 * f2)(x) = x4 - x3 + x - 1.
CS 441 Discrete mathematics for CS M. Hauskrecht
Increasing and decreasing functions
Definition: A function f whose domain and codomain are subsets
of real numbers is strictly increasing if f(x) > f(y) whenever x >
y and x and y are in the domain of f. Similarly, f is called
strictly decreasing if f(x) < f(y) whenever x > y and x and y are
in the domain of f.
Example:
• Let g : R ? R, where g(x) = 2x - 1. Is it increasing ?
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Increasing and decreasing functions
Definition: A function f whose domain and codomain are subsets
of real numbers is strictly increasing if f(x) > f(y) whenever x >
y and x and y are in the domain of f. Similarly, f is called
strictly decreasing if f(x) < f(y) whenever x > y and x and y are
in the domain of f.
Example:
• Let g : R ? R, where g(x) = 2x - 1. Is it increasing ?
• Proof .
For x>y holds 2x > 2y and subsequently 2x-1 > 2y-1
Thus g is strictly increasing.
CS 441 Discrete mathematics for CS M. Hauskrecht
Increasing and decreasing functions
Definition: A function f whose domain and codomain are subsets
of real numbers is strictly increasing if f(x) > f(y) whenever x >
y and x and y are in the domain of f. Similarly, f is called
strictly decreasing if f(x) < f(y) whenever x > y and x and y are
in the domain of f.
Note: Strictly increasing and strictly decreasing functions are oneto-
one.
Why?
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Increasing and decreasing functions
Definition: A function f whose domain and codomain are subsets
of real numbers is strictly increasing if f(x) > f(y) whenever x >
y and x and y are in the domain of f. Similarly, f is called
strictly decreasing if f(x) < f(y) whenever x > y and x and y are
in the domain of f.
Note: Strictly increasing and strictly decreasing functions are oneto-
one.
Why?
One-to-one function: A function is one-to-one if and only if f(x) ?
f(y), whenever x ? y.
CS 441 Discrete mathematics for CS M. Hauskrecht
Identity function
Definition: Let A be a set. The identity function on A is the
function iA: A ? A where iA (x) = x.
Example:
• Let A = {1,2,3}
Then:
• iA (1) = ?
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Identity function
Definition: Let A be a set. The identity function on A is the
function iA: A ? A where iA (x) = x.
Example:
• Let A = {1,2,3}
Then:
• iA (1) = 1
• iA (2) = 2
• iA (3) = 3.
CS 441 Discrete mathematics for CS M. Hauskrecht
Bijective functions
Definition: A function f is called a bijection if it is both one-toone
and onto.
A f: A ?B B
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Definition: Let f be a bijection from set A to set B. The inverse
function of f is the function that assigns to an element b from B
the unique element a in A such that f(a) = b. The inverse
function of f is denoted by f-1. Hence, f-1 (b) = a, when f(a) = b.
If the inverse function of f exists, f is called invertible.
A f: A ?B B A f -1: B ?A B
f is bijective Inverse of f
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Note: if f is not a bijection then it is not possible to define the
inverse function of f. Why?
Assume f is not one-to-one:
?
A f: A ?B B A f -1: B ?A B
f ‘Inverse’
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Note: if f is not a bijection then it is not possible to define the
inverse function of f. Why?
Assume f is not one-to-one:
Inverse is not a function. One element of B is mapped to two
different elements.
A f: A ?B B A f -1: B ?A B
f ‘Inverse’
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Note: if f is not a bijection then it is not possible to define the
inverse function of f. Why?
Assume f is not onto:
?
A f: A ?B B A f -1: B ?A B
f ‘Inverse’
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Note: if f is not a bijection then it is not possible to define the
inverse function of f. Why?
Assume f is not onto:
Inverse is not a function. One element of B is not assigned any
value in B.
A f: A ?B B A f -1: B ?A B
f ‘Inverse’
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 1:
• Let A = {1,2,3} and i A be the identity function
• iA(1) = 1 iA
-1 (1) = 1
• iA(2) = 2 iA
-1 (2) = 2
• iA(3) = 3 iA
-1 (3) = 3
• Therefore, the inverse function of iA is iA.
15
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 2:
• Let g : R ? R, where g(x) = 2x - 1.
• What is the inverse function g-1 ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 2:
• Let g : R ? R, where g(x) = 2x - 1.
• What is the inverse function g-1 ?
Approach to determine the inverse:
y = 2x - 1 => y + 1 = 2x
=> (y+1)/2 = x
• Define g-1(y) = x= (y+1)/2
Test the correctness of inverse:
• g(3) = ..
16
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 2:
• Let g : R ? R, where g(x) = 2x - 1.
• What is the inverse function g-1 ?
Approach to determine the inverse:
y = 2x - 1 => y + 1 = 2x
=> (y+1)/2 = x
• Define g-1(y) = x= (y+1)/2
Test the correctness of inverse:
• g(3) = 2*3 - 1 = 5
• g-1 (5) =
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 2:
• Let g : R ? R, where g(x) = 2x - 1.
• What is the inverse function g-1 ?
Approach to determine the inverse:
y = 2x - 1 => y + 1 = 2x
=> (y+1)/2 = x
• Define g-1(y) = x= (y+1)/2
Test the correctness of inverse:
• g(3) = 2*3 - 1 = 5
• g-1 (5) = (5+1)/2 = 3
• g(10) =
17
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 2:
• Let g : R ? R, where g(x) = 2x - 1.
• What is the inverse function g-1 ?
Approach to determine the inverse:
y = 2x - 1 => y + 1 = 2x
=> (y+1)/2 = x
• Define g-1(y) = x= (y+1)/2
Test the correctness of inverse:
• g(3) = 2*3 - 1 = 5
• g-1 (5) = (5+1)/2 = 3
• g(10) = 2*10 - 1 = 19
• g-1 (19) =
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 2:
• Let g : R ? R, where g(x) = 2x - 1.
• What is the inverse function g-1 ?
Approach to determine the inverse:
y = 2x - 1 => y + 1 = 2x
=> (y+1)/2 = x
• Define g-1(y) = x= (y+1)/2
Test the correctness of inverse:
• g(3) = 2*3 - 1 = 5
• g-1 (5) = (5+1)/2 = 3
• g(10) = 2*10 - 1 = 19
• g-1 (19) = (19+1)/2 = 10.
18
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Definition: Let f be a function from set A to set B and let g be a
function from set B to set C. The composition of the functions
g and f, denoted by g ? f is defined by
• (g ? f)(a) = g(f(a)).
A f: A ? B B g: B ? C C
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c,d}
g : A ? A, f: A ? B
1 ?3 1 ? b
2 ?1 2 ? a
3 ?2 3 ? d
f ? g : A ? B:
• 1 ?
19
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c,d}
g : A ? A, f: A ? B
1 ?3 1 ? b
2 ?1 2 ? a
3 ?2 3 ? d
f ? g : A ? B:
• 1 ? d
• 2 ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c,d}
g : A ? A, f: A ? B
1 ?3 1 ? b
2 ?1 2 ? a
3 ?2 3 ? d
f ? g : A ? B:
• 1 ? d
• 2 ? b
• 3 ?
20
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c,d}
g : A ? A, f: A ? B
1 ?3 1 ? b
2 ?1 2 ? a
3 ?2 3 ? d
f ? g : A ? B:
• 1 ? d
• 2 ? b
• 3 ? a
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 2:
• Let f and g be two functions from Z to Z, where
• f(x) = 2x and g(x) = x2.
• f ? g : Z ? Z
• (f ? g)(x) = f(g(x))
= f( x2 )
= 2(x2)
• g ? f : Z ? Z
• (g ? f)(x) = ?
21
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 2:
• Let f and g be two functions from Z to Z, where
• f(x) = 2x and g(x) = x2.
• f ? g : Z ? Z
• (f ? g)(x) = f(g(x))
= f( x2 )
= 2(x2)
• g ? f : Z ? Z
• (g ? f)(x) = g(f(x))
= g(2x)
= (2x) 2
= 4x2
Note that the order of
the function composition matters
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 3:
• (f ? f -1)(x) = x and (f -1 ? f)(x) = x, for all x.
• Let f : R ? R, where f(x) = 2x – 1 and f -1 (x) = (x+1)/2.
• (f ? f -1 )(x)= f(f -1 (x))
= f( (x+1)/2 )
= 2( (x+1)/2 ) - 1
= (x+1) - 1
= x
22
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 3:
• (f ? f -1)(x) = x and (f -1 ? f)(x) = x, for all x.
• Let f : R ? R, where f(x) = 2x – 1 and f -1 (x) = (x+1)/2.
• (f ? f -1 )(x)= f(f -1 (x))
= f( (x+1)/2 )
= 2( (x+1)/2 ) - 1
= (x+1) - 1
= x
• (f -1 ? f)(x) = f -1 (f(x))
= f -1 ( 2x - 1 )
= (2x)/2
= x
CS 441 Discrete mathematics for CS M. Hauskrecht
Functions
• Definition: Let A and B be two sets. A function from A to B,
denoted f : A ? B , is an assignment of exactly one element of
B to each element of A. We write f(a) = b to denote the
assignment of b to an element a of A by the function f.
A f: A ?B B
Not allowed !!!
CS 441 Discrete mathematics for CS M. Hauskrecht
Injective function
Definition: A function f is said to be one-to-one, or injective, if
and only if f(x) = f(y) implies x = y for all x, y in the domain of
f. A function is said to be an injection if it is one-to-one.
Alternative: A function is one-to-one if and only if f(x) ? f(y),
whenever x ? y. This is the contrapositive of the definition.
A f: A ? B B A f: A ? B B
Not injective function Injective function
3
M. Hauskrecht
Surjective function
Definition: A function f from A to B is called onto, or surjective,
if and only if for every b ? B there is an element a ? A such that
f(a) = b.
Alternative: all co-domain elements are covered
A f: A ?B B
M. Hauskrecht
Bijective functions
Definition: A function f is called a bijection if it is both one-toone
(injection) and onto (surjection).
A f: A ?B B
4
M. Hauskrecht
Bijective functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c}
– Define f as
• 1 ? c
• 2 ? a
• 3 ? b
• Is f a bijection?
• ?
M. Hauskrecht
Bijective functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c}
– Define f as
• 1 ? c
• 2 ? a
• 3 ? b
• Is f a bijection?
• Yes. It is both one-to-one and onto.
5
M. Hauskrecht
Bijective functions
Example 2:
• Define g : W ? W (whole numbers), where
g(n) = ? n/2 ? (floor function).
• 0 ? ? 0/2 ? = ? 0 ? = 0
• 1 ? ? 1/2 ? = ? 1/2 ? = 0
• 2 ? ? 2/2 ? = ? 1 ? = 1
• 3 ? ? 3/2 ? = ? 3/2 ? = 1
• ...
• Is g a bijection?
M. Hauskrecht
Bijective functions
Example 2:
• Define g : W ? W (whole numbers), where
g(n) = ? n/2 ? (floor function).
• 0 ? ? 0/2 ? = ? 0 ? = 0
• 1 ? ? 1/2 ? = ? 1/2 ? = 0
• 2 ? ? 2/2 ? = ? 1 ? = 1
• 3 ? ? 3/2 ? = ? 3/2 ? = 1
• ...
• Is g a bijection?
– No. g is onto but not 1-1 (g(0) = g(1) = 0 however 0 ? 1.
6
CS 441 Discrete mathematics for CS M. Hauskrecht
Bijective functions
Theorem: Let f be a function f: A ?A from a set A to itself,
where A is finite. Then f is one-to-one if and only if f is onto.
Assume
? A is finite and f is one-to-one (injective)
• Is f an onto function (surjection)?
CS 441 Discrete mathematics for CS M. Hauskrecht
Bijective functions
Theorem: Let f be a function f: A ?A from a set A to itself,
where A is finite. Then f is one-to-one if and only if f is onto.
Proof:
? A is finite and f is one-to-one (injective)
• Is f an onto function (surjection)?
• Yes. Every element points to exactly one element. Injection
assures they are different. So we have |A| different elements A
points to. Since f: A ? A the co-domain is covered thus the
function is also a surjection (and a bijection)
? A is finite and f is an onto function
• Is the function one-to-one?
7
CS 441 Discrete mathematics for CS M. Hauskrecht
Bijective functions
Theorem: Let f be a function f: A ?A from a set A to itself,
where A is finite. Then f is one-to-one if and only if f is onto.
Proof:
? A is finite and f is one-to-one (injective)
• Is f an onto function (surjection)?
• Yes. Every element points to exactly one element. Injection
assures they are different. So we have |A| different elements A
points to. Since f: A ? A the co-domain is covered thus the
function is also a surjection (and a bijection)
? A is finite and f is an onto function
• Is the function one-to-one?
• Yes. Every element maps to exactly one element and all
elements in A are covered. Thus the mapping must be one-toone
M. Hauskrecht
Bijective functions
Theorem. Let f be a function from a set A to itself, where A is
finite. Then f is one-to-one if and only if f is onto.
Please note the above is not true when A is an infinite set.
• Example:
– f : Z ? Z, where f(z) = 2 * z.
– f is one-to-one but not onto.
• 1 ? 2
• 2 ? 4
• 3 ? 6
– 3 has no pre-image.
8
CS 441 Discrete mathematics for CS M. Hauskrecht
Functions on real numbers
Definition: Let f1 and f2 be functions from A to R (reals). Then
f1 + f2 and f1 * f2 are also functions from A to R defined by
• (f1 + f2)(x) = f1(x) + f2(x)
• (f1 * f2)(x) = f1(x) * f2(x).
Examples:
• Assume
• f1(x) = x - 1
• f2(x) = x3 + 1
then
• (f1 + f2)(x) = x3 + x
• (f1 * f2)(x) = x4 - x3 + x - 1.
CS 441 Discrete mathematics for CS M. Hauskrecht
Increasing and decreasing functions
Definition: A function f whose domain and codomain are subsets
of real numbers is strictly increasing if f(x) > f(y) whenever x >
y and x and y are in the domain of f. Similarly, f is called
strictly decreasing if f(x) < f(y) whenever x > y and x and y are
in the domain of f.
Example:
• Let g : R ? R, where g(x) = 2x - 1. Is it increasing ?
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Increasing and decreasing functions
Definition: A function f whose domain and codomain are subsets
of real numbers is strictly increasing if f(x) > f(y) whenever x >
y and x and y are in the domain of f. Similarly, f is called
strictly decreasing if f(x) < f(y) whenever x > y and x and y are
in the domain of f.
Example:
• Let g : R ? R, where g(x) = 2x - 1. Is it increasing ?
• Proof .
For x>y holds 2x > 2y and subsequently 2x-1 > 2y-1
Thus g is strictly increasing.
CS 441 Discrete mathematics for CS M. Hauskrecht
Increasing and decreasing functions
Definition: A function f whose domain and codomain are subsets
of real numbers is strictly increasing if f(x) > f(y) whenever x >
y and x and y are in the domain of f. Similarly, f is called
strictly decreasing if f(x) < f(y) whenever x > y and x and y are
in the domain of f.
Note: Strictly increasing and strictly decreasing functions are oneto-
one.
Why?
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Increasing and decreasing functions
Definition: A function f whose domain and codomain are subsets
of real numbers is strictly increasing if f(x) > f(y) whenever x >
y and x and y are in the domain of f. Similarly, f is called
strictly decreasing if f(x) < f(y) whenever x > y and x and y are
in the domain of f.
Note: Strictly increasing and strictly decreasing functions are oneto-
one.
Why?
One-to-one function: A function is one-to-one if and only if f(x) ?
f(y), whenever x ? y.
CS 441 Discrete mathematics for CS M. Hauskrecht
Identity function
Definition: Let A be a set. The identity function on A is the
function iA: A ? A where iA (x) = x.
Example:
• Let A = {1,2,3}
Then:
• iA (1) = ?
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Identity function
Definition: Let A be a set. The identity function on A is the
function iA: A ? A where iA (x) = x.
Example:
• Let A = {1,2,3}
Then:
• iA (1) = 1
• iA (2) = 2
• iA (3) = 3.
CS 441 Discrete mathematics for CS M. Hauskrecht
Bijective functions
Definition: A function f is called a bijection if it is both one-toone
and onto.
A f: A ?B B
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Definition: Let f be a bijection from set A to set B. The inverse
function of f is the function that assigns to an element b from B
the unique element a in A such that f(a) = b. The inverse
function of f is denoted by f-1. Hence, f-1 (b) = a, when f(a) = b.
If the inverse function of f exists, f is called invertible.
A f: A ?B B A f -1: B ?A B
f is bijective Inverse of f
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Note: if f is not a bijection then it is not possible to define the
inverse function of f. Why?
Assume f is not one-to-one:
?
A f: A ?B B A f -1: B ?A B
f ‘Inverse’
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Note: if f is not a bijection then it is not possible to define the
inverse function of f. Why?
Assume f is not one-to-one:
Inverse is not a function. One element of B is mapped to two
different elements.
A f: A ?B B A f -1: B ?A B
f ‘Inverse’
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Note: if f is not a bijection then it is not possible to define the
inverse function of f. Why?
Assume f is not onto:
?
A f: A ?B B A f -1: B ?A B
f ‘Inverse’
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Note: if f is not a bijection then it is not possible to define the
inverse function of f. Why?
Assume f is not onto:
Inverse is not a function. One element of B is not assigned any
value in B.
A f: A ?B B A f -1: B ?A B
f ‘Inverse’
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 1:
• Let A = {1,2,3} and i A be the identity function
• iA(1) = 1 iA
-1 (1) = 1
• iA(2) = 2 iA
-1 (2) = 2
• iA(3) = 3 iA
-1 (3) = 3
• Therefore, the inverse function of iA is iA.
15
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 2:
• Let g : R ? R, where g(x) = 2x - 1.
• What is the inverse function g-1 ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 2:
• Let g : R ? R, where g(x) = 2x - 1.
• What is the inverse function g-1 ?
Approach to determine the inverse:
y = 2x - 1 => y + 1 = 2x
=> (y+1)/2 = x
• Define g-1(y) = x= (y+1)/2
Test the correctness of inverse:
• g(3) = ..
16
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 2:
• Let g : R ? R, where g(x) = 2x - 1.
• What is the inverse function g-1 ?
Approach to determine the inverse:
y = 2x - 1 => y + 1 = 2x
=> (y+1)/2 = x
• Define g-1(y) = x= (y+1)/2
Test the correctness of inverse:
• g(3) = 2*3 - 1 = 5
• g-1 (5) =
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 2:
• Let g : R ? R, where g(x) = 2x - 1.
• What is the inverse function g-1 ?
Approach to determine the inverse:
y = 2x - 1 => y + 1 = 2x
=> (y+1)/2 = x
• Define g-1(y) = x= (y+1)/2
Test the correctness of inverse:
• g(3) = 2*3 - 1 = 5
• g-1 (5) = (5+1)/2 = 3
• g(10) =
17
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 2:
• Let g : R ? R, where g(x) = 2x - 1.
• What is the inverse function g-1 ?
Approach to determine the inverse:
y = 2x - 1 => y + 1 = 2x
=> (y+1)/2 = x
• Define g-1(y) = x= (y+1)/2
Test the correctness of inverse:
• g(3) = 2*3 - 1 = 5
• g-1 (5) = (5+1)/2 = 3
• g(10) = 2*10 - 1 = 19
• g-1 (19) =
CS 441 Discrete mathematics for CS M. Hauskrecht
Inverse functions
Example 2:
• Let g : R ? R, where g(x) = 2x - 1.
• What is the inverse function g-1 ?
Approach to determine the inverse:
y = 2x - 1 => y + 1 = 2x
=> (y+1)/2 = x
• Define g-1(y) = x= (y+1)/2
Test the correctness of inverse:
• g(3) = 2*3 - 1 = 5
• g-1 (5) = (5+1)/2 = 3
• g(10) = 2*10 - 1 = 19
• g-1 (19) = (19+1)/2 = 10.
18
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Definition: Let f be a function from set A to set B and let g be a
function from set B to set C. The composition of the functions
g and f, denoted by g ? f is defined by
• (g ? f)(a) = g(f(a)).
A f: A ? B B g: B ? C C
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c,d}
g : A ? A, f: A ? B
1 ?3 1 ? b
2 ?1 2 ? a
3 ?2 3 ? d
f ? g : A ? B:
• 1 ?
19
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c,d}
g : A ? A, f: A ? B
1 ?3 1 ? b
2 ?1 2 ? a
3 ?2 3 ? d
f ? g : A ? B:
• 1 ? d
• 2 ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c,d}
g : A ? A, f: A ? B
1 ?3 1 ? b
2 ?1 2 ? a
3 ?2 3 ? d
f ? g : A ? B:
• 1 ? d
• 2 ? b
• 3 ?
20
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c,d}
g : A ? A, f: A ? B
1 ?3 1 ? b
2 ?1 2 ? a
3 ?2 3 ? d
f ? g : A ? B:
• 1 ? d
• 2 ? b
• 3 ? a
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 2:
• Let f and g be two functions from Z to Z, where
• f(x) = 2x and g(x) = x2.
• f ? g : Z ? Z
• (f ? g)(x) = f(g(x))
= f( x2 )
= 2(x2)
• g ? f : Z ? Z
• (g ? f)(x) = ?
21
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 2:
• Let f and g be two functions from Z to Z, where
• f(x) = 2x and g(x) = x2.
• f ? g : Z ? Z
• (f ? g)(x) = f(g(x))
= f( x2 )
= 2(x2)
• g ? f : Z ? Z
• (g ? f)(x) = g(f(x))
= g(2x)
= (2x) 2
= 4x2
Note that the order of
the function composition matters
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 3:
• (f ? f -1)(x) = x and (f -1 ? f)(x) = x, for all x.
• Let f : R ? R, where f(x) = 2x – 1 and f -1 (x) = (x+1)/2.
• (f ? f -1 )(x)= f(f -1 (x))
= f( (x+1)/2 )
= 2( (x+1)/2 ) - 1
= (x+1) - 1
= x
22
CS 441 Discrete mathematics for CS M. Hauskrecht
Composition of functions
Example 3:
• (f ? f -1)(x) = x and (f -1 ? f)(x) = x, for all x.
• Let f : R ? R, where f(x) = 2x – 1 and f -1 (x) = (x+1)/2.
• (f ? f -1 )(x)= f(f -1 (x))
= f( (x+1)/2 )
= 2( (x+1)/2 ) - 1
= (x+1) - 1
= x
• (f -1 ? f)(x) = f -1 (f(x))
= f -1 ( 2x - 1 )
= (2x)/2
= x
CS 441 Discrete mathematics for CS M. Hauskrecht