Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 37 · Predicate Logic

Predicate Equivalences and Inference Rules

Learn which quantifier equivalences hold, which are common traps, and the four inference rules (universal and existential instantiation and generalization) with examples.

Propositional logic has tidy algebraic laws, and so does first-order logic, but there are more ways to go wrong. In this lesson you will learn the quantifier laws that do hold, the near-misses that do not, and the four rules of inference that let you reason with quantifiers in proofs.

Equivalences that hold

Let x not appear free in Q (a statement that does not mention x). Then:

Law Equivalence
Negation ¬∀x P ≡ ∃x ¬P, and ¬∃x P ≡ ∀x ¬P
∀ distributes over ∧ ∀x (P ∧ R) ≡ ∀x P ∧ ∀x R
∃ distributes over ∨ ∃x (P ∨ R) ≡ ∃x P ∨ ∃x R
Pulling constants out ∀x (P ∨ Q) ≡ (∀x P) ∨ Q
∃x (P ∧ Q) ≡ (∃x P) ∧ Q
∀x (Q → P) ≡ Q → ∀x P
Same-kind swap ∀x ∀y P ≡ ∀y ∀x P; ∃x ∃y P ≡ ∃y ∃x P
Renaming bound variables ∀x P(x) ≡ ∀z P(z)

The distribution laws have a slogan: ∀ goes with ∧, ∃ goes with ∨.

Only one direction holds

The "wrong pairings" are not equivalences, only one-way implications:

  • ∀x P ∨ ∀x R ⟹ ∀x (P ∨ R), but not conversely. (Everyone is a student or everyone is a teacher is much stronger than everyone is one or the other.)
  • ∃x (P ∧ R) ⟹ ∃x P ∧ ∃x R, but not conversely. (Some x is both even and odd is much stronger than some x is even and some x is odd.)
  • ∀x (P → R) ⟹ (∀x P → ∀x R), but not conversely.
  • ∃y ∀x R ⟹ ∀x ∃y R, but not conversely.

We can find a counterexample for each wrong direction by search over a tiny domain. Predicates over a 2-element domain are just pairs of booleans, so exhaustive checking is cheap.

Python Which quantifier laws really hold?

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two prints are True (real equivalences), two are False (trap equivalences), and the last two are True (valid one-way implications).

Four inference rules for quantifiers

To use quantifiers in a derivation or a written proof, you need rules for removing and adding them.

Rule Form Meaning
Universal instantiation (UI) ∀x P(x) ⊢ P(c) A universal claim applies to any particular c
Universal generalization (UG) P(c) for an arbitrary c ⊢ ∀x P(x) If c was arbitrary, the result holds for all
Existential instantiation (EI) ∃x P(x) ⊢ P(c) for a fresh name c Give a name to the object that exists
Existential generalization (EG) P(c) ⊢ ∃x P(x) A witness proves existence

The restrictions matter:

  • UG requires c to be truly arbitrary: it must not be tied to any assumption about specific objects. ("Let n be an integer. … so n² ≥ 0. Since n was arbitrary, all integers have square ≥ 0.")
  • EI requires a fresh name, one not already used for something else, because we only know some object has the property, not which.

Quantifier rules

UI From ∀x P(x) to P(c)
UG Arbitrary c gives ∀x
EI Name a witness, fresh
EG A witness gives ∃x

Generalize only from arbitrary objects

1 / 2

A classic proof: the Socrates syllogism

Premises: "All humans are mortal" ∀x (H(x) → M(x)); "Socrates is human" H(s). Conclusion: M(s).

  1. ∀x (H(x) → M(x)) (premise)
  2. H(s) (premise)
  3. H(s) → M(s) (UI on 1, with c = s)
  4. M(s) (modus ponens on 2, 3)

A more interesting one: from ∀x (P(x) → Q(x)) and ∃x P(x) conclude ∃x Q(x). By EI take a fresh c with P(c); UI gives P(c) → Q(c); so Q(c); by EG, ∃x Q(x).

Python Mechanical instantiation on a finite domain

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A faulty "proof" and the fix

Suppose ∃x P(x) and ∃x Q(x). A careless proof: "Let c be such that P(c). Let c be such that Q(c). Then P(c) ∧ Q(c), so ∃x (P(x) ∧ Q(x))." That is invalid: the same name c was used for two possibly different witnesses. The second EI needed a fresh name d, and then you could only conclude P(c) ∧ Q(d), which does not give ∃x (P(x) ∧ Q(x)). The earlier non-equivalence list says exactly this fails, and the model P = {0}, Q = {1} is the counterexample.

Prenex normal form

Every first-order formula is equivalent to one with all quantifiers pulled to the front, followed by a quantifier-free part: prenex normal form. You rename bound variables apart, then apply the "pulling out" laws. For example:

∀x P(x) ∧ ∃y Q(y) becomes ∀x ∃y (P(x) ∧ Q(y)).

Prenex form is where automated provers start. Skolemization then replaces each ∃ by a function of the preceding ∀ variables (∀x ∃y R(x, y) becomes ∀x R(x, f(x))), giving a purely universal formula suited to resolution.

Common mistakes

  • Distributing ∀ over ∨ or ∃ over ∧.
  • Generalizing from a specific instance (UG on a non-arbitrary c).
  • Reusing a witness name in EI.
  • Capturing variables when substituting (the free y in P(y) becoming bound inside ∀y). Rename bound variables first.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which equivalence is valid?

    Universal quantification distributes over conjunction; the other three are only one-way.
  2. 2. Existential instantiation requires the new constant to be...

    We only know that some object has the property, so we must not identify it with an existing name.
  3. 3. Universal generalization is allowed when...

    UG needs a fully arbitrary object; otherwise the result only covers the special case.
  4. 4. From P(c) we may always conclude...

    That is existential generalization: c is a witness.

Summary

  • ∀ distributes over ∧ and ∃ over ∨; the opposite pairings are only one-way implications.
  • UI, UG, EI and EG add and remove quantifiers; UG needs an arbitrary object, EI a fresh name.
  • Prenex normal form and Skolemization prepare formulas for automated provers.
  • Check suspicious equivalences by counterexample on tiny domains.

Next: Direct Proof and Proof by Cases