Skip to main content

Introduction to Descrete Mathematics

For GATE CSE, Discrete Mathematics is one of the most important subjects because it supports algorithms, theory of computation, compiler design, and computer networks. Here's a structured list of the concepts you should master.

1. Mathematical Logic​

  • Propositions
  • Logical connectives (AND, OR, NOT, XOR)
  • Truth tables
  • Implication and biconditional
  • Converse, inverse, contrapositive
  • Tautology, contradiction, contingency
  • Logical equivalence
  • Quantifiers (∀, ∃)
  • Predicate logic
  • Negation of quantified statements

Frequently asked

  • CNF and DNF
  • Validity of arguments
  • Proof using logical equivalence

2. Set Theory​

  • Sets and subsets
  • Union, intersection, difference
  • Complement
  • Cartesian product
  • Power set
  • Cardinality
  • Venn diagrams
  • Inclusion-Exclusion Principle

3. Relations​

  • Binary relations

  • Properties:

    • Reflexive
    • Symmetric
    • Antisymmetric
    • Transitive

  • Equivalence relations

  • Equivalence classes

  • Partial order

  • Total order

  • Hasse diagrams

  • Closure of relations

    • Reflexive closure
    • Symmetric closure
    • Transitive closure

4. Functions​

  • Types of functions

    • One-one (Injective)
    • Onto (Surjective)
    • Bijective

  • Composite functions

  • Inverse functions

  • Pigeonhole Principle

5. Counting Techniques (Combinatorics)​

  • Basic counting principle
  • Addition rule
  • Multiplication rule
  • Permutations
  • Combinations
  • Circular permutations
  • Binomial theorem
  • Inclusion-Exclusion Principle
  • Derangements (basic idea)

6. Recurrence Relations​

  • Recursive definitions
  • Linear recurrence relations
  • Homogeneous recurrence
  • Non-homogeneous recurrence
  • Solving recurrence equations
  • Characteristic equation method

7. Graph Theory​

  • Graph terminology
  • Types of graphs
  • Degree of vertex
  • Handshaking lemma
  • Connected graphs
  • Components
  • Trees
  • Properties of trees
  • Spanning trees
  • Bipartite graphs
  • Complete graphs
  • Planar graphs
  • Euler paths and circuits
  • Hamiltonian paths and cycles
  • Graph traversal (BFS, DFS)
  • Graph coloring (basic)

8. Trees​

  • Rooted trees
  • Binary trees
  • m-ary trees
  • Tree traversal
  • Expression trees
  • Properties of binary trees

9. Algebraic Structures (Basic)​

  • Groups
  • Semigroups
  • Monoids
  • Rings
  • Fields (only basic definitions)

Usually only basic questions appear in GATE.

10. Proof Techniques​

  • Direct proof
  • Proof by contradiction
  • Proof by contrapositive
  • Mathematical induction
  • Strong induction

Weightage in GATE CSE

Discrete Mathematics typically contributes 6–10 marks in GATE CSE, though the exact weight varies by year. Topics like logic, sets, relations, combinatorics, graph theory, recurrence relations, and induction are especially common and also support questions in algorithms and theory of computation.

Suggested Study Order​

  1. Logic
  2. Set Theory
  3. Relations & Functions
  4. Counting Techniques
  5. Recurrence Relations
  6. Graph Theory
  7. Trees
  8. Proof Techniques
  9. Algebraic Structures