Connectives, well formed formulas- Tautology-Equivalence of formulas, Tautological implications, Duality law, Normal forms
Statement Calculus – Validity using Truth Tables - Indirect method -Predicates, Variables ,Quantifiers, Free and bound Variables -Theory of inference for predicate calculus.
Grammars - Types of grammar- Left and Right Derivation- Finite state automata- Definition – DFA,NDFA-Procedure for converting NFA to DFA
Partial ordering- Poset- Lattices-Duality of Lattices- Boolean algebra-Definition, Basic Laws – Finite Boolean Algebra, Boolean Expressions- Minimization of Boolean functions by Karnaugh method
Definitions, Types of Graphs - Basic theorems -Walk , Paths, Circuits, Reachability, Connectedness, Euler graph – Related theorem , Hamiltonian paths & Circuit –-Trees - Binary trees -simple theorems –Spanning Trees and Kruskal’s Algorithm(only), Matrix representation of Graphs
Reference Book:
1. Discrete Mathematics by N. C.h S. Iyengar and others, Vikas Publication House Pvt Ltd, 2006 2. Discrete Mathematics by J.K. Sharma, Macmillan Publisher India Limited, 2nd Edition, 2009 3. Graph theory for computer science and Engineers by Narsingh Deo. PHI Learning Pvt Ltd, 2013.
Text Book:
1. Discrete Mathematical Structures with applications to computer science by P Tremblay and R.P Manohar , McGraw Hill, 1975. For units I & II. 2. Discrete Mathematics by Prof.V.Sundaresan, K.S.Ganapathy Subramanian, K.Ganesan, A.R.Publications, June 2001. For units III, IV & V.
