Discrete Mathematics

MA25C14:

Discrete Mathematics

Course Objective:

The Objectives of the course are to Introduce foundational concepts of set theory, relations, functions, and recurrence relations relevant to modeling data and algorithmic structures and to explain principles of propositional and predicate logic, Boolean algebra, and lattice theory for reasoning and decision-making in AI systems and to present core ideas of graph theory and its applications to analyze and optimize networks, data structures, and intelligent systems.

Set Theory, Relations and Functions: Set theory – inductive definition of sets and proof by induction– Peano postulates – Relations – equivalence relations and partitions. Functions –Type of functions: Injective, surjective and bijective functions –Composition of functions – Inverse functions – Permutation functions – Recurrence relations – Solving linear recurrence relations.

Activities: Create and present Venn diagrams to illustrate union, intersection. Categorize real-world mappings such as student-to-email ID, username-to-password, as injective, surjective, or bijective using role-play or sorting tasks.

Logic : Propositions – Logical operators – Normal forms – Rules of inference – Consistency and inconsistency-Propositional logic – Proofs – Predicates – Quantifiers – Universe of discourse – Logical equivalences and implications for quantified statements – Rules of specification and generalization – Validity of arguments.

Activities: Conduct a truth table building competition for compound propositions using logical operators.

Boolean Algebra and Lattice Theory: 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.

Activities: Draw Hasse diagrams for lattices from a given set and identify sublattices and lattice operations.

Graph Theory: Graphs – Types of graphs – Matrix representation of graphs- Graph isomorphism- Walk – Path – Cycles – Eulerian graphs – Hamiltonian graphs – Planar graphs – Euler formula – Shortest path algorithm: Dijkstra’s algorithm.

Activities: Implement Dijkstra’s algorithm to find the shortest path in a weighted AI decision graph.

Weightage: Continuous Assessment: 40%, End Semester Examinations: 60%

Assessment Methodology: Assignments (20%), Solution to application-oriented problems using software (20%), Solving Competitive Examination questions (20%), Internal Examinations (40%).

References:

1. Tremblay J.P., Manohar R., “Discrete Mathematical Structures with applications to Computer Science”, Tata McGraw-Hill, International Edition, 2017.

2. Kenneth H. Rosen, “Discrete Mathematics and its applications: With Combinatorics and Graph Theory (9th Edition)”, Tata McGraw-Hill, 2025.

3. Mott J.L, Kandel A. and Baker T.P., “Discrete Mathematics for Computer Scientists and Mathematicians”, 2nd Edition, Prentice Hall India, 2015.

4. Liu C.L, “Elements of Discrete Mathematics”, 4th Edition, McGraw Hill, 2017.

5. Grimaldi, R.P. “Discrete and Combinatorial Mathematics: An Applied Introduction”, 5th Edition, Pearson Education Asia, Delhi, 2016.