MSCIT09

Discrete Mathematics
Year / Semester: 
3rd Semester

Unit-1 : Sets, Relation and Functions
Sets – the Empty Set, Finite and Infinite Set, Equal and Equivalent set, Subsets, Power set, Universal set, Venn Diagram, Complement of a set, set operations. Relations: Cartesian products, Relation - equivalence relation - partition - partial order relation; Functions: Definition, Inverse functions - Composition of functions - Properties of functions - Binary operation

Unit- 2 : Mathematical Logic-1

Propositions, connectives, conditionals and biconditionals, well formed formulas, tautologies, equivalence of formulas, duality law, normal forms

Unit- 3 : Mathematical Logic-2
Inference theory for propositional calculus; predicate calculus: predicates, free and bound variables, inference theory of predicate calculus

Unit- 4 : Counting Principles
The Pigeonhole principle -. counting; Permutation and Combination: Definition of Permutation and combination, Simple application of permutation and combination

Unit- 5 : Basic Algebraic Structure
Definition and basic properties of semi groups and groups; Subgroup and homomorphpism; lattices as partially ordered set, properties of lattice, Boolean algebra

Unit 6: Graph Theory
Basic terminologies;
Representation of graphs: Matrix representation and Adjacency list representation,
Paths and circuits : Topological sort. Minimum spanning tree- Kruskal and Prim’s algorithm, Eulerian paths and circuits, Hamiltonian paths and circuits, planar graphs,
Grapg traversal Techniques=Df Traversal and BF traversal, Weighted Graphs and Bitpartite Graph.
Trees : Definition – leaf , root , branch node, internal node.

Suggested Readings: 

1. Elements of Discrete mathematics: C.L Lieu , Mc Graw Hill

2. Discrete Mathematical Structure with Application to Computer Science: Trembly J.P Mc Graw Hill