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.