Mathematics.

first order logic

Predicate Logic

Mathematical Logic30 minDifficulty4 out of 10

You should know: propositional logic

Overview

Predicate logic (also called first-order logic, predicate calculus, or quantificational logic) is a formal system used across mathematics, philosophy, linguistics, and computer science. Unlike propositional logic, which treats statements like 'all humans are mortal' as indivisible units, predicate logic looks inside them: it introduces variables, predicates, and quantifiers, so the same statement becomes 'for all x, if x is a human, then x is mortal' — where 'for all x' is a quantifier, x is a variable, and 'is a human' / 'is mortal' are predicates. This extra structure makes predicate logic strictly more expressive than propositional logic, while still building on its connectives.

Intuition

Propositional logic can only say 'Socrates is mortal' as one blob of true/false — it can't express 'everyone like Socrates is mortal' without a new blob for every person. Predicate logic fixes this by introducing variables (x, y, ...) and predicates (functions like Human(x) or Mortal(x)) that take those variables as arguments, plus two quantifiers: ∀ ('for all') and ∃ ('there exists'). Now one formula, ∀x(Human(x) → Mortal(x)), captures the general claim, and you can plug in any specific object for x to get a specific instance.

Formal Definition

Definition

A first-order language consists of variables, predicate symbols, function symbols, constants, the propositional connectives, and the two quantifiers ∀ (universal) and ∃ (existential). ∀x P(x) asserts P(x) holds for every object x in the domain of discourse; ∃x P(x) asserts P(x) holds for at least one x. The quantifiers are dual to each other through negation.

¬∀x P(x)  ⟺  ∃x ¬P(x)\lnot \forall x\, P(x) \iff \exists x\, \lnot P(x)
Negation of universal quantifier
¬∃x P(x)  ⟺  ∀x ¬P(x)\lnot \exists x\, P(x) \iff \forall x\, \lnot P(x)
Negation of existential quantifier
∀x (Human(x)→Mortal(x))\forall x\, (Human(x) \to Mortal(x))
'All humans are mortal'

Notation

NotationMeaning
∀x\forall xUniversal quantifier — 'for all x'
∃x\exists xExistential quantifier — 'there exists an x such that'
P(x)P(x)A predicate — a property that x may or may not satisfy
∃!x\exists! xUnique existential quantifier — 'there exists exactly one x such that'
t1=t2t_1 = t_2Equality between two terms, usually built into first-order logic

Properties

Quantifier negation duality

¬∀x P(x)  ⟺  ∃x ¬P(x)\lnot \forall x\, P(x) \iff \exists x\, \lnot P(x)

Quantifier commutativity (same kind)

∀x∀y P(x,y)  ⟺  ∀y∀x P(x,y)\forall x \forall y\, P(x,y) \iff \forall y \forall x\, P(x,y)

Non-commutativity across kinds

∃x∀y P(x,y)→∀y∃x P(x,y)\exists x \forall y\, P(x,y) \to \forall y \exists x\, P(x,y)

Condition: The converse implication does not hold in general

Distribution of ∀ over ∧

∀x (P(x)∧Q(x))  ⟺  (∀x P(x))∧(∀x Q(x))\forall x\,(P(x) \land Q(x)) \iff (\forall x\, P(x)) \land (\forall x\, Q(x))

Applications

Database query languages (relational algebra, SQL's WHERE clauses) and program verification tools (Hoare logic) are built on first-order predicate statements over relations and program states.

Worked Examples

  1. For every integer x, there exists some y that is its successor.

    ∀x (Int(x)→∃y Succ(x,y))\forall x\,(Int(x) \to \exists y\, Succ(x,y))

Answer: ∀x (Int(x) → ∃y Succ(x,y))

Practice Problems

Difficulty 4/10

Negate ∃x P(x) using quantifier duality.

Difficulty 5/10

Which statement is generally NOT equivalent to the other order of quantifiers ∃x∀y P(x,y)?

Difficulty 5/10

A database query 'return every student who has taken ALL required courses' uses which quantifier structure, and how do you negate 'the student took all required courses'?

Common Mistakes

Common Mistake

Freely swapping ∀ and ∃ when they appear in sequence, e.g. treating ∃x∀y P(x,y) as equivalent to ∀y∃x P(x,y).

∃x∀y P(x,y) → ∀y∃x P(x,y) is valid, but the reverse implication is not. Example: P(x,y) = 'x < y' over integers: ∀y∃x(x<y) is true (always a smaller number), but ∃x∀y(x<y) is false (no smallest integer).

Common Mistake

Forgetting to flip the quantifier when negating.

Negation flips ∀ to ∃ and vice versa: ¬∀x P(x) ⟺ ∃x ¬P(x), not ∀x ¬P(x).

Quiz

The negation of ∀x P(x) is:
Predicate (first-order) logic extends propositional logic by adding:

Summary

  • Predicate logic extends propositional logic with variables, predicates, and quantifiers (∀, ∃).
  • ∀x P(x) means P holds for every x in the domain; ∃x P(x) means P holds for at least one x.
  • Negating a quantifier flips it: ¬∀x P(x) ⟺ ∃x ¬P(x), and ¬∃x P(x) ⟺ ∀x ¬P(x).
  • Quantifiers of the same kind commute; mixed quantifiers (∃∀ vs ∀∃) generally do not.
  • Predicate logic underlies databases, program verification, and automated reasoning systems.

References

  1. WebsiteWikipedia — First-order logic
  2. BookEnderton, H. A Mathematical Introduction to Logic, 2nd ed., Ch. 2.