Website programing

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