Discrete Mathematics
Discrete Mathematics
Book
Discrete Mathematics and Its Applications
Seventh Edition
By K. H. Rosen
Discrete Mathematics
Particular value
Number of students in your class? 50, 60 or 45
Height of students in your class?
continues value, vary from student to student
Yes, No
Today is Friday. True, false
1, 0
Discrete mathematics is the study of mathematical structures
that are countable or otherwise distinct and separable.
Discrete Mathematics
Discrete mathematics is like a special kind of math that
focuses on things you can count or keep separate from
each other. Instead of dealing with smooth and
continuous things, it looks at distinct and individual
pieces, like whole numbers or separate objects.
Digital : Discrete
Analog : Continuous
Discrete Mathematics
Discrete Math 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 the common feature that they are
"discrete" rather than "continuous".
Discrete Mathematics
Generally: Logics making and problem-solving capabilities
In computer science: better understanding of digital computers
high
low
Discrete Mathematics
Some basics
Statement or Proposition
A statement that you can determine to be either true or false.
Examples:
Grass is green.
4+2=6
4+2=8
Discrete Mathematics
There are four figures in a hand.
Close the door.
X is grater than 2.
He is very rich.
X>2
X + 2 is positive
May I come in?
Logic is interesting.
Discrete Mathematics
It is hot today.
-1 > 0
X + Y = 12
Discrete Mathematics
Compound Statement
A combination of two or more propositions using AND, OR,
and NOT operators (logical connectives).
Grass is green OR 4 + 2 = 0
Grass is green OR 4 + 2 = 0 AND 4 + 2 = 7
Discrete Mathematics
Connective Meaning Symbol Called
Negation not ~ Tilde
Conjunction and ^ Hat
Disjunction Or V Vel
Discrete Mathematics
Grass is green OR 4 + 2 = 0 AND 4 + 2 = 7
pv q ^r
p = grass is green
q=4+2=6
r=4+2=7
Discrete Mathematics
Let p = “It is hot”, and q = “it is sunny”
Propositions Symbolic Form
It is not hot. ~p
It is hot and sunny. p^q
It is hot or sunny. pvq
It is not hot but sunny. ~p^q
It is neither hot nor sunny. ~p ^ ~q
Discrete Mathematics
Let h = “Zia is healthy”
w = “Zia is wealthy”
s = “Zia is wise”
Propositions Symbolic Form
Zia is healthy and wealthy but not wise. (h ^ w) ^ ~s
Zia is not wealthy, but he is healthy and wise. ~w ^ (h ^ s)
Zia is neither healthy, wealthy nor wise. ~h ^ ~w ^ ~s
Discrete Mathematics
Negation (~)
If p is a statement variable, then negation of p, "not p", is
denoted as "~p".
It has opposite truth value from p i.e., if p is true, then ~p is
false; if p is false, then ~p is true.
Truth table for ~p
p ~p
T F
F T
Discrete Mathematics
Conjunction (^)
If p and q are statements, then the conjunction of p and q
is "a and p", denoted as "p ^ q".
Remarks
p ^ q is true only when both p and q are true.
If either p or q is false, or both are false, then p ^ q is false.
p q p^q
T T T
T F F
F T F
F F F
Discrete Mathematics
Disjunction (v) or Inclusive OR
If p & q are statements, then the disjunction of p and q is
"p or q", denoted as "p v q".
Remarks
p v q is true when at least one of p or q is true.
p v q is false only when both p and q are false.
p q pvq
T T T
T F T
F T T
F F F