Unit 1
Sets: Relationship between sets,
Operations on sets, set identity, principle of
inclusion and exclusion, Min-sets,
Cut-sets. Relations, properties of binary relations,
equivalence relations and partitions,
partial ordering relations, functions, inverse
functions, composition of functions
and lattices, chains and anti-chains,
complemented & distributive
lattices, Boolean algebra, canonical forms
Unit 2
Prepositional logic, conjunction,
disjunction and negation, interpretation of formulas
in prepositional logic, Validity and
consistency, normal form in prepositional logic and
logic consequences, first order
predicate logic
Unit 3
Introduction to finite state machine,
finite state machine as models of physical
system, equivalence machines, finite
state machine as language recognizers.
Unit 4
Introduction to discrete numeric
functions and generating functions, introduction to
combinaric problems, introduction to
recurrence relational and recursive algorithms,
linear recurrence, relations with
constant coefficients, Homogeneous solutions,
particular solutions, total solutions.
Unit 5
Graph: Finite graphs, incidence and
degree, isomorphism, sub graphs and union of
graphs, connectedness, reachability,
paths, and circuits, Eulerian graphs, tree:
properties of trees, pendant vertices
in tree, center of tree ,spanning trees and cut
vertices, binary tree ,matrix
representation of graph, incidence and adjacency matrix
and their propertices, applications of
graphs in computer science.
.
Reference Books:
1. Discrete structure, Schaum series
2. C.L. Liu, Elements of Discrete
mathematics
3. Sahni S., Concepts in Discrete
Mathematics
4. Levy L.S., Discrete Structure of
Computer Science
5. Kanneth H. Rosen, Discrete
Mathematics & Its Applications, Mcgraw Hill
No comments:
Post a Comment