11 · GATE PYQs (from the slides)
How to use
Attempt each question before expanding the answer. Target: 1-mark ≤ 1.5 min, 2-mark ≤ 3 min. Log mistakes in the README mistake log.
| # | Year | Marks | Topic | Done |
|---|---|---|---|---|
| 1 | 2004 | 2 | Satisfiable vs valid | [ ] |
| 2 | 2005 | 2 | Tautology among implications | [ ] |
| 3 | 2008 | 2 | Equivalent expressions | [ ] |
| 4 | 2009 | 2 | Custom operator | [ ] |
| 5 | 2012 | 1 | Valid inference | [ ] |
| 6 | 2014 Set 2 | 2 | NOT a tautology | [ ] |
| 7 | 2015 Set 2 | 1 | Inference from two statements | [ ] |
| 8 | 2015 Set 3 | 1 | Truth-teller puzzle | [ ] |
| 9 | 2016 Set 2 | 1 | Logical implication count | [ ] |
Q1 · GATE 2004 (2 marks)
The propositional statement is (a) satisfiable but not valid (b) valid (c) a contradiction (d) none of the above
👁 Show answer
Answer: (a)
Falsify it (assume F): consequent F ⇒ P = Q = T, R = F. Antecedent: = T ✓. So T → F = F — a falsifying row exists ⇒ not valid. Satisfy it: P = F makes both sides T ⇒ T. Sometimes T, sometimes F ⇒ satisfiable but not valid.
Q2 · GATE 2005 (2 marks)
Let X = and Y = . Which is a tautology? (a) X ≡ Y (b) X → Y (c) Y → X (d) ¬Y → X
👁 Show answer
Answer: (b)
Use identity: . Let A = P→R, B = Q→R. X = A ∧ B, Y = A ∨ B. (b) — always true ✅ (c) fails at A = T, B = F ❌ (a) fails for the same reason. (d) ¬Y → X: ¬Y = ¬A∧¬B, X = A∧B; with A = B = F, T → F ❌. 🧠 Pattern: “AND implies OR” is always a tautology.
Q3 · GATE 2008 (2 marks)
Which are equivalent? 1. 2. 3. 4. (a) Only 1 and 2 (b) Only 1, 2 and 3 (c) Only 1, 2 and 4 (d) All
👁 Show answer
Answer: (b)
2: De Morgan ⇒ ✅ 3: ✅ 4: ❌ (that’s P ∨ Q) 🧠 Shortcut: think minterms. is false only at (P=F, Q=T), so it’s the 3 minterms excluding . Expression 4 includes that term ⇒ wrong.
Q4 · GATE 2009 (2 marks)
□ is defined by: (T,T)→T, (T,F)→T, (F,T)→F, (F,F)→T. Which is equivalent to ? (a) ¬Q □ ¬P (b) P □ ¬Q (c) ¬P □ Q (d) ¬P □ ¬Q
👁 Show answer
Answer: (b)
□ is false only at (F, T) ⇒ (= Q → P). (a) ❌ (b) ✅ (c) ❌ (d) ❌ 🧠 Custom-operator questions: find the single F row (or single T row) and write the operator as a known one.
Q5 · GATE 2012 (1 mark)
I1: If it rains, the match won’t be played. The match was played. ⇒ There was no rain. I2: If it rains, the match won’t be played. It did not rain. ⇒ The match was played. (a) both correct (b) I1 correct, I2 not (c) I1 not, I2 correct (d) neither
👁 Show answer
Answer: (b)
I1: — Modus Tollens ✅ I2: — denying the antecedent ❌ (R = F, C = F makes premises T, conclusion F)
Q6 · GATE 2014 Set 2 (2 marks)
Which is NOT a tautology? (a) (b) (c) (d)
👁 Show answer
Answer: (b)
(b) Falsify: a = b = c = F ⇒ = T, and = T → F = F ⇒ T → F = F. (a) hypothetical syllogism ✅ (c) AND ⇒ OR of a subset ✅ (d) = T ✅
Q7 · GATE 2015 Set 2 (1 mark)
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? (a) corrupt ⇒ kind (b) not corrupt ⇒ not kind (c) kind ⇒ not corrupt (d) not kind ⇒ not corrupt
👁 Show answer
Answer: (c)
S1: ≡ (contrapositive) . S2: . Hypothetical syllogism: ⇒ ✅ 🧠 When options are conditionals, chain the premises (use contrapositives to make the links match).
Q8 · GATE 2015 Set 3 (1 mark)
Truth-teller/liar tosses a coin and says “The result is head iff I am telling the truth.” (a) head (b) tail (c) if Type 2, tail (d) if Type 1, tail
👁 Show answer
Answer: (a)
Full solution in 06 Logic Puzzles. “X iff I’m telling the truth” always forces X = T.
Q9 · GATE 2016 Set 2 (1 mark)
How many of: i. False ii. Q iii. True iv. v. are logically implied by ?
👁 Show answer
Answer: 4
. “Logically implied” ⇒ must be a tautology. Only check the row P = Q = T: i. F ❌ ii. Q = T ✅ iii. T ✅ iv. T ✅ v. = T ✅ ⇒ 4 🧠 If the premise simplifies to a single minterm, just evaluate each option at that one row.
Prev ← 10 Beyond the Slides · Next → 12 Practice Problems