First-Order & Predicate Logic

Last lesson left propositional logic stuck on too coarse an atom — unable to say “every human is mortal,” because it cannot see inside a statement to the objects and properties within. Here is the language that cracks the atom open. “Every dog has a tail.” Propositional logic cannot state it: Dog → Tail talks about one dog at a time and has no word for “every.” To quantify over objects — “every”, “some” — you need the richer language of 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 ∧. That same “for-all / there-exists” structure is what you write to 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 or 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 plus the power 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)

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 does not 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, the rule flips. “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, ∃x King(x) ⇒ Person(x), goes vacuously true the moment a single non-king exists (the implication holds for that non-king), so it asserts almost nothing.

How GATE asks this

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

1. MCQ — English ↔ FOL translation. 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 (GATE DA 2026)

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 fail: (B) asserts every object in the domain is both a king and a person (pebbles are not kings, so false); (C) uses ∃ and a vacuously-true ⇒; (D) says “some king is a person” — true, but weaker than the every we want. (GATE DA 2026, Q14.)

Worked example 2 — quantifier-implication validity (GATE DA 2026)

Over a non-empty domain, which of these 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 is exactly what lets you “pick one.”
• (ii) Not valid. One P does not make all P. Counterexample: domain of two objects with P true for one and false for the other — ∃x P(x) holds, ∀x P(x) does not.
• (iii) Not valid. The ⇒ direction (ii) 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 its antecedent is true.

So only (i) is valid (GATE DA 2026, Q48) — “one of four,” as the prompt asked. The takeaway: ∀ ⇒ ∃ is the one quantifier-implication that always works on a non-empty domain; every other direction needs extra structure.

In one breath

First-order logic adds to propositional logic the ability to name objects (constants), describe properties and relations (predicates), and quantify over a domain with ∀ (“for all”) and ∃ (“there exists”); the one rule that prevents most errors is that a universal restricts with implication — “all A are B” is ∀x A(x) ⇒ B(x) (never ∧) — while an existential restricts with conjunction — “some A is B” is ∃x A(x) ∧ B(x) (never ⇒); ∀x P(x) ⇒ ∃x P(x) is valid on a non-empty domain, its converse is not, and the dualities ∀x P ≡ ¬∃x ¬P and ∃x P ≡ ¬∀x ¬P let you push negations through.

Practice

A question to carry forward

Logic — propositional and first-order alike — trades only in certainty. A fact is true or it is false; one statement entails another or it does not. But that crispness is also a cage. ∀x Bird(x) ⇒ Flies(x) is flatly false the instant a single penguin exists, and yet “birds usually fly” is both true and genuinely useful. Logic has no word for “usually,” no way to hold a belief at degree 0.9.

The real world runs almost entirely on such degrees. A doctor does not know you have the disease; she assigns it a probability that rises with each symptom. An engine does not know the engine will fail; it estimates a likelihood. Here is the thread onward into a new sub-topic: how do you reason when knowledge is a matter of degree rather than true-or-false — how do you wire up “this influences that” as a web of probabilities, and read off the chance of one thing given another without listing every possible state of the world?