High yield ●●●

🧠 Propositional & First-Order Logic

Why it matters: Almost every paper has a logic question: is a formula valid, which statement is equivalent, which quantifier translation is right, or how many Boolean functions exist.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 6 done.

Formulas

Rows in a truth table
2ⁿ for n variables
Boolean functions of n variables
2^(2ⁿ): 4 for n=1, 16 for n=2, 256 for n=3
Implication
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
De Morgan
¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q
Negating quantifiers
¬∀x P(x) ≡ ∃x ¬P(x); ¬∃x P(x) ≡ ∀x ¬P(x)
Quantifier directions
∃y∀x P ⇒ ∀x∃y P (not conversely); ∀x(P∧Q) ≡ ∀xP ∧ ∀xQ; ∃x(P∨Q) ≡ ∃xP ∨ ∃xQ
Number of minterms of a formula
count of true rows; CNF has one clause per false row
Functionally complete sets
{¬,∧}, {¬,∨}, {¬,→}, {NAND}, {NOR}

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Which statement is equivalent / logically implies another?
Reduce both sides with De Morgan and p → q ≡ ¬p ∨ q, or test with a 2 or 3 variable truth table.
★★★
Translate English to first-order logic
"All A are B" uses →, "some A is B" uses ∧. Check each option against a tiny model.
★★★
Is the formula valid / satisfiable?
Try to make it false; if impossible it is valid. Count true rows.
★★★
Count Boolean functions / functional completeness
2^(2ⁿ) functions; NAND and NOR alone are complete.
★★★
Inference: what follows from the premises
Apply the rules in order; reject affirming the consequent.

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

25 real questions from the official GATE CSE papers (2012 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

25 questions · 0 correct of 0 attempted · marks 0 / 35

Year:
GATE 2025 CS2 · Q15MCQ1 mark
Let P(x) be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?
GATE 2025 CS1 · Q48MSQ2 marks
Which of the following predicate logic formulae/formula is/are CORRECT representation(s) of the statement: "Everyone has exactly one mother"? The meanings of the predicates used are: mother(y, x): y is the mother of x; noteq(x, y): x and y are not equal.

One or more options may be correct. Select all that apply, then submit.

GATE 2024 CS2 · Q12MCQ1 mark
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 cannot be given when student scores more than 50% marks." Which one of the following is the CORRECT representation of the above statement in propositional logic?
GATE 2023 · Q26MSQ1 mark
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 pairs of integers. Which of the following (one or more) option(s) would imply Geetha's conjecture?

One or more options may be correct. Select all that apply, then submit.

GATE 2021 Set 1 · Q7MCQ1 mark
Let p and q be two propositions. Consider the following two formulae in propositional logic. S₁: (¬p ∧ (p ∨ q)) → q S₂: q → (¬p ∧ (p ∨ q)). Which one of the following choices is correct?
GATE 2021 Set 2 · Q15MSQ1 mark
Choose the correct choice(s) regarding the following propositional logic assertion S: S : ((P ∧ Q) → R) → ((P ∧ Q) → (Q → R))

One or more options may be correct. Select all that apply, then submit.

GATE 2020 · Q39MCQ2 marks
Which one of the following predicate formulae is NOT logically valid? Note that W is a predicate formula without any free occurrence of x.
GATE 2019 Set 2 · Q35MCQ2 marks
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 b are integers. Consider the following sets: S1. {1, 2, 3, …, 100}; S2. Set of all positive integers; S3. Set of all integers. Which of the above sets satisfy φ?
GATE 2018 · Q28MCQ2 marks
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 formula using only predicate symbols, and possibly equality, but no function symbols. Suppose φ has a model with a universe containing 7 elements. Which one of the following statements is necessarily true?
GATE 2017 Set 1 · Q1MCQ1 mark
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
GATE 2017 Set 1 · Q2MCQ1 mark
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 R(x, y)) II. ∃y (∀x R(x, y)) III. ∀y (∃x R(x, y)) IV. ¬∃x (∀y ¬R(x, y))
GATE 2017 Set 2 · Q11MCQ1 mark
Let p, q, r denote the statements "It is raining", "It is cold", and "It is pleasant", respectively. Then the statement "It is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold" is represented by
GATE 2017 Set 1 · Q29MCQ2 marks
Let p, q, and r be propositions and the expression (p → q) → r be a contradiction. Then, the expression (r → p) → q is
GATE 2016 Set 1 · Q1NAT1 mark
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 number. The integer x ≥ 2 which satisfies ¬((p ⇒ q) ∧ (¬r ∨ ¬s)) is ______.
GATE 2016 Set 2 · Q1NAT1 mark
Consider the following expressions: (i) false (ii) Q (iii) true (iv) P ∨ Q (v) ¬Q ∨ P. The number of expressions given above that are logically implied by P ∧ (P ⇒ Q) is ______.
GATE 2016 Set 2 · Q27MCQ2 marks
Which one of the following well-formed formulae in predicate calculus is NOT valid?
GATE 2014 Set 1 · Q1MCQ1 mark
Consider the statement "Not all that glitters is gold". Predicate glitters(x) is true if x glitters and predicate gold(x) is true if x is gold. Which one of the following logical formulae represents the above statement?
GATE 2014 Set 3 · Q1MCQ1 mark
Consider the following statements: 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 one of the following about L, M, and N is CORRECT?
GATE 2014 Set 2 · Q6MCQ1 mark
The dual of a Boolean function F(x₁, x₂, …, xₙ, +, ·, '), written as Fᴰ, is the same expression as that of F with + and · swapped. F is said to be self-dual if F = Fᴰ. The number of self-dual functions with n Boolean variables is
GATE 2014 Set 1 · Q53MCQ2 marks
Which one of the following propositional logic formulas is TRUE when exactly two of p, q, and r are TRUE?
GATE 2014 Set 3 · Q53MCQ2 marks
The CORRECT formula for the sentence, "not all rainy days are cold" is
GATE 2014 Set 2 · Q53MCQ2 marks
Which one of the following Boolean expressions is NOT a tautology?
GATE 2013 Code A · Q27MCQ2 marks
What is the logical translation of the following statement? "None of my friends are perfect."
GATE 2012 Code A · Q1MCQ1 mark
Consider the following logical inferences. I₁: If it rains then the cricket match will not be played. The cricket match was played. Inference: There was no rain. I₂: If it rains then the cricket match will not be played. It did not rain. Inference: The cricket match was played. Which of the following is TRUE?
GATE 2012 Code A · Q13MCQ1 mark
What is the correct translation of the following statement into mathematical logic? "Some real numbers are rational"

Common traps

p → q is true when p is false. "If 2 + 2 = 5 then …" is always true.
The converse is not equivalent; only the contrapositive is.
"Some A is B" is ∃x (A ∧ B), not ∃x (A → B), which is true as soon as one A is false.
"All A are B" is ∀x (A → B), not ∀x (A ∧ B), which says everything is both.
Swapping ∀ and ∃ changes the meaning: "everyone has a friend" is not "someone is everyone's friend".