Discrete
mathematics
Lecture 1
Intro to Discrete mathematics
Proposition
“
Respect all in your class
Marks Distribution
Marks
Quizes
10%
Assignments
Final Term 20% Quizes
50%
Assignments
Mid term Mid term
20% Final Term
3
Contact me
lailanadeem.bukc@bahria.edu.pk
4
Timeline
18th September, 23 20th November, 23
Start of semester Course after mid
13th November, 23 15th January, 23
Midterm Final Term
5
Course Outline of discrete
mathematics ( discrete structures)
01. Mathematical 02. Basic Structures
reasoning
propositional and predicate Sets, Functions, Relation,
logic, rules of inference, Sequences, Sums
proof by induction, proof by
contraposition, proof by
contradiction, proof by
implication,
03. Induction and 04. Counting 05. Graphs and Trees
Recursion Graphs and Graph Models, Graph Terminology
Mathematical Induction, The Basics of Counting, The and Special Types of Graphs, Representing
Recursive Algorithms Pigeonhole Principle, Graphs and Graph Isomorphism, Connectivity,
Permutations and Euler and Hamilton Paths, Shortest-Path
Combinations Problems, Introduction to Trees, Applications
of Trees, Tree Traversal, Spanning Tree
6
Book
Lets start the
content
Introduction
Discrete mathematics is the part of
mathematics devoted to the study
of discrete objects
9
Discrete Structures/Mathematics
Discrete mathematics deals with objects that
come in discrete bundles,e.g.,1 or 2 b o o k s
Continuous mathematics deals with objects that vary continuously, e.g.,
3.42 inches from a wall.
10
Why Discrete Mathematics?
• The basis of all of digital information
processing is: Discrete manipulations of discrete structures
represented in memory.
• It’s the basic language and conceptual foundation for all
of computer science.
11
Logic and Proofs
Logic is study of reasoning
e.g
A>B>C
So we can say that
A>C
12
Proposition
13
Examples
14
Examples
15
Test
• 2+ 2 = 4 Proposition
• X + y =4 No
• Are you hungry?
No
• I am Happy Proposition
• It is raining today. proposition
16
Propositional logic
The area of logic that deals with
the proposition is called
propositional logic
17
compound propositions
Many mathematical statements are
constructed by combining one or
more propositions, called
compound propositions,
formed from existing propositions
using logical operators.
18
example
Simple propositions
p: “A student who has taken calculus can take this class”
q: “A student who has taken introductory computer science can
take this class.
Compound Proposition
“Students who have taken calculus or introductory computer
science can take this class”
19
Boolean operators
20
negation
“Vandana’s smartphone has at least 32 GB of
“Michael’s PC runs Linux” memory”
“It is not the case that Michael’s ????
PC runs Linux.” This negation can
be more simply expressed as
“Michael’s PC does not run Linux.”
21
Truth table for negation
22
• p: necessary to pass discrete
mathematics
conjunction • q: necessary to pass English
• p ∧ q:
Let p and q be propositions.
The conjunction of p and q,
denoted by p ∧ q, is the proposition
“p and q.” • Truth table
The conjunction p ∧ q is true when
both p and q are true and is false
otherwise.
23
• p: necessary to pass discrete
mathematics
disjunction • q: necessary to pass English
• p ∨ q:
Let p and q be propositions.
The disjunction of p and q, denoted
by p ∨ q, is the proposition “p or q.”
The disjunction p ∨ q is false when
• Truth table
both p and q are false and is true
otherwise.
It is “inclusive or” means true when
both true
24
• p: Leena is a singer
Natural language is • q: Leena is a writer
ambiguous • p or q:
Note that English “or” can be
ambiguous regarding the “both”
case
• p: Leena is a man
Need context to disambiguate the • q: Leena is a woman
meaning
• p or q:
25
Exclusive or operator
26
• p: “A student can have a salad with
dinner”
example • q: “A student can have soup with
dinner,”
•pVq
•p⊕q
27
The implication • p: I am elected
operator • q: I will lower taxes
The conditional statement p → q is
• If I am elected, then I will lower taxes
the proposition
“if p, then q.” p q P -> q
The conditional statement p → q is
false when p is true and q is false,
and true otherwise.
p is called the hypothesis (premise)
q is called the conclusion (or
consequence)
28
example “If Maria learns discrete mathematics, then she
will find a good job.”
There are many other ways to express this
conditional statement in English. Among the
“If
it is sunny, then we will go to the most natural of these are
beach” • “Maria will find a good job when she learns
discrete mathematics.”
• “For Maria to get a good job, it is sufficient
for her to learn discrete mathematics.” and
• “Maria will find a good job unless she does
not learn discrete mathematics.”
29
CONVERSE,
CONTRAPOSITIVE, If it is raining, then the home team wins
AND INVERSE If p then q…….. p q
Converse
If q then p
The proposition q → p is called the
converse of p → q.
The contrapositive of p → q is the Contrapositive
proposition ¬q → ¬p. -q -p
The proposition ¬p → ¬q is called the
inverse of p → q
Inverse
-p -q
30
• “You can take the flight if and only if
you buy a ticket.”
BICONDITIONALS
Let p and q be propositions.
The biconditional statement p ↔ q is
the proposition “p if and only if q.”
The biconditional statement p ↔ q is
true when p and q have the same truth
values, and is false otherwise.
Biconditional statements are also
called bi-implications
31
• (p ∨ ¬q) → (p ∧ q).
Truth Tables of
Compound Propositions
p q -q p ∨ ¬q p∧ (p ∨ ¬q) →
q (p ∧ q).
Construct the truth table of the
compound proposition
(p ∨ ¬q) → (p ∧ q).
32
Precedence of Logical
Operators
Negation Conjunction Disjunction Implication Biconditional
33
• Table for bit operator
Logic and Bit Truth value bits
Operations T 1
F 0
Computers represent information
using bits. x y x∨y x∧y X⊕y
A bit is a symbol with two possible
1 1
values, namely, 0 (zero) and 1
(one). 1 0
This meaning of the word bit comes
0 1
from binary digit, because zeros
and ones are the digits used in
0 0
binary representations of numbers.
34
example
Find the bitwise OR, bitwise AND,
and bitwise XOR of the bit strings
01 1011 0110 and 11 0001 1101.
35
Exercise 1.1
Q.1 to 40
36
37
