12 · Practice Problems
How to use
30 problems in three levels. Answers are collapsed — click to reveal only after you commit to an answer. Score yourself: Easy 1 pt · Medium 2 pts · Hard 3 pts → total 60. Aim for ≥ 48 before moving on. MSQ = multiple correct options (GATE style), NAT = numeric answer.
🟢 Level 1 — Easy (concept checks)
E1. Is “This sentence is false.” a proposition?
👁 Show answer
No. If it’s true it’s false, and vice versa — no consistent truth value. → 01 Propositions
E2. Find the truth value of .
👁 Show answer
= F
E3. How many rows does the truth table of a formula with 5 distinct variables have?
👁 Show answer
32
E4. Evaluate for p = T, q = F, r = T.
👁 Show answer
Precedence: = F. (Trap: reading it as also gives F here — but in general the parse matters.) → 04 Precedence and Truth Tables
E5. Negate: “I study and I don’t sleep.”
👁 Show answer
→ “I don’t study or I sleep.”
E6. Translate with an arrow: “I’ll go to the beach unless it rains.” (b = beach, r = rains)
👁 Show answer
unless = OR: ≡
E7. Write the contrapositive of .
👁 Show answer
=
E8. Translate: “You can access the Internet from campus only if you are a CS major or you are not a freshman.” (a, c, f)
👁 Show answer
“X only if Y” = X → Y:
E9. Is a tautology?
👁 Show answer
Yes. .
E10. Write “neither p nor q” in two equivalent forms.
👁 Show answer
(De Morgan)
🟡 Level 2 — Medium (GATE 1-mark style)
M1. (MSQ) Which are equivalent to ? (A) (B) (C) (D)
👁 Show answer
Answer: A, B, D
(C) — the opposite. Negating one side flips ↔; negating both doesn’t.
M2. Is ? Justify.
👁 Show answer
No. p = F, r = F (any q): left = = F, right = = T. → is not associative.
M3. Simplify .
👁 Show answer
Same antecedent ⇒ =
M4. Simplify .
👁 Show answer
⇒ negation =
M5. (NAT) How many of the 8 assignments to p, q, r satisfy ?
👁 Show answer
Answer: 4
p = T ⇒ need r = T, q free → 2. p = F ⇒ need q = T, r free → 2. Total 4.
M6. (NAT) How many distinct Boolean functions of 3 variables exist?
👁 Show answer
Answer: 256
M7. Premises: , , . What can you conclude about p?
👁 Show answer
HS: ; MT with : (also ).
M8. Name the error: “If it’s a dog, it has four legs. It has four legs. ∴ It’s a dog.”
👁 Show answer
Affirming the consequent () — invalid.
M9. (NAT) How many of these are tautologies? i. ii. iii. iv. v.
👁 Show answer
Answer: 3
i ✅ (simplification) · ii ❌ (p=T, q=F) · iii ✅ () · iv ❌ (p=F, q=T) · v ✅ (modus tollens) ⚠️ iii surprises people: for any p, q, one of the two implications is always true.
M10. Which sentence is equivalent to “It is not the case that if it rains, I carry an umbrella”?
👁 Show answer
→ “It rains and I don’t carry an umbrella.” (Not “If it doesn’t rain I don’t carry an umbrella” — the negation of → is never an →.)
🔴 Level 3 — Hard (GATE 2-mark style)
H1. Are these specifications consistent? (1) If the file system is not locked, new messages will be queued. (2) The file system is not locked iff the system is functioning normally. (3) If new messages are not queued, they will be sent to the buffer. (4) If the file system is not locked, new messages will be sent to the buffer. (5) New messages will not be sent to the buffer.
👁 Show answer
Answer: Consistent
L = locked, Q = queued, N = normal, B = buffer. (1) (2) (3) (4) (5) (5) B = F → (4) L = T → (2) N = F → (3) Q = T → (1) F → T ✓. Consistent with L = T, Q = T, N = F, B = F. → 05 Translation and Consistency
H2. (NAT) How many assignments satisfy ?
👁 Show answer
Answer: 2
The chain p → q → r → p forces p ≡ q ≡ r. Only TTT and FFF ⇒ 2.
H3. Which is NOT valid? (A) (B) (C) (D)
👁 Show answer
Answer: (C)
Falsify (C): need r = T, p = F; then = T and = T ⇒ T → F. (A) DS, (B) proof by cases, (D) resolution — all valid.
H4. Prove using laws (no truth table) that is a tautology.
👁 Show answer
∎
H5. A says: “If I am a knight, then B is a knight.” What are A and B?
👁 Show answer
Answer: Both knights
Statement , and . If A is a knave (a = F), S = F → anything = T — a knave saying something true ❌. So A is a knight ⇒ S true ⇒ T → b ⇒ b = T. A knight, B knight.
H6. If is FALSE, find the truth value of .
👁 Show answer
Answer: F
false ⇒ p = T, q = T, r = F. Then = F.
H7. (MSQ) Which sets are functionally complete? (A) {¬, →} (B) {∧, ∨} (C) {→} (D) {NOR}
👁 Show answer
Answer: A, D
(B) can’t express ¬ (monotone). (C) is T-preserving: with all inputs T, any →-formula is T, so ¬ is impossible. → 10 Beyond the Slides
H8. Premises: “If I’m hungry, I eat.” “I don’t eat.” “I’m hungry or tired.” Prove “I’m tired.”
👁 Show answer
Step Reason 1 , premises 2 Modus Tollens 3 premise 4 Disjunctive Syllogism (2, 3)
H9. (NAT) In how many rows of the truth table is FALSE?
👁 Show answer
Answer: 3
False ⟺ = T and r = F. is T in 3 of the 4 (p, q) rows, with r = F ⇒ 3.
H10. (MSQ) Which are equivalent to ? (A) (B) (C) (D)
👁 Show answer
Answer: All four
(D) = . Trap: students drop (C) thinking negation changes it — negating both sides keeps ↔ unchanged.
📊 Score log
| Attempt | Date | Easy /10 | Medium /20 | Hard /30 | Total /60 |
|---|---|---|---|---|---|
| 1 | |||||
| 2 |
Prev ← 11 GATE PYQs · Next → 13 Flashcards