Discrete Structures
Introduction
Ahsan Azhar
What is Mathematics, really?
It’s not just about numbers!
Mathematics is much more than that:
Mathematics is, most generally, the study
of any and all certain truths about any and
all well-defined concepts.
But, these concepts can be about numbers, symbols, objects,
images, sounds, anything!
So, what’s this class about?
What are “discrete structures” anyway?
“Discrete” (not “discreet”!) - Composed of distinct, separable parts.
(Opposite of continuous.)
discrete: continuous : : digital: analog
“Structures” - Objects built up from simpler objects according to
some definite pattern.
“Discrete Mathematics” - The mathematical study of discrete
objects and structures.
Discrete Mathematics
When using numbers, we’re much more likely to use ℕ (natural
numbers) and ℤ (whole numbers) than ℚ (fractions) and ℝ (real
numbers).
Reason: ℚ and ℝ are densely ordered
This notion can be defined precisely
Densely Ordered
ℚ, < is densely ordered because
𝑥 ℚ 𝑦 ℚ (𝑥 ≠ 𝑦 𝑧 (𝑥 < 𝑧 & 𝑧 < 𝑦) )
Opposite of densely ordered:
discretely ordered
Yet, ℚ and ℝ can be defined in terms of discrete concepts (as we
have seen)
This means that Discrete Mathematics has no exact borders
Different books and courses treat slightly different topics
Discrete Math used whenever:
Objects are counted
Relationships between finite sets are studied
Processes involving a finite number of steps are analyzed
Discrete Math and Computing
Discrete Math supports computing efforts because information
is stored and manipulated by computing machines in a discrete
fashion
Discrete Math solves problems:
How many ways are there to choose a valid password on a
computer system?
What is the probability of winning a lottery?
Is there a link between two computers in a network?
What is the shortest path between two cities using a
transportation system?
Discrete Math solves problems:
How can a list of integers be sorted so that the integers are in
increasing order?
How many steps are required to do such a sorting?
How can it be proved that a sorting algorithm correctly sorts a
list?
How can a circuit that adds two integers be designed?
How many valid Internet addresses are there?
Why study Discrete Math?
Develop your ability to understand and create mathematical
arguments
Provide mathematical foundations for data structures,
algorithms, database theory, automata theory, formal languages,
compiler theory, computer security, and operating systems.
Discrete Structures We’ll Study
Sets Propositions
Relations Predicates
Functions Quantifiers
Orders of Growth Rules of inference
Sequence Proofs
Sequence as loops Graphs
Time Complexity Trees
Strings
Permutations
Combinations
Have Fun!
Many people find Discrete Mathematics more enjoyable than, for
example, Analysis:
Applicable to just about anything
Some nice puzzles
Highly varied
Our Course Learning Outcomes
CLO Course Learning Outcome (CLO) Taxonomy Mappin
# Level g to PLO
CLO 1 The students will be able to understand basic problems and C2 P2
fundamental concepts of Sets, Functions, Relations, Loops,
Recursion, Quantifiers, and Combinatorics
CLO 2 The students will be able to apply logic proofs, logical C2 P2
reasoning, and models of computation to real problems in
computer science and data networking.
CLO 3 The students will be able to demonstrate how mathematical C2 P2
concepts like graphs and tree concepts are used to solve
problems arising in computer science.
Course Instruments And Grading
Quizzes (20%)
Total 4 quizzes: two before Mids and two After Mids.
Assignments (20%)
Total 4 assignments: two before Mids and two After Mids.
Mid Term (20%)
In 9th week and will cover the content will be studied till 8th week.
Final Term (40%)
After 16 weeks and will cover the content 25% before Mids and rest 75%
from after Mids.
Thanks!
Do you have any questions?
[email protected] F301 - Cab 2- Building A
University of Central Punjab Lahore
CREDITS: This presentation template was created by Slidesgo, and
includes icons by Flaticon and infographics & images by Freepik
