🔣 First Order Logic (Predicate Logic) — GATE Hub
What this folder is
GATE-focused notes for Discrete Mathematics → Chapter 2: First Order Logic, built from the Neso Academy slides (123 pages) and extended with topics GATE asks that the slides skip. Prerequisite: Propositional Logic hub — especially 08 Logical Equivalences and 09 Rules of Inference.
Two slide errors corrected in these notes
- Superman resolution problem — the slides translate “neither impotent nor malevolent” as (that’s “not both”) and then resolve on two literal pairs at once. Corrected in FOL 08 Resolution.
- “Most cars are inexpensive” — the slides treat “most” as ∃. That’s a simplification; “most” isn’t expressible in standard FOL. See FOL 04 Negating Quantifiers.
🗺️ Map of Content
| # | Note | What’s inside | Priority |
|---|---|---|---|
| 01 | FOL 01 Predicates | Predicates, subject, propositional functions | ⭐ |
| 02 | FOL 02 Quantifiers | ∀, ∃, domain, counterexamples, restricted domains | ⭐⭐⭐ |
| 03 | FOL 03 Quantifier Equivalences | When ∀/∃ distribute over ∧/∨ (and when they don’t) | ⭐⭐⭐ |
| 04 | FOL 04 Negating Quantifiers | De Morgan for quantifiers | ⭐⭐⭐ |
| 05 | FOL 05 Translating English | ∀ goes with →, ∃ goes with ∧ — the #1 GATE rule | ⭐⭐⭐ |
| 06 | FOL 06 Nested Quantifiers | Order of quantifiers, ∀x∃y vs ∃y∀x | ⭐⭐⭐ |
| 07 | FOL 07 Nested Translation and Negation | Multi-variable translation, “exactly one”, negating nested formulas | ⭐⭐⭐ |
| 08 | FOL 08 Resolution | Clauses, resolvents, proof by refutation (corrected Superman problem) | ⭐⭐ |
| 09 | FOL 09 Inference for Quantified Statements | Fallacies, UI, UG, EI, EG, universal MP/MT | ⭐⭐ |
| 10 | FOL 10 Beyond the Slides | Free/bound vars, prenex form, “only / exactly / at most”, counting | ⭐⭐⭐ |
| 11 | FOL 11 GATE PYQs | All 11 PYQs from the slides, solved with shortcuts | ⭐⭐⭐ |
| 12 | FOL 12 Practice Problems | 30 new problems (Easy → GATE 2-mark), hidden answers | ⭐⭐⭐ |
| 13 | FOL 13 Flashcards | Spaced Repetition deck | ⭐⭐ |
| 14 | FOL 14 Memory Tricks and Traps | Mnemonics + every edge case GATE uses | ⭐⭐⭐ |
| 15 | FOL 15 Cheat Sheet | One-page revision sheet | ⭐⭐⭐ |
🔗 Concept Flow
graph LR PL[Propositional Logic] --> A[Predicates] A --> B[Quantifiers ∀ ∃] B --> C[Quantifier equivalences] B --> D[Negation] B --> E[Translation] E --> F[Nested quantifiers] F --> G[Nested translation & negation] D --> G PL --> H[Resolution] B --> I[Inference: UI UG EI EG]
🎯 How GATE tests this chapter
Question patterns that keep repeating
- “Which is the correct translation of …?” → apply ∀ with →, ∃ with ∧ and check each option (FOL 05 Translating English). Appears in GATE 2004, 2005, 2006, 2007, 2009, 2012, 2013, 2014.
- “Which is NOT equivalent / which is always true?” → push negations, build a 2-element counter-model (FOL 03 Quantifier Equivalences, FOL 10 Beyond the Slides).
- Nested quantifier order — ∃y∀x ⇒ ∀x∃y, never the reverse (FOL 06 Nested Quantifiers).
- Negation of English statements (“not all”, “none”, “no one”) (FOL 04 Negating Quantifiers).
Formats: MCQ (negative marking), MSQ (all correct options needed), NAT.
📅 Suggested study plan (5 sessions)
- Day 1 — FOL 01 Predicates, FOL 02 Quantifiers, FOL 03 Quantifier Equivalences
- Day 2 — FOL 04 Negating Quantifiers, FOL 05 Translating English
- Day 3 — FOL 06 Nested Quantifiers, FOL 07 Nested Translation and Negation
- Day 4 — FOL 08 Resolution, FOL 09 Inference for Quantified Statements, FOL 10 Beyond the Slides
- Day 5 — FOL 11 GATE PYQs (timed) → FOL 12 Practice Problems → FOL 14 Memory Tricks and Traps
- Ongoing — FOL 13 Flashcards daily; FOL 15 Cheat Sheet weekly
✅ Mastery checklist
- I can say why “x > 3” is not a proposition but “∀x (x > 3)” is
- I always pair ∀ with → and ∃ with ∧ when translating “all / some … are …”
- I can negate any quantified statement so no ¬ sits in front of a quantifier
- I know which of the four distributions (∀/∧, ∀/∨, ∃/∧, ∃/∨) are equivalences and which are one-way
- I can explain why ∃y∀x P(x,y) → ∀x∃y P(x,y) is valid but not the converse
- I can write “exactly one”, “at least two”, “at most one”, “only” in FOL
- I can do a resolution refutation and know that you resolve on one pair at a time
- I’ve solved all 11 PYQs and scored ≥ 80% on the practice set
📝 Mistake log
Track every question you get wrong
Date Question / Source My mistake Correct idea Linked note
Previous chapter ← Propositional Logic · Next chapter → Set Theory