🔣 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

  1. 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.
  2. “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

#NoteWhat’s insidePriority
01FOL 01 PredicatesPredicates, subject, propositional functions⭐
02FOL 02 Quantifiers∀, ∃, domain, counterexamples, restricted domains⭐⭐⭐
03FOL 03 Quantifier EquivalencesWhen ∀/∃ distribute over ∧/∨ (and when they don’t)⭐⭐⭐
04FOL 04 Negating QuantifiersDe Morgan for quantifiers⭐⭐⭐
05FOL 05 Translating English∀ goes with →, ∃ goes with ∧ — the #1 GATE rule⭐⭐⭐
06FOL 06 Nested QuantifiersOrder of quantifiers, ∀x∃y vs ∃y∀x⭐⭐⭐
07FOL 07 Nested Translation and NegationMulti-variable translation, “exactly one”, negating nested formulas⭐⭐⭐
08FOL 08 ResolutionClauses, resolvents, proof by refutation (corrected Superman problem)⭐⭐
09FOL 09 Inference for Quantified StatementsFallacies, UI, UG, EI, EG, universal MP/MT⭐⭐
10FOL 10 Beyond the SlidesFree/bound vars, prenex form, “only / exactly / at most”, counting⭐⭐⭐
11FOL 11 GATE PYQsAll 11 PYQs from the slides, solved with shortcuts⭐⭐⭐
12FOL 12 Practice Problems30 new problems (Easy → GATE 2-mark), hidden answers⭐⭐⭐
13FOL 13 FlashcardsSpaced Repetition deck⭐⭐
14FOL 14 Memory Tricks and TrapsMnemonics + every edge case GATE uses⭐⭐⭐
15FOL 15 Cheat SheetOne-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

  1. “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.
  2. “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).
  3. Nested quantifier order — ∃y∀x ⇒ ∀x∃y, never the reverse (FOL 06 Nested Quantifiers).
  4. 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)


✅ 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

DateQuestion / SourceMy mistakeCorrect ideaLinked note

Previous chapter ← Propositional Logic · Next chapter → Set Theory