Predicate Logic

Predicate logic (first-order logic) extends propositional logic with variables, predicates, and quantifiers, allowing us to reason about objects and their properties.

Predicates

A predicate is a statement containing one or more variables that becomes a proposition when the variables are assigned specific values.

P(x): "x is greater than 3"
P(5) is true
P(1) is false

A predicate with n variables is called an n-place predicate or n-ary predicate.

Q(x, y): "x + y = 10"
Q(3, 7) is true
Q(2, 5) is false

The domain (or universe of discourse) is the set of values a variable can take.

Quantifiers

Quantifiers specify how many objects in the domain satisfy a predicate.

Universal Quantifier (∀)

"For all" — asserts that a predicate holds for every element in the domain.

∀x P(x)

Read: "For all x, P(x) is true."

If the domain is {a₁, a₂, ..., aₙ}, then:

∀x P(x) ≡ P(a₁) ∧ P(a₂) ∧ ... ∧ P(aₙ)

Example: Domain = integers

∀x (x² ≥ 0)     — true
∀x (x > 0)       — false (counterexample: x = -1)

Existential Quantifier (∃)

"There exists" — asserts that a predicate holds for at least one element in the domain.

∃x P(x)

Read: "There exists an x such that P(x) is true."

If the domain is {a₁, a₂, ..., aₙ}, then:

∃x P(x) ≡ P(a₁) ∨ P(a₂) ∨ ... ∨ P(aₙ)

Example: Domain = integers

∃x (x² = 4)      — true (x = 2 or x = -2)
∃x (x² = -1)     — false (no real integer squares to -1)

Uniqueness Quantifier (∃!)

"There exists exactly one" — a shorthand that can be defined in terms of ∀ and ∃.

∃!x P(x) ≡ ∃x (P(x) ∧ ∀y (P(y) → y = x))

Bound and Free Variables

A variable is bound if it is within the scope of a quantifier.
A variable is free if it is not bound by any quantifier.

∀x (P(x) ∧ Q(x, y))

Here, x is bound (by ∀x), and y is free.

A formula with no free variables is called a sentence (or closed formula) — it has a definite truth value.

A formula with free variables is called an open formula — its truth value depends on the values assigned to the free variables.

Scope

The scope of a quantifier is the part of the formula to which it applies.

∀x P(x) ∨ Q(x)

Ambiguous! Could mean:

(∀x P(x)) ∨ Q(x) — x in Q(x) is free
∀x (P(x) ∨ Q(x)) — x in Q(x) is bound

Convention: the scope of a quantifier extends as little as possible unless parentheses indicate otherwise. So ∀x P(x) ∨ Q(x) means (∀x P(x)) ∨ Q(x).

Nested Quantifiers

Predicates with multiple variables require multiple quantifiers.

∀x ∀y P(x, y)       "For all x and all y, P(x, y)"
∀x ∃y P(x, y)       "For every x, there exists a y such that P(x, y)"
∃x ∀y P(x, y)       "There exists an x such that for all y, P(x, y)"
∃x ∃y P(x, y)       "There exist x and y such that P(x, y)"

Order of Quantifiers Matters

∀x ∃y (x + y = 0)

Domain = integers. True: for any x, choose y = -x.

∃y ∀x (x + y = 0)

Domain = integers. False: no single y works for all x.

Rule: ∀x ∃y P(x, y) and ∃y ∀x P(x, y) are not equivalent in general.

However, same-type quantifiers can be reordered:

∀x ∀y P(x, y) ≡ ∀y ∀x P(x, y)
∃x ∃y P(x, y) ≡ ∃y ∃x P(x, y)

Relationship Between Quantifier Orderings

∃y ∀x P(x, y) → ∀x ∃y P(x, y)

The reverse does not hold in general. If one y works for all x, then certainly for each x we can find a y (the same one). But if each x has its own y, there may not be a single y for all.

Negation of Quantified Statements

De Morgan's laws for quantifiers:

¬(∀x P(x)) ≡ ∃x ¬P(x)
¬(∃x P(x)) ≡ ∀x ¬P(x)

In words:

"Not everything is P" ≡ "Something is not P"
"Nothing is P" ≡ "Everything is not P"

Negating Nested Quantifiers

Push ¬ inward, flipping each quantifier:

¬(∀x ∃y P(x, y))
≡ ∃x ¬(∃y P(x, y))
≡ ∃x ∀y ¬P(x, y)

Example: Negate "Every student has taken some course."

Original: ∀s ∃c Taken(s, c)
Negation: ∃s ∀c ¬Taken(s, c)
English:  "There is a student who has not taken any course."

Translating English to Predicate Logic

Example 1: "All humans are mortal."

∀x (Human(x) → Mortal(x))

Note: Use → with ∀ (not ∧). "∀x (Human(x) ∧ Mortal(x))" would mean "everything is a mortal human."

Example 2: "Some students are hardworking."

∃x (Student(x) ∧ Hardworking(x))

Note: Use ∧ with ∃ (not →). "∃x (Student(x) → Hardworking(x))" would be trivially true if anything is not a student.

Common pattern:

∀ typically pairs with →
∃ typically pairs with ∧

Example 3: "No bird can swim."

¬∃x (Bird(x) ∧ CanSwim(x))
≡ ∀x (Bird(x) → ¬CanSwim(x))

Example 4: "Every student who studies hard passes the exam."

∀x ((Student(x) ∧ StudiesHard(x)) → Passes(x))

Example 5: "There is a number that is greater than every other number." (Domain: reals)

∃x ∀y (x ≥ y)

This is false over the reals (no maximum).

Prenex Normal Form

A formula is in prenex normal form if it has the structure:

Q₁x₁ Q₂x₂ ... Qₙxₙ φ(x₁, x₂, ..., xₙ)

where each Qᵢ is ∀ or ∃, and φ is quantifier-free (the matrix).

The sequence Q₁x₁ Q₂x₂ ... Qₙxₙ is the prefix.

Converting to Prenex Normal Form

Eliminate → and ↔ using equivalences.
Push ¬ inward using De Morgan's laws for quantifiers.
Rename bound variables to avoid clashes (standardize apart).
Move quantifiers to the front.

Example:

∀x P(x) → ∃x Q(x)
≡ ¬(∀x P(x)) ∨ ∃x Q(x)          (eliminate →)
≡ ∃x ¬P(x) ∨ ∃y Q(y)            (rename to avoid clash)
≡ ∃x ∃y (¬P(x) ∨ Q(y))          (move quantifiers out)

Logical Equivalences in Predicate Logic

Distribution over ∧ and ∨:

∀x (P(x) ∧ Q(x)) ≡ ∀x P(x) ∧ ∀x Q(x)
∃x (P(x) ∨ Q(x)) ≡ ∃x P(x) ∨ ∃x Q(x)

Non-equivalences (be careful):

∀x (P(x) ∨ Q(x)) ≢ ∀x P(x) ∨ ∀x Q(x)
∃x (P(x) ∧ Q(x)) ≢ ∃x P(x) ∧ ∃x Q(x)

Quantifiers with unrelated variables: If y does not appear free in P(x):

∀x P(x) ∧ Q(y) ≡ ∀x (P(x) ∧ Q(y))
∃x P(x) ∨ Q(y) ≡ ∃x (P(x) ∨ Q(y))

Inference Rules in Predicate Logic

Universal Instantiation (UI)

∀x P(x)
∴ P(c)        for any element c in the domain

Universal Generalization (UG)

P(c)          for an arbitrary c
∴ ∀x P(x)

(c must be arbitrary, not a specific element)

Existential Instantiation (EI)

∃x P(x)
∴ P(c)        for some specific (but unknown) element c

(c must be a fresh constant not used elsewhere)

Existential Generalization (EG)

P(c)          for some element c
∴ ∃x P(x)

Real-World Applications

Database queries: SQL essentially uses predicate logic. SELECT * FROM users WHERE age > 18 corresponds to {u | User(u) ∧ age(u) > 18}.
Program specification: Pre/post conditions are predicate logic formulas. ∀arr ∀i (0 ≤ i < len(arr) - 1 → arr[i] ≤ arr[i+1]) specifies a sorted array.
Knowledge representation: Ontologies and knowledge bases (Prolog, Datalog, OWL) use first-order logic.
Formal verification: Proving program correctness using Hoare logic involves predicate logic assertions.
Type systems: Type judgments like ∀α. α → α (polymorphic identity function) are quantified statements.