Lecture#1

Email: sumaira.mustafa@nu.edu.pk

Office: 131 (First floor)

Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education.
Discrete vs. Continuous

• Discrete Mathematics is all about dealing with distinct or separate

steps.
• It focuses on processes that involve a sequence of individual
steps rather than continuous, uninterrupted changes.
• In simple terms, it looks at things that can be broken down into
countable, distinct parts.
2
Discrete vs Continous
Discrete Continuous

3
Discrete Structures
 The study of mathematical structures that are
fundamentally discrete rather than continuous.
 The objects studied in discrete mathematics – such as
integers, graphs, and statements in logic have distinct,
separated values.
 Discrete mathematics is essential for future courses in
fields like computer science, mathematics, and other
disciplines, providing foundational concepts for areas
such as algorithms, logic, set theory, and network
optimization.

4
Discrete Mathematics vs Discrete Structures
 Discrete Structures are structures that are used in describing
discrete mathematics.
 Discrete Mathematics is math that makes use of discrete
structures.
 "Discrete Math" OR "Discrete Structure" is not the name of a
branch of mathematics, like number theory, algebra, calculus, etc.
Rather, it's a description of a set of branches of math that all have in
common the feature that they are "discrete" rather than
"continuous".
Types of Problems Addressed by
Discrete Mathematics
 How many ways can a password be chosen following
specific rules?
 How many valid Internet addresses are there?
 What is the probability of winning a particular lottery?
 Is there a link between two computers in a network?
 How can I identify spam email messages?
 How can I encrypt a message so that no unintended
recipient can read it?
 How can we build a circuit that adds two integers?
Goals of a Course in Discrete
Mathematics
 Mathematical Reasoning:
 Ability to read, understand, and construct mathematical
arguments and proofs.
 Combinatorial Analysis:
 Techniques for counting objects of different kinds.
 Discrete Structures:
 Abstract mathematical structures that represent objects
and the relationships between them.
 Examples are sets, permutations, relations, graphs, trees,
and finite state machines.
Goals of a Course in Discrete
Mathematics
 Algorithmic Thinking:
 Solving problems by defining algorithms—sequences of
steps to solve a problem. It includes analyzing time and
memory requirements and ensuring correctness.
 Applications and Modeling:
 Discrete mathematics is applied in diverse fields like
computing, chemistry, biology, linguistics, geography,
and business to solve real-world problems and develop
new models.
Propositional Logic
 The phrase “propositional logic” is composed of two
words:
 Proposition
 logic
LOGIC
 Logic is the study of reasoning that helps distinguish
between valid and invalid arguments; it forms the
foundation for constructing correct mathematical
statements.
 For Example:
 Rules of logic enable us to understand about the
mathematical statements like:
 For every positive integer n, the sum of positive integers not
exceeding n is n(n+1)/2.
 Either it is a valid mathematical argument or invalid argument

10
Proposition
 Proposition is a declarative sentence (a sentence that
is declaring a fact or stating an argument) that is either
true or false but not both.
 If a proposition is true, we say that it has a truth value
of "true”.
 If a proposition is false, its truth value is "false".
 The truth values “true” and “false” are, respectively,
denoted by the letters T and F.

11
Examples

12
Statement
 If the sentence is preceded by other sentences that
make the pronoun or variable reference clear, then
the sentence is a statement.

13
Examples

14
Propositional Logic
 Propositional Logic (also called Statement Logic) is a
branch of logic that deals with propositions — statements
that are either true or false, but not both.
 Connectives:
 Compound Propositions; constructed from existing
propositions using logical operators (connectives).
 Negation ¬
 Conjunction ∧ (represents logical operation “AND”)
 Disjunction ∨ (represents logical operation “OR”)
 Implication →
 Biconditional ↔
 Constructing Propositions
 Propositional Variables: p, q, r, s, …
 The proposition that is always true is denoted by T and the
proposition that is always false is denoted by F.
Compound Propositions: Negation
 The negation of a proposition p is denoted by ¬p and
has this truth table:
p ¬p
T F
F T

 Example: If p denotes “The earth is round.”, then ¬p

denotes “It is not the case that the earth is round,” or
more simply “The earth is not round.”
Conjunction
 The conjunction of propositions p and q is denoted
by p ∧ q and has this truth table:
p q p∧q
T T T
T F F
F T F
F F F

 Example: If p denotes “I am at home.” and q denotes

“It is raining.” then p ∧q denotes “I am at home and it
is raining.”
Disjunction
 The disjunction of propositions p and q is denoted
by p ∨q and has this truth table:

p q p ∨q
T T T
T F T
F T T
F F F

 Example: If p denotes “I am at home.” and q denotes

“It is raining.” then p ∨q denotes “I am at home or it is
raining.”
The Connective Or in English
 In English “or” has two distinct meanings.
 “Inclusive Or” - In the sentence “Students who have taken CS202 or
Math120 may take this class,” we assume that students need to have taken
one of the prerequisites, but may have taken both. This is the meaning of
disjunction. For p ∨q to be true, either one or both of p and q must be true.
 “Exclusive Or” - When reading the sentence “Soup or salad comes with
this entrée,” we do not expect to be able to get both soup and salad. This is
the meaning of Exclusive Or (Xor). In p ⊕ q , one of p and q must be true,
but not both. The truth table for ⊕ is:

p q p ⊕q
T T F
T F T
F T T
F F F
Recommended Books:

 Text Book
 Discrete Mathematics with Applications (second
edition) by Susanna S. Epp
 Reference
 Discrete Mathematics and Its Applications (fourth
edition) by Kenneth H. Rosen
 Discrete Mathematics by Ross and Wright

20
 Home Task
Types of Problems Addressed by Discrete Mathematics
 What is the shortest path between two cities using a
transportation system?
 Find the shortest tour that visits each of a group of cities
only once and then ends in the starting city.
 How can we represent English sentences so that a computer
can reason with them?
 How can we prove that there are infinitely many prime
numbers?
 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 always
correctly sorts a list?
 Home Task
 Numbers and their characteristics: