Set theory and relations are the grammar of discrete mathematics: almost every later topic, from functions and lattices to graph theory, is written in this language. GATE rewards a clean grasp of set identities, the reflexive-symmetric-transitive tests, closures, equivalence classes, and partial orders, and it punishes vague memorisation with distractor-heavy options. Below are 12 solved MCQs from KnowledgeGate's published question bank, every one a previous-year GATE problem with the year marked. Attempt each before reading the explanation, which stays short on purpose. Every question here links its exact solved page; if a definition feels shaky, the full theory sits in the Discrete Mathematics learn module.
Set operations and identities
Q1. In a class of 200 students, 125 took Programming, 85 took Data Structures, 65 took Computer Organization, 50 took Programming and Data Structures, 35 took Data Structures and Computer Organization, 30 took Programming and Computer Organization, and 15 took all three. How many took none of the three? (GATE 2004)
(a) 15
(b) 20
(c) 25
(d) 35
Answer: (c) 25. Inclusion-exclusion gives the union as 125 + 85 + 65 minus 50 + 35 + 30 plus 15, which is 275 - 115 + 15 = 175. The students taking none are 200 - 175 = 25. Add the singles, subtract the pairs, add back the triple: getting the alternating signs right is the whole exam here (see the solved page).
Q2. For sets A and B, the set (A - B) union (B - A) union (A intersection B) equals (GATE 1996)
(a) A union B
(b) A complement union B complement
(c) A intersection B
(d) A complement intersection B complement
Answer: (a) A union B. The three pieces are the only-in-A part, the only-in-B part, and the shared part. They are disjoint and together cover exactly everything in A or in B, so their union is A union B. A quick Venn sketch settles this class of identity in seconds (see the solved page).
Q3. If P, Q, R are subsets of the universal set U, the value of (P intersection Q intersection R) union (P complement intersection Q intersection R) union Q complement union R complement is (GATE 2008)
(a) Q complement union R complement
(b) P union Q complement union R complement
(c) P complement union Q complement union R complement
(d) U
Answer: (d) U. Merge the first two terms: (P union P complement) intersection Q intersection R is just Q intersection R. What remains is (Q intersection R) union (Q intersection R) complement, because by DeMorgan Q complement union R complement is the complement of Q intersection R. A set unioned with its own complement is the universe U (see the solved page).
Relations: definitions and properties
Q4. For a set A of n elements, how many binary relations can be defined on A? (GATE 1999)
(a) n squared
(b) 2 to the power n
(c) 2 to the power n squared
(d) None of the above
Answer: (c) 2 to the power n squared. A binary relation on A is any subset of A cross A, and A cross A has n times n = n squared ordered pairs. The number of subsets of a set with n squared elements is 2 to the power n squared. Every counting question about relations starts from this A cross A base (see the solved page).
Q5. For the relation R = {(x, y), (x, z), (z, x), (z, y)} on the set {x, y, z}, which is TRUE? (GATE 2009)
(a) R is symmetric but not antisymmetric
(b) R is not symmetric but antisymmetric
(c) R is both symmetric and antisymmetric
(d) R is neither symmetric nor antisymmetric
Answer: (d) neither. Symmetry fails because (x, y) is present but (y, x) is not. Antisymmetry also fails because both (x, z) and (z, x) are present with x not equal to z, which is exactly the pattern antisymmetry forbids. A relation can lack both properties at once, and mixing up "not symmetric" with "antisymmetric" is the classic slip (see the solved page).
Q6. The empty relation S = the empty set on the set A = {1, 2, 3} is (GATE 2002)
(a) neither reflexive nor symmetric
(b) symmetric and reflexive
(c) transitive and reflexive
(d) transitive and symmetric
Answer: (d) transitive and symmetric. The empty relation has no pairs, so symmetry and transitivity hold vacuously, there is no counterexample to break them. But reflexivity fails, because it demands (1,1), (2,2) and (3,3), none of which are present. Vacuous truth is a favourite discrete-maths trap (see the solved page).
Closures and equivalence relations
Q7. For S = {(x, y) : y = x + 1 and x, y in {0, 1, 2, ...}}, the reflexive transitive closure of S is (GATE 2004)
(a) {(x, y) : y greater than x}
(b) {(x, y) : y greater than or equal to x}
(c) {(x, y) : y less than x}
(d) {(x, y) : y less than or equal to x}
Answer: (b) {(x, y) : y greater than or equal to x}. S holds only the successor pairs (x, x+1). Transitivity chains these into (x, x+n) for every positive n, giving all pairs with y greater than x. Adding reflexivity supplies the case n = 0, so the closure is every pair with y greater than or equal to x. Closure means adding the minimum pairs to gain the named property (see the solved page).
Q8. A relation R on the integers is defined by x R y if x + y is even. Which is true? (GATE 2000)
(a) R is not an equivalence relation
(b) R is an equivalence relation with 1 equivalence class
(c) R is an equivalence relation with 2 equivalence classes
(d) R is an equivalence relation with 3 equivalence classes
Answer: (c) an equivalence relation with 2 classes. A sum is even exactly when both numbers share parity, so R is reflexive, symmetric and transitive, an equivalence relation. It partitions the integers into two classes, the evens and the odds. Every equivalence relation corresponds to a partition, and here parity is the partition (see the solved page).
Q9. The number of equivalence relations on the set {1, 2, 3, 4} is (GATE 1997)
(a) 15
(b) 16
(c) 24
(d) 4
Answer: (a) 15. Equivalence relations on a set are in one-to-one correspondence with its partitions, so the count is the Bell number. For a 4-element set the Bell number is 15. Do not count orderings or subsets; count the ways to partition (see the solved page).
Q10. For a set S of n elements, the numbers of ordered pairs in the largest and the smallest equivalence relations on S are (GATE 2007)
(a) n and n
(b) n squared and n
(c) n squared and 0
(d) n and 1
Answer: (b) n squared and n. The largest equivalence relation is the universal relation S cross S, with n squared pairs, corresponding to the single-block partition. The smallest is the identity relation, one pair (a, a) per element, so n pairs, corresponding to all singletons. Reflexivity forbids the empty relation, which rules out option (c) (see the solved page).
Partial orders and Hasse diagrams
Q11. For X = {2, 3, 6, 12, 24} with the partial order x less than or equal to y when x divides y, the number of edges in the Hasse diagram is (GATE 1996)
(a) 3
(b) 4
(c) 9
(d) None of the above
Answer: (b) 4. A Hasse diagram draws only cover relations, dropping edges implied by transitivity. The covers here are 2 divides 6, 3 divides 6, 6 divides 12, and 12 divides 24, four edges in all. Pairs like 2 divides 12 are omitted because 6 sits between them. Reduce to covers before counting, never draw the full order (see the solved page).
Q12. A partial order P on the natural numbers is defined by (0, 0) in P, and (a, b) in P if and only if a mod 10 is at most b mod 10 and (a div 10, b div 10) in P. Which pairs lie in P: (i) (101, 22), (ii) (22, 101), (iii) (145, 265), (iv) (0, 153)? (GATE 2007)
(a) (i) and (iii)
(b) (ii) and (iv)
(c) (i) and (iv)
(d) (iii) and (iv)
Answer: (d) (iii) and (iv). The rule compares numbers digit by digit from the units up, requiring each digit of the first to be at most the matching digit of the second. For (145, 265): 5 at most 5, 4 at most 6, 1 at most 2, all hold. For (0, 153): 0 is at most every digit. Pair (i) fails at the hundreds digit and (ii) fails at the units, so only (iii) and (iv) qualify (see the solved page).
How this set is examined
The 12 questions above walk the whole spine of the topic: set operations and identities solved by inclusion-exclusion or a Venn sketch (Q1 to Q3), the property tests and counting of relations (Q4 to Q6), closures and equivalence relations tied back to partitions (Q7 to Q10), and partial orders read off Hasse diagrams (Q11 to Q12). The recurring theme is that an equivalence relation is a partition and a partial order is a divisibility-style hierarchy, so translating a relation into that picture usually cracks the question. The set algebra in Q1 to Q3 is the same structure you meet as a Boolean algebra, so the Boolean algebra and K-map MCQs drill the identical laws on logic variables. The full worked theory behind this set sits in our Set theory and relations explained deep dive, which rebuilds every definition from the ground up.
Work each question a second time a week later, and confirm your reasoning against the Discrete Mathematics learn module. GATE aspirants get the full discrete maths sequence inside GATE Guidance by Sanchit Sir, and you can place the subject in the wider syllabus on the GATE CS Exam page. Solve, review the ones you missed, and the marks get locked in on the second pass.
