First-Order (Predicate) Logic

Propositional logic cannot express "every student has a roll number" or "some number is larger than all others". First-order (predicate) logic adds variables that range over a domain, predicates about them, and quantifiers.

Predicates and quantifiers

A predicate P(x) becomes a proposition once x is given a value: with P(x) = "x > 3", P(5) is true and P(2) is false.

The truth value depends on the domain: ∀x (x² ≥ x) is true over the integers but false over the reals (x = 0.5). Over a finite domain {a₁, …, aₙ}, ∀x P(x) is P(a₁) ∧ … ∧ P(aₙ) and ∃x P(x) is P(a₁) ∨ … ∨ P(aₙ).

Negation

Negation swaps the quantifiers (De Morgan's laws for quantifiers):

• ¬∀x P(x) ≡ ∃x ¬P(x) ("not everyone passed" = "someone failed")
• ¬∃x P(x) ≡ ∀x ¬P(x) ("no one passed" = "everyone failed")

Pushing negations inward through nested quantifiers flips each one: ¬∀x ∃y P(x, y) ≡ ∃x ∀y ¬P(x, y).

Translating English

The two standard patterns:

• "All A are B": ∀x (A(x) → B(x)). Using ∧ instead would claim everything is both A and B.
• "Some A are B": ∃x (A(x) ∧ B(x)). Using → instead would be true as soon as anything is not an A.

The order of quantifiers matters

Quantifiers of the same kind can be swapped (∀x ∀y ≡ ∀y ∀x, ∃x ∃y ≡ ∃y ∃x), but mixed quantifiers cannot:

• ∃y ∀x P(x, y) → ∀x ∃y P(x, y) is valid: if one y works for every x, then every x has some y.
• The converse is not valid: "every person has a mother" (∀x ∃y) does not mean "someone is everyone's mother" (∃y ∀x).

Evaluating over a small finite domain makes the differences visible:

D = range(1, 5)

different = lambda x, y: x != y
print("for all x, exists y with y != x:", all(any(different(x, y) for y in D) for x in D))
print("exists y, for all x with y != x:", any(all(different(x, y) for x in D) for y in D))

even = lambda x: x % 2 == 0
odd = lambda x: x % 2 == 1
print("forall x (even or odd):         ", all(even(x) or odd(x) for x in D))
print("(forall x even) or (forall x odd):", all(even(x) for x in D) or all(odd(x) for x in D))
print("exists x (even and odd):        ", any(even(x) and odd(x) for x in D))
print("(exists x even) and (exists x odd):", any(even(x) for x in D) and any(odd(x) for x in D))

for all x, exists y with y != x: True
exists y, for all x with y != x: False
forall x (even or odd):          True
(forall x even) or (forall x odd): False
exists x (even and odd):         False
(exists x even) and (exists x odd): True

Which laws hold?

The program above shows the failures: every number is even or odd, but not all numbers are even and not all are odd; and some number is even and some is odd, but no number is both.

A variable in the scope of a quantifier is bound; otherwise it is free. A formula with free variables is not a proposition until they are given values.

Practice questions