Discrete Mathematics for GATE CSE 2027: What to Study and How to Practise

Confused between one‑one and onto functions? Do you find quantifiers or graph coloring tricky? Discrete Mathematics can feel hard. It becomes much clearer when you link every definition to a tiny example.

This guide will split the subject into topics, hand‑out formulas and the kinds of questions you should be able to answer.

1. Propositional Logic: Is the Statement Always True?

Propositional logic is about statements that can be either true or false.

What to learn:

• Operators: AND OR, NOT implication and biconditional.
• Propositional logic truth tables.
• Logical. Equivalence.
• Tautology, contradiction and contingency.
• Conjunctive normal form (CNF). Disjunctive normal form (DNF).
• Rules of inference and validity of arguments.
• Concept: An implication pq is false only when p is true and q is false.

Example: "If a number is divisible by 4 it is even." A counterexample would be a number, by 4 but not even.

Practice: Construct truth tables, identify expressions and determine whether an argument is valid.

Propositional logic is about statements that can be either true or false.

2. Set Theory: Count Without Double-Counting

Set theory for GATE covers collections of objects and relationships between them.

What to learn:

• Union, intersection, difference and complement.
• Subsets and power sets.
• Cartesian product of sets.
• Venn diagram problems.

Inclusion–exclusion for overlapping sets.

Example: If 25 students study C, 20 study Python and 10 study both, then 25+20-10=35 students study at least one language.

3. Relations and Functions: Know the Difference

These concepts look similar, but questions test very specific properties

Here is the input from the user:

• Two combinations to remember:
• Equivalence relation: Reflexive plus symmetric plus transitive.
• Partial order relation: Reflexive plus antisymmetric plus transitive.

Also practise composition of relations, matrix representation, closure of relations and transitive closure using the Warshall algorithm.

One One and Onto Functions

• Injective or one one: Different inputs produce outputs.
• Onto: Every element of the codomain has a preimage.
• Bijective: Both one one and onto.
• Inverse function: A function has an inverse on its codomain when it is bijective.

Common mistake: Checking whether a function is onto, without checking its codomain.

4. Posets and Hasse Diagrams: Find the Right Element

An ordered set or poset is a collection of items together with a relation that tells us when one item comes before another. A Hasse diagram is a picture that shows a finite poset in a way. I find that looking at the diagram helps a lot.

Questions to practice:

• Which elements can be compared with each other?
• Which elements are maximal and which are minimal?
• Does there exist an element or a least element?
• What are the upper bounds and lower bounds for the elements?
• Does every pair of elements have both an upper bound and a greatest lower bound?

Important distinction: A maximal element is one that has no element strictly above it. A greatest element on the hand is one that is greater than or equal to every element in the poset.

A lattice is a poset where every pair of elements has one least upper bound and one unique greatest lower bound. After you feel comfortable, with this you can move on to learning about bounded, complemented lattices

5. Groups and Monoids: Check the Properties

For algebraic structures, use a checklist instead of memorising examples.

In each case, the operation must be closed on the set.

Example: Integers under addition form a group. Non-negative integers under addition form a monoid, but not a group, because positive integers do not have additive inverses within that set.

Also cover subgroups and cyclic groups.

6. Graph Theory for GATE CSE: Edges or Vertices?

Start by identifying what the question asks you to visit, remove, connect or color

Quick results to revise:

• Sum of vertex degrees in an undirected graph: 2|E|.
• Number of odd-degree vertices: Always even.
• Edges in a tree with n vertices: n-1.
• Edges in a simple complete graph: n(n-1)/2.
• A graph is bipartite if and only if it contains no odd cycle.

Also practise planar graphs, graph coloring, maximum matching in bipartite graphs and connectivity questions.

7. Combinatorics: Does Order Matter?

Before selecting a formula, ask:

1. Does order matter?
2. Is repetition allowed?
3. Are the objects distinct?
4. Are there restrictions?

Useful formulas:

Other themes to explore:

• Basic counting principle.
• Permutations and combinations with recurrence.
• Pigeonhole and general pigeonhole law.
• Inclusion/exclusion law.
• Binomial theorem.
• Stars and bars.

For example, if three students are to be selected for a series of tasks, counting would be seen as combinations. On the other hand, if students are assigned different roles in a team, then counting would be considered as permutations.

8. Recurrence Relations: Build the Sequence

A recurrence relation defines a term using earlier terms.

Example:

an=an-1+2,a0=1

This sequence produces the numbers 1, 3 5 7 and so on giving the form a_n = 2n + 1.

What to practise:

• Form a recurrence from a word problem.
• Solve linear recurrence relations.
• Apply conditions.
• Handle repeated characteristic roots.
• Use generating functions.

A common mistake is finding a solution and then forgetting to apply the initial conditions.

How to Use Discrete Mathematics GATE PYQ With Solutions

• Attempt each previous year question first without reading the solution.
• Identify the concept being tested.
• Compare your reasoning with the worked solution.
• Record the error: concept, calculation or interpretation.
• Reattempt incorrect questions after a gap.

For Discrete Mathematics GATE practice questions mix direct concept checks with problems that combine ideas.

What needs to be in GATE Notes on Discrete Mathematics?

• Logic: equivalence, negation of quantifiers, and rules of inference.
• Relations: definitions of properties and examples that contradict them.
• Functions: conditions for functions to be one-to-one, onto, and bijective.
• Posets: boundaries and differences between lowest and highest.
• Graphs: important results and their conditions.
• Falling: formulas and one example of when to use each one.
• Recurrence: solving methods and initial conditions.

The useful GATE formula sheet on Discrete Mathematics conveys when the formula needs to be applied. It is no less important than the memory of the formula itself.