The GATE Grind

GATE Engineering Mathematics: Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices – Previous Year Questions

32 GATE previous year questions on Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices (Engineering Mathematics, Computer Science) with answers and explanations, from every paper.

32 questions worth 46 marks in all (18 1-mark, 14 2-mark). Asked between 2007 and 2026, so you can see how the topic has been tested over time.

  1. GATE 2007 CS Q2 (1 mark, Multiple choice) – S has n elements. How many ordered pairs are in the largest and smallest equivalence relations on S respectively?
  2. GATE 2007 CS Q26 (2 marks, Multiple choice) – Partitions of S=a, b, c, d are π1=a, b, c, d, π2=a, b, c, d, π3=a, b, c, d, π4=a, b, c, d. Define πi≺πj iff πi refines πj. Which shown poset diagram…
  3. GATE 2008 CS Q2 (1 mark, Multiple choice) – P, Q, R are subsets of universal set U. Simplify (P Q R)(Pc Q R) Qc Rc.
  4. GATE 2009 CS Q4 (1 mark, Multiple choice) – Consider the binary relation R = (x, y), (x, z), (z, x), (z, y) on x, y, z. Which one of the following is TRUE?
  5. GATE 2021 CS (CS2) Q21 (1 mark, Multiple select) – For n≥2, S1 contains all n×n matrices over a,b,c, and S2 contains all functions from \0,1,,n2-1\ to 0,1,2. Which are correct?
  6. GATE 2015 CS (CS3) Q12 (1 mark, Multiple choice) – U is the power set of S=1,2,3,4,5,6. T is cardinality, T′ complement in S, and T∖R set difference. Which is true?
  7. GATE 2015 CS (CS3) Q60 (2 marks, Multiple choice) – On ordered pairs of positive integers, ((p,q),(r,s))∈R iff p−s=q−r. Which describes R?
  8. GATE 2015 CS (CS2) Q12 (1 mark, Numerical answer) – Find the cardinality of the power set of 0,1,2,…,10.
  9. GATE 2015 CS (CS2) Q13 (1 mark, Multiple choice) – On positive integers, aRb iff a≠b and a,b have a common divisor greater than one. Which describes R?
  10. GATE 2010 CS Q13 (1 mark, Multiple choice) – How many reflexive relations exist on a five-element set?
  11. GATE 2017 CS (CS2) Q31 (1 mark, Numerical answer) – X=a,b,c,d,e has partial order R=(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),(b,e),(c,c),(c,e),(d,d),(d,e),(e,e), with Hasse diagram shown. How many…
  12. GATE 2016 CS (CS2) Q36 (2 marks, Multiple choice) – On N N, (a,b)R(c,d) iff a ≤ c or b ≤ d. P: R is reflexive. Q: R is transitive. Which is true?
  13. GATE 2014 CS (CS3) Q12 (1 mark, Multiple choice) – Let X,Y be finite sets and f:X Y. Which statement is TRUE?
  14. GATE 2014 CS (CS3) Q59 (2 marks, Multiple choice) – Consider all f:\0,1,,2014\\0,1,,2014\ satisfying f(f(i))=i. P: Every such function fixes every i. Q: Every such function fixes some i. R: Every such…
  15. GATE 2014 CS (CS2) Q60 (2 marks, Multiple choice) – S is the set of integers from 1 to 2014. For distinct subsets U,V, define U < V when the minimum element of their symmetric difference belongs to U.…
  16. GATE 2014 CS (CS1) Q60 (2 marks, Numerical answer) – S is the set of all functions f:\0,1\4\0,1\. If N counts functions from S to 0,1, find 2 2N.
  17. GATE 2016 CS (CS1) Q38 (2 marks, Numerical answer) – A function f : N+ N+, defined on the set of positive integers N+, satisfies the following properties: f(n) = f(n/2) if n is even f(n) = f(n+5) if n is…
  18. GATE 2015 CS (CS1) Q11 (1 mark, Multiple choice) – If g(x) = 1 - x and h(x) = xx-1, then g(h(x))h(g(x)) is:
  19. GATE 2015 CS (CS1) Q20 (1 mark, Multiple choice) – For a set A, the power set of A is denoted by 2A. If A = \5, \6\, \7\\, which of the following options are TRUE? I. 2A II. 2A III. \5, \6\\ 2A IV. \5,…
  20. GATE 2015 CS (CS1) Q42 (2 marks, Multiple choice) – Suppose L = \p, q, r, s, t\ is a lattice represented by the following Hasse diagram: [Hasse diagram: p is the bottom, t is the top, and q, r, s are…
  21. GATE 2018 CS Q37 (2 marks, Multiple choice) – Let N be the set of natural numbers. Consider the following sets. P: Set of Rational numbers (positive and negative) Q: Set of functions from \0,1\ to…
  22. GATE 2019 CS Q31 (1 mark, Numerical answer) – The value of 351 mod 5 is .
  23. GATE 2019 CS Q64 (2 marks, Numerical answer) – In an RSA cryptosystem, the value of the public modulus parameter n is 3007. If it is also known that (n)=2880, where () denotes Euler's Totient…
  24. GATE 2026 CS (CS2) Q26 (1 mark, Multiple select) – Let R be a binary relation on the set \1,2,,10\, where (x,y) R if the product xy is the square of an integer. Which of the following properties is/are…
  25. GATE 2025 CS (CS2) Q42 (2 marks, Multiple select) – Let F be the set of all functions from \1,,n\ to \0,1\. Define the binary relation on F as follows: f, g F,\ f g if and only if x \1,,n\,\ f(x) g(x),…
  26. GATE 2025 CS (CS1) Q17 (1 mark, Multiple choice) – g(.) is a function from A to B, f(.) is a function from B to C, and their composition defined as f(g(.)) is a mapping from A to C. If f(.) and f(g(.))…
  27. GATE 2025 CS (CS1) Q58 (2 marks, Numerical answer) – Consider a probability distribution given by the density function P(x). P(x) = cases Cx2, & for 1 x 4 \\ 0, & for x < 1 or x > 4 cases The probability…
  28. GATE 2024 CS (CS2) Q34 (1 mark, Numerical answer) – Let P be the partial order defined on the set \1,2,3,4\ as follows: P=\(x,x) x\1,2,3,4\\\(1,2),(3,2),(3,4)\. The number of total orders on \1,2,3,4\…
  29. GATE 2024 CS (CS1) Q32 (1 mark, Numerical answer) – Let A and B be non-empty finite sets such that there exist one-to-one and onto functions (i) from A to B and (ii) from A A to A B. The number of…
  30. GATE 2023 CS Q49 (2 marks, Multiple select) – Let f: A B be an onto (or surjective) function, where A and B are nonempty sets. Define an equivalence relation on the set A as a 1 a 2 if f(a 1) =…
  31. GATE 2021 CS (CS1) Q53 (2 marks, Multiple select) – A relation R is said to be circular if aRb and bRc together imply cRa. Which of the following options is/are correct?
  32. GATE 2020 CS Q27 (1 mark, Numerical answer) – Let R be the set of all binary relations on the set \1,2,3\. Suppose a relation is chosen from R at random. The probability that the chosen relation…