Mansoura University

Faculty of Computers and Information

Department of Computer Science
First Semester- 2024-2025

Lecture notes for Discrete Mathematics

First Grade
Chapter 3: Functions

◼◼ From calculus, you are familiar with the

concept of a real-valued function f,
which assigns to each number xR a value
y = f(x), where yR.

◼◼ But, the notion of a function can also be

naturally generalized to the concept of
assigning elements of any set to elements of
any set. (Also known as a map.)
Function: Formal Definition
◼◼ For any sets A and B a taht yas ew ,function
(or “mapping )”f from A to B (f :A →B )is a
particular assignment of exactly one element
f(x)B to each element xA.
◼◼ Functions can be represented graphically in
several ways:
f A B
• • y
a• •b •
•
•
f •
•
A B • • x
Like Venn diagrams Bipartite Graph Plot
 Function : assignment

By a function from a set A to a set B we mean an

assignment or rule f such that for every a∈A there is a
unique b∈B such that f(a)=b.
The set A is called the domain of f and the set B is
called the codomain.
We say two functions f and g are equal if they have
the same domain and the same codomain, and if for
every a in the domain, f(a)=g(a).
Some Function Terminology
◼◼ If it is written that f : A → B, and f(a) = b
(where aA and bB), then we say:
◼◼ A is the domain of f
◼◼ B is the codomain of f

◼◼ b is the image of a under f

◼◼ a can not have more than 1 image

◼◼ a is a pre-image of b under f

◼◼ b may have more than 1 pre-image

◼◼ The range RB of f is R = {b | a f(a) = b }

Range versus Codomain
◼◼ The range of a function might not be its whole
codomain.

◼◼ The codomain is the set that the function is

declared to map all domain values into.
◼◼ The range is the particular set of values in the
codomain that the function actually maps
elements of the domain to.
Range vs. Codomain: Example
◼◼ Suppose I declare that: “f is a function
mapping students in this class to the set of
grades {A, B, C, D, F}.”

◼◼ At this point, you know f ’s codomain is:

_{A, _B, C, D_,_F_}_, and its range is _unknown!

◼◼ Suppose the grades turn out all As and Bs.

◼◼ Then the range of f is _{A,_B} , but its

codomain is _still {A,_B, C, D_,_F_}_!
Function Operators
◼◼ + , × (“plus”,“times”) are binary operators
over R. (Normal addition & multiplication.)
◼◼ Therefore, we can also add and multiply two
real-valued functions f,g: R → R:
◼◼ (f + g): R → R, where (f + g)(x) = f(x) + g(x)

◼◼ (fg): R → R, where (fg)(x) = f(x)g(x)

◼◼ Example 6:
Let f and g be functions from R to R
such that f(x) = x2 and g(x) = x – x2.
What are the functions f + g and fg?
 Function Composition Operator
University of

Note the match here. It’s necessary!

◼◼ For functions g: A → B and f : B → C, there is a

special operator called compose (“◦”).
◼◼ It composes (creates) a new function from f and

g by applying f to the result of applying g.

◼◼ We say (f ◦ g): A → C, where (f ◦ g)(a) = f(g(a)).

◼◼ Note: f ◦ g cannot be defined unless range of g

is a subset of the domain of f.

◼◼ Note g(a)B, so f(g(a)) is defined and C.

◼◼ Note that ◦ is non-commuting. (Like Cartesian ,

but unlike +, , ) (Generally, f ◦ g  g ◦ f.)

Function Composition
Illustration
◼◼ g: A → B, f : B → C
Function Composition:
Example
◼◼ g: A → B, f : B → C
Function Composition:
Example
◼◼ Example 20: Let g: {a, b, c} → {a, b, c} such that
g(a) = b, g(b) = c, g(c) = a.
Let f : {a, b, c} → {1, 2, 3} such that
f(a) = 3, f(b) = 2, f(c) = 1.
What is the composition of f and g, and what
is the composition of g and f ?
◼◼ f◦g: {a, b, c} → {1, 2, 3} such that

(f◦g)(a) = 2, (f◦g)(b) = 1, (f◦g)(c) = 3.

(f◦g)(a) = f(g(a)) = f(b) = 2
(f◦g)(b) = f(g(b)) = f(c) = 1
(f◦g)(c) = f(g(c)) = f(a) = 3
◼◼ g◦f is not defined (why?)
Function Composition:
Example
◼◼ If f(x) = x2 and g(x) = 2x + 1, then what is the
composition of f and g, and what is the
composition of g and f ?
◼◼ (f◦g)(x) = f(g(x))
= f(2x+1)
= (2x+1)2
(g◦f)(x) = g(f(x))
◼◼

= g(x 2)
= 2x 2 + 1
Note that f◦g  g◦f. (4x2+4x+1  2x2+1)
Images of Sets under Functions University of Hawaii

◼◼ Given f : A → B, and SA,

◼◼ The image of S under f is simply the set of all
images (under f) of the elements of S.
f(S) = {f(t) | tS}
= {b | tS: f(t) = b}.

◼◼ Note the range of f can be defined as simply

the image (under f) of f ’s domain.
One-to-One Functions
◼◼ A function f is one-to-one (1–1), or injective,
or an injection, iff f(a) = f(b) implies that a = b
for all a and b in the domain of f (i.e. every
element of its range has only 1 pre-image).
◼◼ Formally, given f : A→B,

“f is injective”: a,b (f(a) = f(b) → a = b) or

equivalently a,b (a  b → f(a)  f(b))
◼◼ Only one element of the domain is mapped to
any given one element of the range.
◼◼ Domain & range have the same cardinality.

What about codomain?

One-to-One Illustration
◼◼ Bipartite (2-part) graph representations of
functions that are (or not) one-to-one:
• • • • • •
• • • •
• • •
• • • • •
• • •
• • •
• • •
One-to-one Not one-to-one Not even a function!
◼◼ Example 8:
Is the function f : {a, b, c, d} → {1, 2, 3, 4, 5} with
f(a) = 4, f(b) = 5, f(c) = 1, and f(d) = 3 one-to-one?
◼◼ Example 9:
Let f : Z → Z such that f(x) = x2. Is f one-to-one?
 Sufficient Conditions for
1–1ness
◼◼ For functions f over numbers, we say:
◼◼ f is strictly (or monotonically) increasing

iff x  y → f(x)  f(y) for all x, y in domain;

◼◼ f is strictly (or monotonically) decreasing

iff x  y → f(x)  f(y) for all x, y in domain;

◼◼ If f is either strictly increasing or strictly

decreasing, then f is one-to-one.
◼◼ E.g. x3
Onto (Surjective) Functions
◼◼ A function f : A → B is onto or surjective or a
surjection iff for every element bB there is
an element aA with f(a) = b (bB, aA: f
(a) = b) (i.e. its range is equal to its
codomain).
◼◼ Think: An onto function maps the set A onto

(over, covering) the entirety of the set B, not

just over a piece of it.
◼◼ E.g., for domain & codomain R, x3 is onto,
whereas x2 isn’t. (Why not?)
Illustration of Onto
◼◼ Some functions that are, or are not, onto their
codomains:

◼◼ Example13: Is the function f(x) = x + 1 from

the set of integers to the set of integers onto?
 Bijections and Inverse Function University of

◼◼ A function f is said to be a one-to-one

correspondence, or a bijection, or reversible, or
invertible, iff it is both one-to-one and onto.

◼◼ Let f : A → B be a bijection.
The inverse function of f is the function that
assigns to an element bB the unique element
aA such that f(a) = b.
The inverse function of f is denoted by f -1: B → A.
Hence, f -1(b) = a when f(a) = b.
Inverse Function Illustration
◼◼ Let f: A → B be a bijection

◼◼ Example 16: Let f : {a, b, c} → {1, 2, 3} such that

f(a) = 2, f(b) = 3, f(c) = 1. Is f invertible, and if it is,
what is its inverse? Yes. f–1(1) = c, f–1(2) = a, f–1(3) = b
◼◼ Example 18: Let f be the function from R to R with
f(x) = x2. Is f invertible? No. f is not a one-to-one
function. So it’s not invertible.
 Mappings in Java
◼◼ A discrete function can be represented by a Map
interface or HashMap class in Java programming
language
◼◼ Map map<Integer,String>
= new HashMap<Integer,String>() ;
◼◼ Here, the domain is Integer, the codomain is String
◼◼ We can construct such a mapping by putting all pairs
{a, f(a)} into our map. (a is the key, f(a) is the value.)
◼◼ map.put(2,"Jan");
◼◼ for (Kid kid:kids) {map.put(kid.id,kid.name);}
◼◼ If we put another pair with the same key, it will overwrite
the previous pair – it’s not a function! (May be a bug…)
 Image, Range, Bijection in Java University of Hawaii

◼◼ Map.keys() returns the image

◼◼ it’s a Java Set!

◼◼ map.values() returns the range

◼◼ it’s a Java Set!

◼◼ Is a map a bijection?
Iff the cardinalities of the image and range are the same:
◼◼ if (map.keys().size()==map.values().size()) {
System.out.println("map is a bijection”);
}
Inverse Function in Java
◼◼ Let’s construct an inverse!
◼◼ Prepare the inverse function:
◼◼ Map inverse<String,Integer>
=new HashMap<String,Integer; )(>
◼◼ Here, the domain is String si niamodoc eht ,Integer
◼◼ Go through all keys in map eht fo stnemele lla(image )
otni }yek,eulav{ riap hcae tup dnainverse:
◼◼ for (Integer id:map.keys()) {
String name = map.get(id);
inverse.put(id:name,id;)
}
The Identity Function
◼◼ For any domain A, the identity function
I: A → A (also written as IA, 1, 1A) is the
unique function such that aA: I(a) = a.
◼◼ Note that the identity function is always both
one-to-one and onto (i.e., bijective).
◼◼ For a bijection f : A → B and its inverse
function f -1: B → A,
f −1  f = I A
◼◼ Some identity functions you’ve seen:

◼◼ + 0,  1,  T,  F,  ,  U.
Identity Function Illustrations
◼◼ The identity function:

•
• •
• • y y = I(x) =
x
• •
• •

Domain and range x

 Graphs of Functions
◼◼ We can represent a function f : A → B as a set of
ordered pairs {(a, f(a)) | aA}. ← The function’s graph.

◼◼ Note that aA, there is only 1 pair (a, b).

◼◼ Later : relations loosen this restriction.

◼◼ For functions over numbers, we can represent

an ordered pair (x, y) as a point on a plane.
◼◼ A function is then drawn as a curve (set of

points), with only one y for each x.

Graphsof Functions: Examples
Hawaii
University of

The graph of f(n) = 2n + 1 The graph of f(x) = x2

from Z to Z from Z to Z
 Floor & Ceiling Functions
▪ In discrete math, we frequently use the following two
functions over real numbers:
▪ The floor function ⎣ ・ ⎦ : R → Z, where ⎣x⎦
(“floor of x”) means the largest integer  x,
i.e., ⎣x⎦ = max( {iZ | i  x} ).

E.g. ⎣2.3⎦ = 2, ⎣5⎦ = 5, ⎣–1.2⎦ = –2

▪ The ceiling function ⎡・⎤ : R → Z, where ⎡x⎤

(“ceiling of x”) means the smallest integer ≥ x,

i.e., ⎡x⎤ = min( {i∈Z | i ≥ x} )

E.g. ⎡2.3⎤ = 3, ⎡5⎤ = 5, ⎡–1.2⎤ = –1

 Functions for Computer Science

Floor Function
f (q ) =  q  the largest integer less than or equal to q
where q is rational numbers
f (1.5) = 1.5 = 1, f (−3) =  −3 = −3, f ( −2.7) =  −2.7  = −3
Ceiling Function
f (q ) =  q  the smallest integer greater than or equal to q
where q is rational numbers

f (1.5) = 1.5 = 2, f (−3) =  −3 = −3, f (−2.7) =  −2.7  = −2

School of Software
Floor & Ceiling Functions
Floor & Ceiling Functions
 Plots with Floor/Ceiling:
Example

Graph of (a) Floor ⎣x⎦ (b) Ceiling Functions ⎡x⎤

 Plots with Floor/Ceiling
◼◼ Note that for f(x) = ⎣x⎦ the graph of f includes the
point (a, 0) for all values of a such that
0  a  1, but not for the value a = 1.
◼◼ We say that the set of points (a, 0) that is in f

does not include its limit or boundary point (a,1).

◼◼ Sets that do not include all of their limit points

are called open sets.

◼◼ In a plot, we draw a limit point of a curve using

an open dot (circle) if the limit point is not on the

curve, and with a closed (solid) dot if it is on the
curve.
 Plots with Floor/Ceiling:
Another Example
◼◼ Plot of graph of function f(x) = ⎣x/3⎦
f(x)

Set of points (x, f(x))

2

-6 -3 3 6 x
-2
 References
❑ Discrete Mathematics and Its Applications Seventh Edition 7th Edition
,Kenneth Rosen , McGraw Hill , 2011
❑ Discrete mathematics for computer scientists , Clifford Stein, Robert L.
Drysdale, Kenneth Bogart.
❑ https://drive.google.com/file/d/1km8aUn2bHHbEUGIwuCKSTGeLe-
UDKCoe/view?usp=drive_link