Department of Computer Science & IT
Instructor: Asif Raza (MSCS)
Discrete Mathematics
Course Objective
Course Objective
• Express statements with the precision of formal logic
• Analyze arguments to test their validity
• Apply the basic properties and operations related to sets
• Apply to sets the basic properties and operations related to relations and
function
• Define terms recursively
• Prove a formula using mathematical induction
• Prove statements using direct and indirect methods
• Compute probability of simple and conditional events
• Identify and use the formulas of combinatorics in different problems
• Illustrate the basic definitions of graph theory and properties of graphs
• Relate each major topic in Discrete Mathematics to an application area in
computing
Recommended Books
Recommended Books
• Discrete Mathematics with Applications (second edition) by Susanna S. Epp
• Discrete Mathematics and Its Applications (fourth edition) by Kenneth H. Rosen
• Discrete Mathematics by Ross and Wright
Main Topics
Main Topics
1. Logic
2. Sets & Operations on sets
3. Relations & Their Properties
4. Functions
5. Sequences & Series
6. Recurrence Relations
7. Mathematical Induction
8. Loop Invariants
9. Combinatorics
10. Probability
11. Graphs and Trees
Topics Cover Today
What is Discrete Mathematics?
What is Logic ?
What is Proposition?
Examples of Proposition
Rule of Proposition
Understanding Statements
Compound Statement
Symbolic Representation of Statement
List of Logical Connectives
Translating From English To Symbols
Translating From Symbols To English
What is Discrete Mathematics?
What is Discrete Mathematics?
Discrete Mathematics concerns processes that consist of a
sequence of individual steps.
What is Logic ?
What is Logic ?
Logic is the study of the principles and methods that
distinguishes between a valid and an invalid argument.
What is Statement ?
What is Statement ?
A statement is a declarative sentence that is either true or false
but not both.
A statement is also referred to as a Proposition
Examples of Propositions
• 2+2 = 4
• 3*4=12
• It is Sunday today.
• Sky is blue.
Propositions (Continue--)
• 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.
Rule of Proposition
Rule of Proposition
If the sentence is preceded by other sentences that make the
pronoun or variable reference clear, then the sentence is a
statement.
Example
x=1
x>2
x > 2 is a statement with truth-value
FALSE
Example
Bill Gates is an American
He is very rich
He is very rich is a statement with truth-value
TRUE.
Understanding Statements
Understanding Statements
i. x + 2 is positive. Not a statement
ii. Logic is interesting. A statement
iii. It is hot today. A statement
iv. -1 > 0 A statement
v. x + y = 12 Not a statement
Compound Statement
Compound Statement
Simple statements could be used to build a compound
statement.
Compound Statement
I. 3 + 2 = 5” and “Lahore is a city in Pakistan”
II. “The grass is green” or “ It is hot today”
III. “Discrete Mathematics is not difficult to me”
Compound Statement
I. 3 + 2 = 5” and “Lahore is a city in Pakistan”
II. “The grass is green” or “ It is hot today”
III. “Discrete Mathematics is not difficult to me”
And, or, not are called logical connectives.
Symbolic Representation of
Statement
Symbolic Representation of
Statement
Statements are symbolically represented by letters
such as p, q, r,...
Symbolic Representation of
Statement
Statements are symbolically represented by letters
such as p, q, r,...
Example:
p = “Islamabad is the capital of Pakistan”
q = “17 is divisible by 3”
List of Logical Connectives
List of Logical Connectives
Logical Connectives
Example
p = “Islamabad is the capital of Pakistan”
q = “17 is divisible by 3”
p q = “Islamabad is the capital of Pakistan and 17 is divisible by 3”
p q = “Islamabad is the capital of Pakistan or 17 is divisible by 3”
~p = “It is not the case that Islamabad is the capital of Pakistan” or
simply
“Islamabad is not the capital of Pakistan”
Translating From English To
Symbols
Translating From English To Symbols
Translating From Symbols To
English
Translating From Symbols To English
