DIGITAL NOTES
ON
Discrete Mathematics
B.TECH II YEAR - I SEM
(2019-20)
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
(Autonomous Institution – UGC, Govt. of India)
(Affiliated to JNTUH, Hyderabad, Approved by AICTE - Accredited by NBA & NAAC – ‘A’ Grade - ISO 9001:2015 Certified)
Maisammaguda, Dhulapally (Post Via. Hakimpet), Secunderabad – 500100, Telangana State, INDIA.
, MAL MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
II Year B.Tech CSE – I Sem
T/P/D C L
3 /-/- 3
(R18A0506) Discrete Mathematics
UNIT-I
Mathematical Logic : Statements and notations, Connectives, Well formed formulas, Truth
Tables, tautology, equivalence implication, Normal forms, Quantifiers, universal quantifiers.
Predicates : Predicative logic, Free & Bound variables, Rules of inference, Consistency,
proof of contradiction, Automatic Theorem Proving.
UNIT-II
Relations: Properties of Binary Relations, equivalence, transitive closure, compatibility and
partial ordering relations, Lattices, Hasse diagram. Functions: Inverse Function Composition
of functions, recursive Functions, Lattice and its Properties,
Algebraic structures : Algebraic systems Examples and general properties, Semigroups and
monads, groups sub groups’ homomorphism, Isomorphism.
UNIT-III
Elementary Combinatorics: Basis of counting, Combinations & Permutations, with
repetitions, Constrained repetitions, Binomial Coefficients, Binomial Multinomial theorems,
the principles of Inclusion – Exclusion. Pigeon hole principles and its application.
UNIT-IV
Recurrence Relation : Generating Functions, Function of Sequences Calculating Coefficient
of generating function, Recurrence relations, Solving recurrence relation by substitution and
Generating funds. Characteristics roots solution of In homogeneous Recurrence Relation.
UNIT-V
Graph Theory : Representation of Graph, DFS, BFS, Spanning Trees, planar Graphs. Graph
Theory and Applications, Basic Concepts Isomorphism and Sub graphs, Multi graphs and
Euler circuits, Hamiltonian graphs, Chromatic Numbers.
TEXT BOOKS:
1. Elements of DISCRETE MATHEMATICS- A computer Oriented Approach- C L
Liu, D P Mohapatra. Third Edition, Tata McGraw Hill.
2. Discrete Mathematics for Computer Scientists & Mathematicians, J.L. Mott, A.
Kandel, T.P. Baker, PHI.
REFERENCE BOOKS:
1. Discrete Mathematics and its Applications, Kenneth H. Rosen, Fifth Edition.TMH.
2. Discrete Mathematical structures Theory and application-Malik & Sen, Cengage.
3. Discrete Mathematics with Applications, Thomas Koshy, Elsevier.
4. Logic and Discrete Mathematics, Grass Man & Trembley, Pearson Education.
, MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
INDEX
S. No Topic Page no
Unit
1 MATHEMATICAL LOGIC 1
I
2 PREDICATES 10
I
I
3 RULES OF INFERENCE 11
II
4 RELATIONS 22
II
5 FUINCTIONS 31
II
6 ALGEBRAIC STRUCTURES 36
III
7 ELEMENTARY COMBINATORICS 42
III
8 BINOMIAL COEFFICIENTS 49
III
9 PEGION HOLE PRINCIPLE 54
IV
10 RECURRENCE RELATION 57
IV
11 SOLVING RECURRENCE RELATION 61
V
12 GRAPH THEORY 65
V
13 APPLICATIONS OF GRAPH 73
V
14 MULTIGRAPHS & EULER CIRCUITS 76
V
15 CHROMATIC NUMBERS 79
, MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
UNIT-I
Mathematical Logic
Statements and notations:
A proposition or statement is a declarative sentence that is either true or false (but not both).
For instance, the following are propositions:
Paris is in France< (true)
London is in Denmark< (false)
2 < 4 < (true)
4 = 7< (false)
However the following are not propositions:
what is your name?< (this is a question)
do your homework< (this is a command)
this sentence is false< (neither true nor false)
x is an even number< (it depends on what x represents)
Socrates< (it is not even a sentence)
The truth or falsehood of a proposition is called its truth value.
Connectives:
Connectives are used for making compound propositions. Generally used five connectives are –
OR (V)
AND (K)
Negation/ NOT (¬)
Implication / if-then (→)
If and only if ( ¤ ).
Well formed formulas (wff):
The strings that produce a proposition when their symbols are interpreted must follow the
rules given below, and they are called wffs(well-formed formulas) of the first order
predicate logic.
DM 1
ON
Discrete Mathematics
B.TECH II YEAR - I SEM
(2019-20)
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
(Autonomous Institution – UGC, Govt. of India)
(Affiliated to JNTUH, Hyderabad, Approved by AICTE - Accredited by NBA & NAAC – ‘A’ Grade - ISO 9001:2015 Certified)
Maisammaguda, Dhulapally (Post Via. Hakimpet), Secunderabad – 500100, Telangana State, INDIA.
, MAL MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
II Year B.Tech CSE – I Sem
T/P/D C L
3 /-/- 3
(R18A0506) Discrete Mathematics
UNIT-I
Mathematical Logic : Statements and notations, Connectives, Well formed formulas, Truth
Tables, tautology, equivalence implication, Normal forms, Quantifiers, universal quantifiers.
Predicates : Predicative logic, Free & Bound variables, Rules of inference, Consistency,
proof of contradiction, Automatic Theorem Proving.
UNIT-II
Relations: Properties of Binary Relations, equivalence, transitive closure, compatibility and
partial ordering relations, Lattices, Hasse diagram. Functions: Inverse Function Composition
of functions, recursive Functions, Lattice and its Properties,
Algebraic structures : Algebraic systems Examples and general properties, Semigroups and
monads, groups sub groups’ homomorphism, Isomorphism.
UNIT-III
Elementary Combinatorics: Basis of counting, Combinations & Permutations, with
repetitions, Constrained repetitions, Binomial Coefficients, Binomial Multinomial theorems,
the principles of Inclusion – Exclusion. Pigeon hole principles and its application.
UNIT-IV
Recurrence Relation : Generating Functions, Function of Sequences Calculating Coefficient
of generating function, Recurrence relations, Solving recurrence relation by substitution and
Generating funds. Characteristics roots solution of In homogeneous Recurrence Relation.
UNIT-V
Graph Theory : Representation of Graph, DFS, BFS, Spanning Trees, planar Graphs. Graph
Theory and Applications, Basic Concepts Isomorphism and Sub graphs, Multi graphs and
Euler circuits, Hamiltonian graphs, Chromatic Numbers.
TEXT BOOKS:
1. Elements of DISCRETE MATHEMATICS- A computer Oriented Approach- C L
Liu, D P Mohapatra. Third Edition, Tata McGraw Hill.
2. Discrete Mathematics for Computer Scientists & Mathematicians, J.L. Mott, A.
Kandel, T.P. Baker, PHI.
REFERENCE BOOKS:
1. Discrete Mathematics and its Applications, Kenneth H. Rosen, Fifth Edition.TMH.
2. Discrete Mathematical structures Theory and application-Malik & Sen, Cengage.
3. Discrete Mathematics with Applications, Thomas Koshy, Elsevier.
4. Logic and Discrete Mathematics, Grass Man & Trembley, Pearson Education.
, MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
INDEX
S. No Topic Page no
Unit
1 MATHEMATICAL LOGIC 1
I
2 PREDICATES 10
I
I
3 RULES OF INFERENCE 11
II
4 RELATIONS 22
II
5 FUINCTIONS 31
II
6 ALGEBRAIC STRUCTURES 36
III
7 ELEMENTARY COMBINATORICS 42
III
8 BINOMIAL COEFFICIENTS 49
III
9 PEGION HOLE PRINCIPLE 54
IV
10 RECURRENCE RELATION 57
IV
11 SOLVING RECURRENCE RELATION 61
V
12 GRAPH THEORY 65
V
13 APPLICATIONS OF GRAPH 73
V
14 MULTIGRAPHS & EULER CIRCUITS 76
V
15 CHROMATIC NUMBERS 79
, MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
UNIT-I
Mathematical Logic
Statements and notations:
A proposition or statement is a declarative sentence that is either true or false (but not both).
For instance, the following are propositions:
Paris is in France< (true)
London is in Denmark< (false)
2 < 4 < (true)
4 = 7< (false)
However the following are not propositions:
what is your name?< (this is a question)
do your homework< (this is a command)
this sentence is false< (neither true nor false)
x is an even number< (it depends on what x represents)
Socrates< (it is not even a sentence)
The truth or falsehood of a proposition is called its truth value.
Connectives:
Connectives are used for making compound propositions. Generally used five connectives are –
OR (V)
AND (K)
Negation/ NOT (¬)
Implication / if-then (→)
If and only if ( ¤ ).
Well formed formulas (wff):
The strings that produce a proposition when their symbols are interpreted must follow the
rules given below, and they are called wffs(well-formed formulas) of the first order
predicate logic.
DM 1
