Discrete Stuctures and Graph
Theory
Course Content
Text Books
• “Discrete Mathematics and Its Applications”, Kenneth H. Rosen, 7th
Edition, Tata McGraw-Hill, 2017, ISBN: 9780073383095.
• “Elements of Discrete Mathematics”, C. L. LIU, 4th Edition, Tata
McGraw-Hill, 2017, ISBN-10: 1259006395 ISBN-13: 978125
9006395.
Reference Books
• ”Discrete Mathematical Structures”, G. Shanker Rao, 2 nd Edition2009,
New Age International, ISBN-10: 8122426697, ISBN-13: 9788122426694
• “Discrete Mathematics”, Lipschutz, Lipson, 2nd Edition, 1999, Tata
McGraw-Hill, ISBN: 007 463710X.
• “Graph Theory”, V. K. Balakrishnan, 1 st Edition, 2004, Tata McGraw-Hill ,
ISBN-10: 0- 07-058718-3, ISBN-13: 9780070587182.
• “Discrete Mathematical Structures”, B. Kolman, R. Busby and S. Ross, 4th
Edition, Pearson Education, 2002, ISBN: 8178085569
• “Discrete Mathematical Structures with application to Computer Science”,
J. Tremblay, R. Manohar, Tata McGraw-Hill, 2002, ISBN: 0070651426
• “Discrete Mathematics”, R. K. Bisht, H. S. Dhami, Oxford University Press,
ISBN: 9780199452798
Introduction to Discrete Mathematics
A B
a = qb+r gcd(a,b) = gcd(b,r)
Why is discrete mathematics?
Logic: artificial intelligence (AI), database, circuit design
Counting: probability, analysis of algorithm
Graph theory: computer network, data structures
Number theory: cryptography, coding theory
logic, sets, functions, relations, etc
Why is discrete mathematics?
GATE core subject
Competitive Exams
Learn Competitive Programming
It Improves:
• Mathematical thinking
• Problem solving ability
• Foundation of all subjects in computer Engineering
What are “discrete structures” ?
“Discrete” - Composed of distinct, separable parts. (Opposite of
continuous.)
discrete:continuous :: digital:analog
“Structures” - Objects built up from simpler objects according
to some definite pattern.
“Discrete Mathematics” - The study of discrete, mathematical
objects and structures.
Logic, Proofs and Set Theory
https://www.youtube.com/watch?v=QmMnLxWVSGM
Lets see what is the Answer
Statements/ Proposition
•Proposition or Statement or An Assertion
•Primary (Primitive, atomic ) statements
•Set of Declarative sentences which cannot be further broken
down into simpler sentences.
•Those who have one and only one of two possible values called
“Truth Values”.
•True and False or T and F or 1 and 0
•Two-valued logic
•Some statements can be assertion but not the propositions
• Ex. “This statement is false”
Statement (Proposition)
A Statement is a sentence that is either True or False
Examples: 2+2=4 True
3x3=8 False
787009911 is a prime
Non-examples: x+y>0
x2+y2=z2
They are true for some values of x and y
but are false for some other values of x and y.
The Statement/Proposition Game
• “Elephants are bigger than ant.”
Is this a statement? yes
Is this a proposition? yes
What is the truth value
of the proposition? true
The Statement/Proposition Game
• “520 < 111”
Is this a statement? yes
Is this a proposition? yes
What is the truth value
of the proposition? false
The Statement/Proposition Game
• “Please do not fall asleep.”
Is this a statement? no
It’s a request.
Is this a proposition? no
Only statements can be propositions.
Examples of statements/ Propositions
All the following declarative sentences are propositions.
1. Washington, D.C., is the capital of the United States of
America.
2. Toronto is the capital of Canada.
3. 1 + 1 = 2.
4. 2 + 2 = 3.
Propositions 1 and 3 are true, whereas 2 and 4 are false.
Examples
• Consider the following sentences.
1. What time is it?
2. Read this carefully.
3. x + 1 = 2.
4. x + y = z.
Sentences 1 and 2 are not propositions because they are not
declarative sentences.
Sentences 3 and 4 are not propositions because they are neither
true nor false.
Note that each of sentences 3 and 4 can be turned into a
proposition if we assign values to the variables
Class Assignement
• Which of these sentences are propositions? What are the truth values of those that
are propositions?
a) Boston is the capital of Massachusetts.
b) Miami is the capital of Florida.
c) 2 + 3 = 5.
d) 5 + 7 = 10.
e) x + 2 = 11.
f) Answer this question.
g) Do not pass go.
h) What time is it?
i) There are no black flies in Maine.
j) 4 + x = 5.
k) The moon is made of green cheese.
l) 2n ≥ 100
Class Assignement
• Which of these sentences are propositions? What are the truth values of
those that are propositions?
a) Boston is the capital of Massachusetts. T
b) Miami is the capital of Florida. F
c) 2 + 3 = 5. T
d) 5 + 7 = 10. F
e) x + 2 = 11.
f) Answer this question.
g) Do not pass go.
h) What time is it?
i) 4 + x = 5.
j) The moon is made of green cheese. F
k) 2n ≥ 100
Operators/ Connectives
• An operator or connective combines one or more
operand expressions into a larger expression.
• Two types of declarative sentences
• First is Primitive or primary or atomic statement
• Denoted by Capital letters A,B,C…..P,Q,R…
P: London is capital of India.
A:Ram is poor.
• Second types are obtained from primitives using connectives and
parenthesis.
• Called molecular or compound statements
• Like statements connective also denoted by symbol
Examples
e.g.
1. India is country and Mumbai is capital of India.
P:India is country
Q:Mumbai is capital of India.
P and Q P ^ Q
2. Ram is poor but he is clever.
A: Ram is poor.
B: Ram is clever.
A and B
Connectives
1. Negation (Not)
2. Conjunction (and)
3. Disjunction (or)
4. Conditional (if…then) /implication
5. Bi-conditional (if and only if)
Connectives’ Symbols
Formal Name Nickname Property Symbol
Negation operator NOT Unary ¬
Conjunction operator AND Binary
Disjunction operator OR Binary
Exclusive-OR operator XOR Binary
Implication operator IMPLIES Binary
Biconditional operator IFF Binary ↔
Lecture 3
• https://web.microsoftstream.com/video/eaf4
01a0-8259-4d61-af55-87efd46b1b92
• https://web.microsoftstream.com/video/6ef3
7cbd-170d-440c-ac61-cfe331ac5816
