Connectives- well formed formulas - Tautology-Equivalence of formulas , Tautological implications, Duality law, and Normal forms. (Chapter I, Section:1-2.1 to 1-2.4,1-2.6 to 1-2.11, 1-3.1 to 1-3.5)
Validity using Truth Tables - Indirect method -Predicates, Variables ,Quantifiers, Free and bound Variables -Theory of inference for predicate calculus. (Chapter: I, Section:1-4.1 to 1-4.3,1-5.1 to 1-5.5, 1-6.4 ,1-6.5)
Grammars - Types of grammar- Left and Right Derivation- Finite state automata- Definition – DFA,NDFA-Procedure for converting NFA to DFA (Chapter : 7, Section: 7.1,7.2,7.3)
Partial ordering- Poset- Lattices-Duality of Lattices- Boolean algebra-Definition ,Basic Laws – Finite Boolean Algebra , Boolean Expressions- Minimization of Boolean functions by Karnaugh method. (Chapter : 6, Section: 6.1,6.2,6.3,6.4)
Definitions, Types of Graphs - Basic theorems -Walk , Paths, Circuits, Reach ability, Connectedness, Euler graph – Related theorem , Hamiltonian paths & Circuit – Matrix representation of Graphs-Trees - Binary trees -simple theorems –Spanning Trees and Kruskal’s Algorithm(only) . (Chapter: 5, section: 5.1(pg.no:5.1 to 5.11),5.2 (pg.no :5.39,5.40),5.3 (pg.no:5.43 -5 .47))
Reference Book:
1. Discrete Maths by N. C.h S. Iyengar and others 2. Discrete Maths by J.K. Sharma 3. Graph theory for computer science and Engineers by NarsinghDeo
Text Book:
1. P Tremblay and R.P Manohar “Discrete Mathematical Structures with applications to computer science”, McGraw Hill, 1975. For units I & II. 2. Discrete Mathematics by Prof.V.Sundaresan, K.S.Ganapathy Subramanian, K.Ganesan, A.R.Puiblications, June 2001. For units III, IV & V.
