First Order Predicate Logic Explained: Quantifiers, Translation and Worked Examples

Learn how predicates get meaning from a domain, why quantifier order matters, and how to translate, negate and evaluate formulas without losing their scope.

KnowledgeGate Team

Exam prep & CS education

Updated 4 Nov 20266 min read
First Order Predicate Logic Explained: Quantifiers, Translation and Worked Examples

Propositional logic feels manageable until a single symbol such as P becomes Prime(x). Truth then depends on the chosen domain and the value assigned to x, while swapping ∀ and ∃ can reverse the claim. A sound analysis fixes the first-order language, domain, interpretation and quantifier scope before translating or negating the formula; a finite model then settles it with witnesses and counterexamples.

First-order predicate logic: what it adds to propositional logic

Let P mean "3 is prime". This proposition already has a truth value. By contrast, Prime(x) is a predicate. Its truth cannot be decided until we know the domain and the value assigned to x. Over {1,2,3,4}, Prime(2)=true, while Prime(4)=false.

First-order predicate logic talks about individual objects, their properties, and relations between them. It is called first-order because its variables range over individuals in the domain, not over predicates or sets of individuals.

Atomic formulas can still be joined with ¬, ∧, ∨, →, and ↔. The new power comes from ∀x, meaning "for every x", and ∃x, meaning "there exists an x". For the connective layer and its bridge into quantifiers, use Propositional and Predicate Logic in Discrete Mathematics. First-order analysis continues from that foundation by defining terms, predicates, relations, scope, substitution and model evaluation.

The vocabulary of a first-order language

Use one numerical language over D={1,2,3,4}. It may contain variables x,y, constants 1,4, unary predicates Even(x) and Odd(x), and the binary predicate Less(x,y), meaning x<y. As a separate syntax example, a unary function succ(x) returns the successor object as defined by the chosen model. Predicates return truth values. Functions return objects in the domain.

This separates terms from formulas:

  • x, 1, and succ(x) are terms that name or produce objects.

  • Even(x) and Less(x,4) are atomic formulas.

  • Even(x) → Less(x,4) is a compound formula.

  • A bare term such as succ(2) is not a true-or-false assertion.

Parentheses show the scope of each quantifier:

  • ∀x(Even(x) → Less(x,4)): every even element is less than 4.

  • ∃y(Less(2,y) ∧ Odd(y)): some odd element is greater than 2.

  • ∀x(Even(x) → ∃y(Less(x,y) ∧ Odd(y))): every even element has a larger odd element.

Translate English carefully: quantifier order changes the claim

Universal and Existential Quantifiers Explained isolates witness, counterexample and scope tactics for ∀ and ∃. Full first-order translation adds class predicates, domain guards, relations and an explicit interpretation. Take the finite model U={Asha,Bharat,Charu,Logic,Graphs}. Let Student={Asha,Bharat,Charu} and Book={Logic,Graphs}, with the reading relation:

Reads={(Asha,Logic),(Bharat,Logic),(Bharat,Graphs),(Charu,Graphs)}.

"Every student reads some book" becomes:

∀x(Student(x) → ∃y(Book(y) ∧ Reads(x,y)))

It is true. Asha has witness Logic; Bharat has witnesses Logic and Graphs; Charu has witness Graphs.

Now translate "There is a book that every student reads":

∃y(Book(y) ∧ ∀x(Student(x) → Reads(x,y)))

This is false. Logic fails for Charu, while Graphs fails for Asha. In ∀x∃y, a different y may witness the claim for each x. In ∃y∀x, one common y must work for every x.

A student-by-book grid showing who has read Logic and Graphs, with every student reading some book true and one shared book false.

Worked finite model: evaluate a quantified sentence step by step

Fix the interpretation first: D={1,2,3,4}, Even={2,4}, Odd={1,3}, and Less={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}.

Evaluate φ = ∀x(Even(x) → ∃y(Less(x,y) ∧ Odd(y))), which says "every even element has a larger odd element".

  1. At x=1, Even(1) is false, so the implication is true. The inner existential is also true with y=3.

  2. At x=2, Even(2) is true. Choose y=3; both 2<3 and Odd(3) are true, so the implication is true.

  3. At x=3, Even(3) is false, so the implication is true. No odd element greater than 3 exists in D.

  4. At x=4, Even(4) is true, but no y in D satisfies 4<y. The implication is false.

Therefore, φ=false in this model. A universal statement needs every case to pass, and x=4 is one counterexample. The same formula may have a different truth value under another domain or interpretation, so the model is part of the problem.

A table over D={1,2,3,4} testing each element for a larger odd element, with x=4 as the counterexample that makes the formula false.

Negate quantified formulas without losing scope

The core quantifier rules are ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x). Also use ¬(P → Q) ≡ P ∧ ¬Q and De Morgan's laws.

Negate the worked formula one controlled step at a time:

  1. ¬φ = ∃x ¬(Even(x) → ∃y(Less(x,y) ∧ Odd(y)))

  2. ¬φ = ∃x(Even(x) ∧ ¬∃y(Less(x,y) ∧ Odd(y)))

  3. ¬φ = ∃x(Even(x) ∧ ∀y(¬Less(x,y) ∨ ¬Odd(y)))

The earlier counterexample now becomes a witness. Choose x=4: Even(4)=true, and for every y in the domain, either 4<y is false or Odd(y) is false. Thus ¬φ=true, exactly matching φ=false.

Free variables, bound variables and safe substitution

In Even(x) ∧ ∃y Less(x,y), both occurrences of x are free. The occurrence of y is bound within the existential scope. This is an open formula, not a sentence, so it needs an assignment for x before it becomes true or false.

With x:=2, Even(2) is true and y=3 witnesses Less(2,y), so the formula is true. With x:=4, Even(4) is true but no larger y exists in D, so it is false.

Closing it as ∀x(Even(x) → ∃y Less(x,y)) produces a sentence, and that sentence is false, with the counterexample x=4. Renaming bound y in ∃y Less(x,y) to z gives ∃z Less(x,z) without changing the meaning, provided the new name does not capture a free variable.

Predicate-logic traps and how questions expose them

Trap

Failure

Repair

Swap ∀x∃y with ∃y∀x

Different witnesses become one common witness

Translate the quantifiers in spoken order

Reverse "all A are B"

Write B(x)→A(x)

Write ∀x(A(x)→B(x))

Mishandle a false antecedent

Mark false→Q as false

An implication with a false antecedent is true

Push ¬ past a quantifier unchanged

Keep ∀ or ∃

Switch ∀ and ∃, then negate the body

Call an open formula a proposition

Ignore a free variable

Supply an assignment or bind the variable

Quantifiers also do not distribute blindly. On D={1,2}, let P(x) mean x=1 and Q(x) mean x=2. Both ∃x P(x) and ∃x Q(x) are true, but ∃x(P(x) ∧ Q(x)) is false. No single object is both 1 and 2.

Representative tasks ask you to translate a sentence, identify free and bound variables, compare quantifier orders, negate a formula, evaluate it on a finite domain, or find a counterexample. Quantifiers and Predicate Logic Practice Problems: Step-by-Step Solutions supplies a larger drill set of translations, truth evaluations and negations. Build semantic control first by interpreting each symbol and domain, then use the drill set to increase speed. GATE Guidance by Sanchit Sir provides the structured GATE pathway without treating one question pattern as guaranteed.

First-order predicate logic: the short version and next step

Use this six-step recall ladder:

  1. Choose the domain.

  2. Interpret constants, functions, and predicates.

  3. Mark every quantifier's scope.

  4. Identify any free variables.

  5. Evaluate ∃ by finding a witness.

  6. Evaluate ∀ by checking every object or finding one counterexample.

As a retrieval task, rewrite both student-book formulas from memory. Then explain the contrast in one sentence: different books may witness the first formula, but no single book witnesses the second.

For adjacent core-CS learning, continue through CS Fundamentals for Exams and Placements. If predicate logic is your only weak point, repeat the two finite-model traces before moving on.