PRESENTATION
OF DISCRETE
STRUCTURES
WISHAH ZUBAIR (37)
KINZA ALI(05)
SOMI JAMAL(44)
SABA NOOR(21)
Dep: BSCS
Section :A
Semester:2
FUNCTIONS
In discrete structures, a function is a
fundamental concept that describes a relationship
between elements of two sets, where each element
of the first set (called the domain) is related to
exactly one element of the second set (called the
codomain). In simpler terms, a function assigns
Formally, a function 𝑓f from set 𝐴A to set 𝐵B,
exactly one output value to each input value.
denoted as 𝑓:𝐴→𝐵f:A→B, is a rule or
correspondence that assigns to each element 𝑥x in
set 𝐴A exactly one element 𝑦y in set 𝐵B.
EXAMPLE
DAILY LIFE EXAMPLE
Consider the conversion of temperature from Celsius
𝑓:𝑅→𝑅f:R→R where 𝑅R represents the set of real
to Fahrenheit or vice versa. Let's take the function
numbers.
formula 𝐹=95𝐶+32F=59C+32.
To convert Celsius (𝐶C) to Fahrenheit (𝐹F), we use the
formula 𝐶=59(𝐹−32)C=95(F−32).
To convert Fahrenheit (𝐹F) to Celsius (𝐶C), we use the
In both cases, these formulas represent functions.
Each input temperature value (in Celsius or
Fahrenheit) is mapped to a unique output temperature
value (in Fahrenheit or Celsius).
TYPES OF FUNCTION
Injective (One-to-One) Function:
Surjective (Onto) Function:
Bijective Function:
Injective (One-to-One)
Function:
Definition: A function where each element of
the domain maps to a unique element of the
codomain.
A function ‘f’ from get ‘A’ to set ‘B’ is one to
one if no two elements in ‘A’ are mapped to
same element in ‘B’.
In other words, an injective function ensures
that different elements in the domain are
mapped to different elements in the codomain.
EXAMPLE:
DAILY LIFE EXAMPLE:
In a library, each book is assigned a unique
identification number or code. This identification
number serves as a way to uniquely identify each book
identification number as 𝑓( 𝑥) f(x), where 𝑥x represents
in the library's catalog system. Let's denote this
the book.
The domain 𝐴A consists of all the books in the library.
In this scenario:
The codomain 𝐵B consists of all possible identification
The function 𝑓:𝐴→𝐵f:A→B maps each book to its
numbers.
corresponding identification number.
Surjective (Onto)
Function:
Definition: A function where every element
of the codomain is mapped to by at least
one element of the domain.
A function ‘f’ from set ‘A’ to set ‘B’ is onto if
each element of ‘B’ is mapped to atleast one
element of ‘A’ .
In other words, a surjective function ensures
that every element in the codomain is the
image of at least one element in the domain.
EXAMPLE:
DAILY LIFE EXAMPLE:
Imagine you are hosting a party, and you have a variety
of drinks available for your guests. Let's say you have
three types of drinks: water, soda, and juice. Your guests
Domain 𝐴A: Set of guests at the party.
can choose from these options.
Codomain 𝐵B: Set of all possible drink options (water,
The function 𝑓:𝐴→𝐵f:A→B maps each guest to their
soda, juice).
chosen drink.
This function is surjective because every possible drink
at the party. In other words, for every drink option 𝑦y,
option (water, soda, juice) is served to at least one guest
there exists at least one guest 𝑥x such
Bijective Function:
Definition: A function that is
both injective and surjective.
A function ‘f’ : A-> B is bijective
if ‘f’ is both one to one(Injective)
and onto(Surjective).
EXAMPLE:
DAILY LIFE EXAMPLE:
A common daily life example of a
bijective function is a key and lock
system. Each key (input) corresponds to
exactly one lock (output), and each lock
has exactly one corresponding key. This
demonstrates both injectivity (each lock
has a unique key) and surjectivity (every
lock can be opened by its corresponding
key).
