The GATE Grind

GATE Engineering Mathematics: Discrete Mathematics: Propositional and First Order Logic – Previous Year Questions

39 GATE previous year questions on Discrete Mathematics: Propositional and First Order Logic (Engineering Mathematics, Computer Science) with answers and explanations, from every paper.

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

  1. GATE 2007 CS Q22 (2 marks, Multiple choice) – Graph(x) means x is a graph; Connected(x) means x is connected. Which does NOT express “Not every graph is connected”?
  2. GATE 2007 CS Q48 (2 marks, Multiple choice) – Which is TRUE of conjunctive-normal-form formulae?
  3. GATE 2008 CS Q30 (2 marks, Multiple choice) – fsa(x) means x is a finite-state automaton; pda(y) means y is a pushdown automaton; equivalent(a, b) means language equivalence. Which formula…
  4. GATE 2008 CS Q31 (2 marks, Multiple choice) – Which expressions are equivalent? I. P ∨ ¬Q II. ¬(¬P ∧ Q) III. (P ∧ Q) ∨ (P ∧ ¬Q) ∨ (¬P ∧ ¬Q) IV. (P ∧ Q) ∨ (P ∧ ¬Q) ∨ (¬P ∧ Q)
  5. GATE 2009 CS Q23 (2 marks, Multiple choice) – Which logical formula most appropriately represents “Gold and silver ornaments are precious”? G(x): x is a gold ornament; S(x): x is a silver…
  6. GATE 2009 CS Q24 (2 marks, Multiple choice) – The binary operation □ has this truth table. Which expression is equivalent to P ∨ Q? P Q P □ Q --- --- --- T T T T F T F T F F F T
  7. GATE 2009 CS Q26 (2 marks, Multiple choice) – Which formulae are equivalent? I. ¬∀x P(x) II. ¬∃x P(x) III. ¬∃x ¬P(x) IV. ∃x ¬P(x)
  8. GATE 2021 CS (CS2) Q25 (1 mark, Multiple select) – For S:((P Q) R)((P Q)(Q R)), choose the correct statements.
  9. GATE 2015 CS (CS3) Q26 (1 mark, Multiple choice) – A room contains truth-tellers and liars. An unknown person tosses a fair coin unseen and says: “The result is head if and only if I am telling the…
  10. GATE 2015 CS (CS2) Q11 (1 mark, Multiple choice) – S1: If a candidate is known to be corrupt, he will not be elected. S2: If a candidate is kind, he will be elected. Which follows logically?
  11. GATE 2015 CS (CS2) Q63 (2 marks, Multiple choice) – Which first-order formula is logically valid?
  12. GATE 2010 CS Q40 (2 marks, Multiple choice) – Let F(x,y,t) mean that x can fool y at time t. What does x\, y\, t\, F(x,y,t) express?
  13. GATE 2011 CS Q40 (2 marks, Multiple choice) – For positive integers x,y,z, define P(x)=(x=1) y[( z(x=yz))((y=x)(y=1))]. Which is correct?
  14. GATE 2013 CS Q37 (2 marks, Multiple choice) – With F(x)=“x is my friend” and P(x)=“x is perfect”, translate “None of my friends are perfect”.
  15. GATE 2013 CS Q57 (2 marks, MTA) – Which formula is NOT equivalent to x( y\, z\,)?
  16. GATE 2012 CS Q11 (1 mark, Multiple choice) – I₁: If it rains, the cricket match will not be played; the match was played; infer no rain. I₂: If it rains, the match will not be played; it did not…
  17. GATE 2012 CS Q23 (1 mark, Multiple choice) – Translate “Some real numbers are rational” into logic.
  18. GATE 2017 CS (CS2) Q21 (1 mark, Multiple choice) – Let p,q,r mean “It is raining”, “It is cold”, “It is pleasant”. Represent: “It is not raining and it is pleasant, and it is not pleasant only if it is…
  19. GATE 2016 CS (CS2) Q11 (1 mark, Numerical answer) – Consider (i) false, (ii) Q, (iii) true, (iv) P Q, (v) Q P. How many are logically implied by P(P Q)?
  20. GATE 2016 CS (CS2) Q37 (2 marks, Multiple choice) – Which predicate-calculus formula is NOT valid?
  21. GATE 2014 CS (CS3) Q11 (1 mark, Multiple choice) – P: Good mobile phones are not cheap. Q: Cheap mobile phones are not good. L: P implies Q. M: Q implies P. N: P is equivalent to Q. Which is correct?
  22. GATE 2014 CS (CS3) Q63 (2 marks, Multiple choice) – Which formula expresses “not all rainy days are cold”?
  23. GATE 2014 CS (CS2) Q63 (2 marks, Multiple choice) – Which Boolean expression is NOT a tautology?
  24. GATE 2014 CS (CS1) Q11 (1 mark, Multiple choice) – “Not all that glitters is gold.” Predicate glitters(x) means x glitters, and gold(x) means x is gold. Which formula represents this statement?
  25. GATE 2014 CS (CS1) Q63 (2 marks, Multiple choice) – Which propositional formula is TRUE exactly when two of p, q, r are TRUE?
  26. GATE 2017 CS (CS1) Q11 (1 mark, Multiple choice) – The statement ( p) ( q) is logically equivalent to which of the statements below? I. p q II. q p III. ( q) p IV. ( p) q
  27. GATE 2017 CS (CS1) Q12 (1 mark, Multiple choice) – Consider the first-order logic sentence F: x( y R(x, y)). Assuming non-empty logical domains, which of the sentences below are implied by F? I. y( x…
  28. GATE 2017 CS (CS1) Q39 (2 marks, Multiple choice) – Let p, q, and r be propositions and the expression (p q) r be a contradiction. Then, the expression (r p) q is
  29. GATE 2016 CS (CS1) Q11 (1 mark, Numerical answer) – Let p, q, r, s represent the following propositions. p: x \8, 9, 10, 11, 12\ q: x is a composite number r: x is a perfect square s: x is a prime…
  30. GATE 2015 CS (CS1) Q19 (1 mark, Multiple choice) – Which one of the following is NOT equivalent to p q?
  31. GATE 2018 CS Q38 (2 marks, Multiple choice) – Consider the first-order logic sentence s\, t\, u\, v\, w\, x\, y\ (s,t,u,v,w,x,y) where (s,t,u,v,w,x,y) is a quantifier-free first-order logic…
  32. GATE 2019 CS Q45 (2 marks, Multiple choice) – Consider the first order predicate formula : x[( z\ z x((z=x)(z=1))) w\,(w>x)( z\ z w((w=z)(z=1)))] Here 'a b' denotes that 'a divides b', where a and…
  33. GATE 2026 CS (CS2) Q11 (1 mark, Multiple choice) – For two different persons x and y, the predicate M(x,y) denotes that x knows y. Consider the following statement: There is a person who does not know…
  34. GATE 2025 CS (CS2) Q15 (1 mark, Multiple choice) – Let P(x) be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?
  35. GATE 2025 CS (CS1) Q48 (2 marks, Multiple select) – Which of the following predicate logic formulae/formula is/are CORRECT representation(s) of the statement: "Everyone has exactly one mother"? The…
  36. GATE 2024 CS (CS2) Q12 (1 mark, Multiple choice) – Let p and q be the following propositions: p: Fail grade can be given. q: Student scores more than 50% marks. Consider the statement: "Fail grade…
  37. GATE 2023 CS Q26 (1 mark, Multiple select) – Geetha has a conjecture about integers, which is of the form x\,[P(x) y\, Q(x,y)], where P is a statement about integers, and Q is a statement about…
  38. GATE 2021 CS (CS1) Q17 (1 mark, Multiple choice) – Let p and q be two propositions. Consider the following two formulae in propositional logic. S 1: ( p (p q)) q S 2: q ( p (p q)) Which one of the…
  39. GATE 2020 CS Q49 (2 marks, Multiple choice) – Which one of the following predicate formulae is NOT logically valid? Note that W is a predicate formula without any free occurrence of x.