MA 221	DISCRETE MATHEMATICS	3-0-0-6
Prerequistes: Nil Syllabus: Set theory: Sets, relations, equivalence relations, partially ordered sets, functions, countability, lattices and Boolean algebras. Logic: Well-formed formula, interpretations, propositional logic, predicate logic, theory of inference for propositional logic and predicate logic. Combinatorics: Permutations, combinations, recurrences, generating functions, partitions, special numbers like Fibonacci, Stirling and Catalan numbers. Graph Theory: Graphs and digraphs, special types of graphs, isomorphism, connectedness, Euler and Hamilton paths, planar graphs, graph colouring, trees, matching. Textbooks: 1. J. P. Tremblay and R. Manohar, Discrete Mathematics with Applications to Computer Science, Tata McGraw-Hill, 1997. 2. K. H. Rosen, Discrete Mathematics & its Applications, 6th Ed., Tata McGraw-Hill, 2007. References: 1. A. Shen and N. K. Vereshchagin, Basic Set Theory, American Mathematical Society, 2002. 2. A. Kumar, S. Kumaresan and B. K. Sarma, A Foundation Course in Mathematics, Narosa, 2018. 3. M. Huth and M. Ryan, Logic in Computer Science, Cambridge University Press, 2004. 4. V. K. Balakrishnan, Theory and Problems of Combinatorics, Schaum's Series, McGraw-Hill, 1995. 5. R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd Ed., Addison-Wesley, 1994. 6. A. Tucker, Applied Combinatorics, 6th Ed., Wiley, 2012. 7. R. Balakrishnan and K. Ranganathan, A Text Book of Graph Theory, Springer, 2000.