datarekha

First-Order & Predicate Logic

Translate English into ∀ and ∃ without falling into the most common GATE trap — the ∀ uses ⇒, ∃ uses ∧ rule.

8 min read Intermediate GATE DA Lesson 104 of 122

What you'll learn

  • Predicates, constants, variables, and the two quantifiers ∀ and ∃
  • The signature trap: 'All A are B' is ∀x A(x) ⇒ B(x), never ∀x A(x) ∧ B(x)
  • For ∃ you usually want ∧, not ⇒
  • Quantifier-implication validity: ∀x P(x) ⇒ ∃x P(x) is valid; the converse is not
  • Reading and writing FOL translations the way GATE phrases them

Before you start

Propositional Logic GATE DA · lesson Machine Learning section Generative AI section

“Every dog has a tail.” Propositional logic can’t say that — Dog → Tail only talks about one dog at a time. To quantify over objects (“every”, “some”), you need a richer language: first-order (predicate) logic, or FOL.

The vocabulary is small, the traps are predictable, and almost every GATE question on this topic turns on one tiny choice — whether the connective inside the quantifier should be ⇒ or ∧. The same “for-all / there-exists” structure is what you write when you query a knowledge graph, state a database integrity constraint, or specify what a system must guarantee — so getting the quantifier right is a working skill, not just an exam trick.

The pieces

  • Constants name specific objects — Alice, India, 7.
  • Variables range over a domain of objects — usually written x, y.
  • Predicates describe properties or relations — King(x), Person(x), Likes(x, y), Parent(x, y). A predicate applied to constants/variables becomes a proposition (true or false in a given world).
  • Quantifiers bind variables:
    • ∀x ϕ(x) — “for all x, ϕ(x) holds” (universal).
    • ∃x ϕ(x) — “there exists an x such that ϕ(x) holds” (existential).

Inside ϕ you still use the propositional connectives ¬, ∧, ∨, ⇒, ⇔. So FOL is propositional logic with the ability to quantify over a domain.

The signature trap: ∀ uses ⇒, ∃ uses ∧

This is the single biggest source of wrong answers — and the question GATE most loves to set.

Take the English sentence “All kings are persons.” The correct FOL is:

∀x  King(x) ⇒ Person(x)

Why? Read it aloud: “for every object x, if x is a king, then x is a person.” When x is some random pebble, King(pebble) is false, the implication is vacuously true, and the pebble doesn’t break the sentence.

The wrong version — the one that catches people — is:

∀x  King(x) ∧ Person(x)    ✗

That reads “every object in the domain is both a king and a person.” Pebbles included. False in any realistic world.

For existentials, flip the rule. “Some king is a person” is:

∃x  King(x) ∧ Person(x)

“There exists an x who is both a king and a person.” The wrong version here would be ∃x King(x) ⇒ Person(x), which is vacuously true the moment a single non-king exists (the implication holds for that non-king). Useless.

Universal ∀ → use ⇒∀x King(x) ⇒ Person(x)“Every king is a person.”∀x King(x) ∧ Person(x) ✗Says every object is BOTHa king and a person — almost never true.Existential ∃ → use ∧∃x King(x) ∧ Person(x)“Some king is a person.”∃x King(x) ⇒ Person(x) ✗Vacuously true as soon as onenon-king exists. Asserts nothing.
Memorise this pairing: ∀ with ⇒, ∃ with ∧. Swapping them is the most-tested FOL error.

How GATE asks this

Two patterns, both close to the surface of the rule above:

  1. MCQ — English ↔ FOL translation. You’re given a sentence in English and four FOL formulas; pick the correct one. The wrong options almost always include the ∀x A(x) ∧ B(x) trap, the converse B(x) ⇒ A(x), and a swap like ∃x A(x) ⇒ B(x).
  2. MSQ — quantifier-implication validity. Given a non-empty domain, which of ∀x P(x) ⇒ ∃x P(x), ∃x P(x) ⇒ ∀x P(x), etc., are valid (true under every interpretation)?

Worked example 1 — translation (real 2026 question)

Which FOL formula correctly captures “Each king is a person”?

(A) ∀x King(x) ⇒ Person(x)
(B) ∀x King(x) ∧ Person(x)
(C) ∃x King(x) ⇒ Person(x)
(D) ∃x King(x) ∧ Person(x)

Apply the rule: “each / every / all” is ∀, and under ∀ the connective is ⇒. That gives (A).

Why the rest are wrong:

  • (B) asserts every object in the domain is both a king and a person. Pebbles are not kings, so this is false in any realistic world.
  • (C) uses ∃, which only claims at least one king exists. Even worse, the ⇒ inside ∃ is vacuously true the moment a single non-king exists.
  • (D) says “some king is a person” — true, but weaker than what we want (which is every king).

(This is GATE DA 2026, Q14.)

Worked example 2 — quantifier-implication validity (real 2026 question)

Over a non-empty domain, which of the following are valid (true under every interpretation)?

(i) ∀x P(x) ⇒ ∃x P(x)
(ii) ∃x P(x) ⇒ ∀x P(x)
(iii) ∃x P(x) ⇔ ∀x P(x)
(iv) ∀x P(x) ⇒ ∃x ¬P(x)

Run each through your head:

  • (i) Valid. If P holds for every x, pick any one of them — P holds for it, so “there exists” is satisfied. The non-empty-domain condition is exactly what guarantees you can “pick one”.
  • (ii) Not valid. One P doesn’t make all P. Counterexample: domain {a, b}, with P(a) = T, P(b) = F. Then ∃x P(x) is true but ∀x P(x) is false.
  • (iii) Not valid. The ⇒ direction (ii) above already fails, so the ⇔ fails too. Same counterexample.
  • (iv) Not valid. If P holds for every x, then ¬P holds for none, so ∃x ¬P(x) is false — the implication is false whenever the antecedent is true.

So only (i) is valid. (This is GATE DA 2026, Q48.)

The takeaway: ∀ ⇒ ∃ is the one quantifier-implication that always works (given a non-empty domain). Every other direction needs extra structure.

Quick check

Quick check

0/6
Q1Which FOL formula correctly captures 'Every student passed the exam'? (Let S(x) = 'x is a student', P(x) = 'x passed the exam'.)
Q2Which FOL formula correctly captures 'Some king is a person'?
Q3Over a non-empty domain, which of the following are VALID (true under every interpretation)? (select all that apply)select all that apply
Q4Which FOL formula correctly captures 'Everyone loves someone'? (Let L(x, y) = 'x loves y'.)
Q5Which statements about FOL are TRUE? (select all that apply)select all that apply
Q6Which FOL formula correctly captures 'No bird can fly underwater'? (Let B(x) = 'x is a bird', F(x) = 'x can fly underwater'.)

Practice this in an interview

All questions
What makes a predicate sargable, and what are the most common ways to accidentally make a predicate non-sargable?

A sargable predicate (Search ARGument ABLE) is one the engine can evaluate using an index seek — a direct traversal to the matching key range. Predicates become non-sargable when a function or implicit cast is applied to the indexed column, forcing the engine to compute a derived value for every row before comparing.

What is the logical processing order of a SQL SELECT statement?

SQL processes clauses in this order: FROM, WHERE, GROUP BY, HAVING, SELECT, ORDER BY, LIMIT. This matters because it explains why you cannot use a SELECT alias in a WHERE clause, but you can use it in ORDER BY.

How does operator precedence work with AND and OR in a WHERE clause?

AND binds more tightly than OR, just like multiplication binds more tightly than addition. Without parentheses, the expression A OR B AND C is evaluated as A OR (B AND C), not (A OR B) AND C. Always use parentheses when mixing AND and OR to make intent explicit.

Sign in to track your progress

Completed lessons, your XP, level, and streak save to your account — it's free and takes a few seconds.

Explore further

Related lessons

Propositional Logic Reading Pseudocode & Predicting Output Always-True Synthesis Drills Relational Algebra I
Skip to content