MCA09

Discrete Mathematics
Year / Semester: 
3rd Semester

Unit-1 : Sets
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.

Unit-2 : Relation
Relations: Cartesian products, Relation - equivalence relation - partition - partial order relation

Unit-3 : Function
Functions: Definition, Inverse functions -  Composition of functions - Properties of functions - Binary operation

Unit- 4 : Mathematical Logic-1                                                                          
Propositions, connectives, conditionals and biconditionals, well formed formulas, tautologies, equivalence of formulas, duality law, normal forms

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

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

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

Unit -8 : Basic Algebraic Structure – II
Basic definition and properties of Ring, Commutative Ring, Integral domain, Field

Unit 9 : Graph Theory
Basic terminology, multigraphs and weighted graphs,Matrix representation of graph,

paths and circuits : Eulerian paths and circuits, Hamiltonian paths and circuits, planar graphs, Trees : Definition – leaf , root , branch node, internal node, Rooted and binary trees , regular m-ary tree