Discrete Mathematics
Definition: Discrete Mathematics equips students with mathematical foundations essential for computer science, emphasizing logical reasoning, proofs, sets, counting, algebraic structures, and graph theory.
Available PYQs:
2019
2020
2024
Praxian Analysis 2025
To add PYQs: Click Here
Detailed Syllabus
Module 1: Sets, Relation and Function
- Operations and Laws of Sets, Cartesian Products, Binary Relation.
- Partial Ordering Relation, Equivalence Relation.
- Image of a Set, Sum and Product of Functions, Bijective functions.
- Inverse and Composite Function, Size of a Set.
- Finite and infinite Sets, Countable and uncountable Sets.
- Cantor’s diagonal argument and The Power Set theorem, Schroeder-Bernstein theorem.
- Principles of Mathematical Induction: The Well-Ordering Principle, Recursive definition.
- The Division algorithm: Prime Numbers, The Greatest Common Divisor – Euclidean Algorithm.
- The Fundamental Theorem of Arithmetic.
Module 2: Basic Counting Techniques
- Inclusion and exclusion principle.
- Pigeon-hole principle.
- Permutation and combination.
Module 3: Propositional Logic
- Syntax, Semantics, Validity and Satisfiability.
- Basic Connectives and Truth Tables.
- Logical Equivalence: The Laws of Logic, Logical Implication, Rules of Inference.
- The use of Quantifiers.
- Proof Techniques: Terminology, Proof Methods and Strategies.
- Forward Proof, Proof by Contradiction, Proof by Contraposition.
- Proof of Necessity and Sufficiency.
Module 4: Algebraic Structures and Morphism
- Algebraic Structures with one Binary Operation: Semi Groups, Monoids, Groups.
- Congruence Relation and Quotient Structures.
- Free and Cyclic Monoids and Groups, Permutation Groups.
- Substructures, Normal Subgroups.
- Algebraic Structures with two Binary Operations: Rings, Integral Domain and Fields.
- Boolean Algebra and Boolean Ring, Identities of Boolean Algebra, Duality.
- Representation of Boolean Function, Disjunctive and Conjunctive Normal Form.
Module 5: Graphs and Trees
- Graphs and their properties: Degree, Connectivity, Path, Cycle, Sub Graph, Isomorphism.
- Eulerian and Hamiltonian Walks.
- Graph Colouring, Colouring maps and Planar Graphs.
- Colouring Vertices, Colouring Edges, List Colouring, Perfect Graph – definition, properties and examples.
- Rooted trees, trees and sorting.
- Weighted trees and prefix codes.
- Bi-connected component and Articulation Points.
- Shortest distances.