Lecture # 1
CHAPTER # 1
Course Objective:
[Link] statements with the precision of formal logic
[Link] arguments to test their validity
[Link] the basic properties and operations related to sets
[Link] to sets the basic properties and operations related to relations and functions
[Link] terms recursively
[Link] a formula using mathematical induction
[Link] statements using direct and indirect methods
[Link] probability of simple and conditional events
[Link] and use the formulas of combinatorics in different problems
[Link] the basic definitions of graph theory and properties of graphs
[Link] each major topic in Discrete Mathematics to an application area in computing
Recommended Books:
[Link] Mathematics with Applications (second edition) by Susanna S. Epp
[Link] Mathematics and Its Applications (fourth edition) by Kenneth H. Rosen
[Link] Mathematics by Ross and Wright
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. Loop Invariants
10. Combinatorics
11. Probability
12. Graphs and Trees
What is Discrete Mathematics?
Discrete mathematics is a branch of mathematics that deals with countable, distinct, and separate objects or structures.
OR
Discrete Mathematics concerns processes that consist of a sequence of individual steps.
APPLICATIONS
It provides the foundation for various areas of computer science, including algorithms, data structures, cryptography, and
among others
LOGIC: Logic is the study of the principles and methods that distinguish between a valid and an invalid argument.
DIFFERENT TYPES OF LOGIC :
1) PROPOSTIONAL LOGIC
2) PREDICATE (FOL: First Order logic) LOGIC
3) HIGHER ORDER LOGIC
4) TEMPORAL LOGIC
5) FUZZY LOGIC
STATEMENT/ PROPOSITIONS:
A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false,
but not both.
It was first developed systematically by the Greek philosopher Aristotle more than 2300 years ago.
1) Logic is interesting. A statement
2) It is hot today. A statement
3) -1 > 0 A statement
4) x + y = 12 Not a statement
PROPOSITIONAL VARIABLES:
We use letters to denote propositional variables (or statement variables), that is, variables that represent
propositions, just as letters are used to denote numerical variables. The conventional letters used for propositional
variables are p, q, r, s, . .
EXAMPLES:
p = “Islamabad is the capital of Pakistan”
q = “17 is divisible by 3”
PREDICATE LOGIC:
If the sentence is preceded by other sentences that make the pronoun or variable reference clear, then the sentence is a
statement.
Not Propositions
Example:
x=1
x>2
x is greater than 2.
He is very rich
Propositions
Example
Bill Gates is an American
He is very rich
“He is very rich”.
COMPOUND PROPOSITIONS:
Many mathematical statements are constructed by combining one or more propositions. New
propositions, called compound propositions, are formed from existing propositions using
logical operators.
EXAMPLES:
1. “3 + 2 = 5” and “Lahore is a city in Pakistan”
2. “The grass is green” or “ It is hot today”
3. “Discrete Mathematics is not difficult to me”
AND, OR, NOT are called LOGICAL CONNECTIVES.
LOGICAL CONNECTIVE:
Truth Table A truth table specifies the truth value of a compound proposition for all possible truth values of its
constituent propositions.
EXAMPLES # 1
COVERT THE FOLLOWING STATEMENTS IN THE SYMBOLIC
REPRESENTATION
p = “Islamabad is the capital of Pakistan”
q = “17 is divisible by 3”
1) “Islamabad is the capital of Pakistan and 17 is divisible by 3”
p∧q
2) “Islamabad is the capital of Pakistan or 17 is divisible by 3”
p∨q
3) “Islamabad is not the capital of Pakistan”
~p
EXAMPLES # 2
TRANSLATING FROM ENGLISH TO SYMBOLS
Let
p = “It is hot”,
q = “ It is sunny”
SENTENCE SYMBOLIC FORM
[Link] is not hot. ~ p
[Link] is hot and sunny. p ∧q
[Link] is hot or sunny. p ∨ q
[Link] is not hot but sunny. ~ p ∧q
[Link] is neither hot nor sunny. ~ p ∧ ~ q
EXAMPLE # 03
Let
h = “Zia is healthy”
w = “Zia is wealthy”
s = “Zia is wise”
Translate the compound statements to symbolic form:
1) Zia is healthy and wealthy but not wise. (h ∧ w) ∧ (~ s)
2) Zia is not wealthy but he is healthy and wise. ~ w ∧ (h ∧ s)
3) Zia is neither healthy, wealthy nor wise. ~h∧~w∧~s
EXAMPLE # 04
TRANSLATING FROM SYMBOLS TO ENGLISH:
Let
m = “Ali is good in Mathematics”
c = “Ali is a Computer Science student”
Translate the following statement forms into plain English:
1) ~ c Ali is not a Computer Science student
2) c∨ m Ali is a Computer Science student or good in Math's.
3) m ∧ ~ c Ali is good in Math's but not a Computer Science student
EXAMPLE # 05
Truth Tables :
1. ~ p ∧ q
2. ~ p ∧ (q ∨ ~ r)
3. (p ∨ q) ∧ ~ (p ∧ q)
DE MORGAN’S LAWS
1) The negation of an AND statement is logically equivalent to the OR statement in
which each component is negated.
Symbolically ~ (p ∧ q) ≡ ~ p ∨ ~ q
2) The negation of an OR statement is logically equivalent to the AND statement in
which each component is negated.
Symbolically ~ (p ∨ q) ≡ ~ p ∧ ~ q
Truth Table of ~ (p ∨ q) ≡ ~ p ∧ ~ q
CONTRADICTION: A contradiction is a
TAUTOLOGY: A tautology is a statement form that is
statement form that is always false regardless
always true regardless of the truth values of the
of the truth values of the statement variables. A
statement variables. A tautology is represented by the
contradiction is represented by the symbol “c”.
symbol “t”.
A compound proposition that is neither a tautology nor a contradiction is called a contingency.
LOGIC AND BIT OPERATIONS: