Logic is the part of Discrete Mathematics that GATE and UGC NET keep returning to, because it tests reasoning rather than memory. The same core ideas recur every year: translating an English sentence into connectives, checking whether two formulas are equivalent, negating a quantified statement correctly, and deciding when a first-order formula is valid. Below are 12 solved MCQs pulled from KnowledgeGate's published question bank, every one a previous-year GATE or NET question with the exam and year marked. Attempt each before reading the answer; the explanation after it is deliberately short, just enough to lock the reasoning in. Each question links to its exact solved page inside the Discrete Mathematics learn module, so you can see the full working and practise the neighbours.
Logical connectives and truth values
Q1. Let p and q be propositions, p: "Fail grade can be given" and q: "Student scores more than 50% marks". Which represents "Fail grade cannot be given when a student scores more than 50% marks"? (GATE 2024, see the solved page)
(a) q → ¬p
(b) q → p
(c) p → q
(d) ¬p → q
Answer: (a) q → ¬p.
The word "when" sets up the condition: whenever q holds (score above 50%), a fail cannot be given, which is ¬p. That is exactly the implication q → ¬p. The contrapositive p → ¬q says the same thing, but the direct translation of the sentence is q → ¬p.
Q2. If the proposition ¬p → q is true, then the truth value of ¬p ∨ (p → q) is (UGC NET 2005, see the solved page)
(a) True
(b) Multiple values
(c) False
(d) Cannot be determined
Answer: (d) Cannot be determined.
The premise ¬p → q is equivalent to p ∨ q, so at least one of p, q is true, but this leaves several cases open. Take p true and q false: the target becomes False ∨ (True → False) = False. Take p true and q true: it becomes False ∨ (True → True) = True. Since the same premise yields both outcomes, the value is not determined.
Q3. Which one of the following is NOT equivalent to p ↔ q? (GATE 2015, see the solved page)
(a) (¬p ∨ q) ∧ (p ∨ ¬q)
(b) (¬p ∨ q) ∧ (q → p)
(c) (¬p ∧ q) ∨ (p ∧ ¬q)
(d) (¬p ∧ ¬q) ∨ (p ∧ q)
Answer: (c).
The biconditional p ↔ q is true exactly when p and q share a truth value, so its two standard forms are (¬p ∨ q) ∧ (¬q ∨ p) and (p ∧ q) ∨ (¬p ∧ ¬q). Option (c), (¬p ∧ q) ∨ (p ∧ ¬q), is true when p and q differ, which is exactly the exclusive-or. That is the negation of the biconditional, so it is the odd one out.
Q4. With P: "Good mobile phones are not cheap" and Q: "Cheap mobile phones are not good", let L: P implies Q, M: Q implies P, N: P is equivalent to Q. Which is CORRECT? (GATE 2014, see the solved page)
(a) Only L is true
(b) Only M is true
(c) Only N is true
(d) L, M and N are all true
Answer: (d).
Write P as G → ¬C ("good implies not cheap") and Q as C → ¬G ("cheap implies not good"). The contrapositive of G → ¬C is C → ¬G, which is precisely Q. A statement and its contrapositive are logically equivalent, so P and Q are equivalent, and equivalence gives both implications for free. Hence L, M and N all hold.
Q5. What is the converse of the assertion "I stay only if you go"? (GATE 1998, see the solved page)
(a) I stay if you go
(b) If I stay then you go
(c) If you do not go then I do not stay
(d) If I do not stay then you go
Answer: (a) I stay if you go.
"P only if Q" means P → Q, so the assertion is "if I stay then you go". The converse swaps hypothesis and conclusion to give "if you go then I stay", which reads naturally as "I stay if you go". Option (b) just restates the original, and option (c) is the contrapositive.
Q6. "If X, then Y unless Z" is represented in propositional logic by (GATE 2002, see the solved page)
(a) (X ∧ ¬Z) → Y
(b) (X ∧ Y) → ¬Z
(c) X → (Y ∧ ¬Z)
(d) (X → Y) ∧ ¬Z
Answer: (a) (X ∧ ¬Z) → Y.
"Y unless Z" means Y is required precisely when Z is false. So the whole sentence fires when X holds and Z is absent, forcing Y. That antecedent is X ∧ ¬Z and the consequent is Y, giving (X ∧ ¬Z) → Y.
Quantifiers and translating statements
Q7. The correct translation of "Some real numbers are rational" is (GATE 2012, see the solved page)
(a) ∃x (real(x) ∨ rational(x))
(b) ∀x (real(x) → rational(x))
(c) ∃x (real(x) ∧ rational(x))
(d) ∃x (rational(x) → real(x))
Answer: (c) ∃x (real(x) ∧ rational(x)).
"Some" is the existential quantifier, and the same object must carry both properties, so you need a conjunction inside ∃x. Option (a) allows an x that is real or rational but not both, and option (b) is a universal "all" claim, which is far stronger than what was asked.
Q8. The logical translation of "None of my friends are perfect" is (GATE 2013, see the solved page)
(a) ∃x (F(x) ∧ ¬P(x))
(b) ∃x (¬F(x) ∧ P(x))
(c) ∃x (¬F(x) ∧ ¬P(x))
(d) ¬∃x (F(x) ∧ P(x))
Answer: (d) ¬∃x (F(x) ∧ P(x)).
"None" asserts that no x is both a friend and perfect, which is directly ¬∃x (F(x) ∧ P(x)). Pushing the negation inward gives the equivalent universal form ∀x (F(x) → ¬P(x)), a useful check that the two ways of saying "none" agree.
Q9. The first-order statement equivalent to "Every teacher is liked by some student" is (GATE 2005, see the solved page)
(a) ∀x [teacher(x) → ∃y [student(y) → likes(y, x)]]
(b) ∀x [teacher(x) → ∃y [student(y) ∧ likes(y, x)]]
(c) ∃y ∀x [teacher(x) → [student(y) ∧ likes(y, x)]]
(d) ∀x [teacher(x) ∧ ∃y [student(y) → likes(y, x)]]
Answer: (b).
Under a universal, restrict with an implication (teacher(x) → ...); under an existential, restrict with a conjunction (student(y) ∧ likes(y, x)). Using an implication inside ∃y would be satisfied by any non-student, and swapping the quantifiers to ∃y ∀x changes the meaning to one student who likes every teacher.
Q10. The correct translation of "Some boys in the class are taller than all the girls", with taller(x, y) true if x is taller than y, is (GATE 2004, see the solved page)
(a) ∃x (boy(x) → ∀y (girl(y) ∧ taller(x, y)))
(b) ∃x (boy(x) ∧ ∀y (girl(y) ∧ taller(x, y)))
(c) ∃x (boy(x) → ∀y (girl(y) → taller(x, y)))
(d) ∃x (boy(x) ∧ ∀y (girl(y) → taller(x, y)))
Answer: (d).
The outer conjunction ∃x (boy(x) ∧ ...) guarantees an actual boy, while the inner implication girl(y) → taller(x, y) says "for every y, if y is a girl then x is taller". Replacing the inner implication with a conjunction would wrongly claim every object is a girl, and using an outer implication would let a non-boy satisfy the statement vacuously.
Predicate-logic validity and inference
Q11. For arbitrary predicates P(x) and Q(x), which statement is always TRUE? (GATE 2005, see the solved page)
(a) (∀x (P(x) ∨ Q(x))) ⇒ ((∀x P(x)) ∨ (∀x Q(x)))
(b) (∀x (P(x) ⇒ Q(x))) ⇒ ((∀x P(x)) ⇒ (∀x Q(x)))
(c) (∀x P(x) ⇒ ∀x Q(x)) ⇒ (∀x (P(x) ⇒ Q(x)))
(d) (∀x P(x) ⇔ ∀x Q(x)) ⇒ (∀x (P(x) ⇔ Q(x)))
Answer: (b).
If every x satisfies P(x) ⇒ Q(x), and every x satisfies P(x), then modus ponens on an arbitrary element gives Q for that element, hence ∀x Q(x). Option (a) fails on a two-element domain where P holds only at one point and Q only at the other, so ∀x (P ∨ Q) is true while neither universal alone is.
Q12. Which one of these first-order logic formulas is valid? (GATE 2007, see the solved page)
(a) ∀x (P(x) ⇒ Q(x)) ⇒ (∀x P(x) ⇒ ∀x Q(x))
(b) ∃x (P(x) ∨ Q(x)) ⇒ (∃x P(x) ⇒ ∃x Q(x))
(c) ∃x (P(x) ∧ Q(x)) ⇔ (∃x P(x) ∧ ∃x Q(x))
(d) ∀x ∃y P(x, y) ⇒ ∃y ∀x P(x, y)
Answer: (a).
This is the same principle as Q11: universal modus ponens distributes over ∀. Option (d) is the classic quantifier-swap trap, since ∀x ∃y does not imply ∃y ∀x (every person has a mother does not mean one person is everyone's mother), and option (c) fails because two properties can each be witnessed separately without a single object having both.
Where these 12 fit in your preparation
The set mirrors how logic is actually examined: connectives and truth-value reasoning (Q1-Q6), translating English into quantifiers (Q7-Q10), and deciding first-order validity (Q11-Q12). If you missed more than two, the gap is usually the restriction rule, an implication under ∀ and a conjunction under ∃, or the quantifier-swap trap in Q12.
Work through the theory behind each answer in the Discrete Mathematics learn module, then keep going with the Graph Theory MCQs, the other high-yield Discrete Mathematics topic. GATE aspirants get the full sequence inside GATE Guidance by Sanchit Sir, and you can see where logic sits in the wider syllabus on the GATE CS category page. Solve, review the ones you missed, and return to this set a week later; the second pass is where the marks get locked in.
