FOL 12 · Practice Problems
How to use
30 problems in three levels. Answers are collapsed — commit before you click. Score: Easy 1 · Medium 2 · Hard 3 → total 60. Aim for ≥ 48. MSQ = multiple correct options, NAT = numeric.
🟢 Level 1 — Easy
E1. Is “x > 3” a proposition? What about “∀x (x > 3)” over the integers?
👁 Show answer
“x > 3” — no (predicate, x free). “∀x (x > 3)” — yes, and it’s F (x = 0). → FOL 01 Predicates
E2. P(x): x² > x, domain integers. Find P(0), P(2), P(−1).
👁 Show answer
P(0): 0 > 0 F · P(2): 4 > 2 T · P(−1): 1 > −1 T
E3. Truth value of over the reals?
👁 Show answer
T
E4. Truth value of over the positive integers?
👁 Show answer
F — the only solution, x = −2, isn’t in the domain. Domain trap.
E5. Negate with no ¬ in front of the quantifier.
👁 Show answer
E6. Negate .
👁 Show answer
E7. Translate “Every student is smart.” (domain: people; S: student, M: smart)
👁 Show answer
E8. Translate “Some student is smart.”
👁 Show answer
E9. Domain {1, 2, 3}. Write and without quantifiers.
👁 Show answer
and
E10. In , which variables are free / bound? Is it a proposition?
👁 Show answer
x bound, y free ⇒ not a proposition. → FOL 10 Beyond the Slides
🟡 Level 2 — Medium (GATE 1-mark style)
M1. Domain: integers. Truth values of (i) (ii)
👁 Show answer
(i) T (y = −x) (ii) F (no single y works for every x)
M2. Truth value of over (i) natural numbers {0, 1, 2, …} (ii) integers?
👁 Show answer
(i) F — x = 0 has no smaller natural (ii) T — y = x − 1. Same formula, domain flips the answer.
M3. Truth value of over (i) naturals (ii) integers?
👁 Show answer
(i) T — x = 0 (ii) F — no least integer
M4. (MSQ) Which are equivalent to ? (A) (B) (C) (D)
👁 Show answer
Answer: A, D
(D) simplifies to (A). (C) has the wrong quantifier — negation flips ∀ to ∃.
M5. Write “No student likes exams” in two equivalent forms.
👁 Show answer
M6. Is ? Give a counter-model if not.
👁 Show answer
No. Domain {1, 2}: P = (T, F), Q = (F, T). LHS T, RHS F. → FOL 03 Quantifier Equivalences
M7. Which direction is valid: or its converse?
👁 Show answer
The given direction (left → right) is valid. The converse fails on the same P = (T, F), Q = (F, T) model.
M8. Translate “Everyone has exactly one mother.” M(x, y): y is the mother of x.
👁 Show answer
, or
M9. “All birds fly. Tweety does not fly. ∴ Tweety is not a bird.” Valid?
👁 Show answer
Valid — universal modus tollens. (Whether the premise “all birds fly” is true doesn’t matter for validity.)
M10. Translate “Only students can vote.” (S: student, V: can vote)
👁 Show answer
— “only” flips the arrow. Not (that’s “all students can vote”).
🔴 Level 3 — Hard (GATE 2-mark style)
H1. (MSQ) Which are valid for all P? (A) (B) (C) (D)
👁 Show answer
Answer: A, C
(A) a single x that works for all y also gives each y an x. (B) converse fails: P(x, y): x = y over {1, 2}. (C) take the witness of ∃xP; it’s also a Q. (D) fails on P = (T, F), Q = (F, T).
H2. (NAT) Domain {a, b}. P(a) = T, P(b) = F, Q(a) = F, Q(b) = T. How many of these are TRUE? i. ii. iii. iv.
👁 Show answer
Answer: 2
i T, ii F, iii F, iv T. This one model separates both non-equivalences.
H3. Translate “There is exactly one topper in the class.” (domain: students; T(x): x is a topper)
👁 Show answer
H4. Translate (i) “At least two students passed” (ii) “At most one student passed.” (P: passed)
👁 Show answer
(i) (ii) — note it’s TRUE when nobody passed.
H5. Negate fully.
👁 Show answer
H6. L(x, y): x loves y. Write “Everybody loves somebody” and “Somebody is loved by everybody”. Which implies which?
👁 Show answer
and . The second implies the first (∃y∀x ⇒ ∀x∃y), not conversely.
H7. Use resolution to show , , ⊢ .
👁 Show answer
Add . + → . + → . + → . + → □ ✅ → FOL 08 Resolution
H8. (NAT) Domain has 2 elements; P is a unary predicate. How many interpretations of P make true? How many make true?
👁 Show answer
interpretations total. : 3 (all but all-false). : 2 (exactly one element true).
H9. Translate “Not every student passed, but some did.”
👁 Show answer
H10. A student writes: “From and , by EI get and , so .” What’s wrong?
👁 Show answer
EI must introduce a fresh constant each time: and . Nothing says c = d, so the conclusion doesn’t follow (counter-model: P = (T, F), Q = (F, T)). → FOL 09 Inference for Quantified Statements
📊 Score log
| Attempt | Date | Easy /10 | Medium /20 | Hard /30 | Total /60 |
|---|---|---|---|---|---|
| 1 | |||||
| 2 |
Prev ← FOL 11 GATE PYQs · Next → FOL 13 Flashcards