MA3354 DISCRETE MATHEMATICS Anna University Syllabus
MA3354 DISCRETE MATHEMATICS L T P C 3 1 0 4
COURSE OBJECTIVES:
• To extend student’s logical and mathematical maturity and ability to deal with abstraction.
• To introduce most of the basic terminologies used in computer science courses and application of ideas to solve practical problems.
• To understand the basic concepts of combinatorics and graph theory.
• To familiarize the applications of algebraic structures.
• To understand the concepts and significance of lattices and boolean algebra which are widely used in computer science and engineering.
UNIT I LOGIC AND PROOFS 9+3
Propositional logic – Propositional equivalences – Predicates and quantifiers – Nested quantifiers – Rules of inference – Introduction to proofs – Proof methods and strategy.
UNIT II COMBINATORICS 9+3
Mathematical induction – Strong induction and well ordering – The basics of counting – The pigeonhole principle – Permutations and combinations – Recurrence relations – Solving linear recurrence relations
– Generating functions – Inclusion and exclusion principle and its applications.
UNIT III GRAPHS 9+3
Graphs and graph models – Graph terminology and special types of graphs – Matrix representation of graphs and graph isomorphism – Connectivity – Euler and Hamilton paths.
UNIT IV ALGEBRAIC STRUCTURES 9+3
Algebraic systems – Semi groups and monoids – Groups – Subgroups – Homomorphism’s – Normal subgroup and cosets – Lagrange’s theorem – Definitions and examples of Rings and Fields.
UNIT V LATTICES AND BOOLEAN ALGEBRA 9+3
Partial ordering – Posets – Lattices as posets – Properties of lattices – Lattices as algebraic systems – Sub lattices – Direct product and homomorphism – Some special lattices – Boolean algebra – Sub Boolean Algebra – Boolean Homomorphism.
TOTAL: 60 PERIODS
COURSE OUTCOMES:
At the end of the course, students would :
CO1:Have knowledge of the concepts needed to test the logic of a program.
CO2:Have an understanding in identifying structures on many levels.
CO3:Be aware of a class of functions which transform a finite set into another finite set which relates to input and output functions in computer science.
CO4:Be aware of the counting principles.
CO5:Be exposed to concepts and properties of algebraic structures such as groups, rings and fields.
TEXT BOOKS:
- Rosen. K.H., “Discrete Mathematics and its Applications”, 7th Edition, Tata McGraw Hill Pub. Co. Ltd., New Delhi, Special Indian Edition, 2017.
- Tremblay. J.P. and Manohar. R, “Discrete Mathematical Structures with Applications to Computer Science”, Tata McGraw Hill Pub. Co. Ltd, New Delhi, 30th Reprint, 2011.
REFERENCES:
- Grimaldi. R.P. “Discrete and Combinatorial Mathematics: An Applied Introduction”, 5thEdition, Pearson Education Asia, Delhi, 2013.
- Koshy. T. “Discrete Mathematics with Applications”, Elsevier Publications, 2006.
- Lipschutz. S. and Mark Lipson., “Discrete Mathematics”, Schaum’s Outlines, Tata McGraw Hill Pub. Co. Ltd., New Delhi, 3rd Edition, 2010.