Skip to main content

Subsection 5.1.17 Summary of the New Rules

Here’s one way to think about how we use these instantiation and generalization rules:

Video cover image

We instantiate. Then we work in the simpler world of Boolean logic. Then we generalize at the end.

Here are some important ideas to keep in mind as you’re doing this:

  • Quantifier Exchange is an equivalence rule. So it can be used anywhere in an expression. (In other words, it’s fine to apply it to an entire expression, but application to smaller subexpressions is also allowed.)

  • Inference rules (unlike equivalence rules) can be applied only to entire statements, not to subexpressions within statements. The instantiation and generalization rules are inference rules.

  • So, if we want to instantiate (i.e., remove a quantifier), we must work from the outside in.

  • On the other hand, if we want to generalize (i.e., add a quantifier), we must work from the inside out.

  • Because of the requirement that Existential Instantiation must use a previously undefined element (but Universal Instantiation does not have that requirement), it generally makes sense to do Existential Instantiations first.

  • Some of our new predicate logic rules are natural generalizations, to a possibly infinite domain, of Boolean logic rules that we already had:

    • The quantifier exchange rules generalize the Boolean De Morgan’s laws. We’ve already seen why that’s so.

    • Universal Instantiation generalizes Boolean Simplification. Recall that the quantifier ∀ can be thought of as another way of writing a large (possibly even infinite) conjunction. So we have this generalization of Simplification:

P(x1) ∧ P(x2) ∧ P(x3) ∧ . . . written as: ∀x (P(x))

∴ P(xk)

If I know that some claim is true for all values, then I can conclude that it must be true for any individual one.

  • Universal Generalization generalizes Boolean Conjunction: Again, recall that ∀ can be thought of as another way of writing a large (possibly even infinite) conjunction. So we have this generalization of Conjunction:

P(c) → P(x1)

P(x2)

. . .

∴ P(x1) ∧ P(x2) ∧ . . . written as: ∀x (P(x))

If I know that some claim is true for some arbitrary individual c, then I know that it must be true for individual1 and individual2 and so forth. Thus it is true of all individuals. Note the sense in which Universal Instantiation and Universal Generalization are inverses of each other.

  • Existential Generalization generalizes Boolean Addition: Recall that the quantifier ∃ can be thought of as another way of writing a large (possibly even infinite) disjunction So we have this generalization of Addition:

P(x1)

∴ P(x1) ∨ P(x2) ∨ P(x3) . . . written as: ∃x (P(x))

If I know that some claim is true for one individual then I know that it is true of at least one element out of some possibly infinite set.

  • Existential Instantiation doesn’t generalize any of our Boolean rules, but it’s interesting nevertheless to write it out in an analogous way:

P(x1) ∨ P(x2) ∨ P(x3) . . . written as: ∃x (P(x))

∴ P(xk) for some xk

If I know that there exists some individual of whom some claim is true, then there must be at least one specific one of whom it’s true. Note the sense in which Existential Instantiation and Existential Generalization are inverses of each other.

Big Idea

In the appendix, you’ll find a Predicate logic “cheat sheet”. You may want to keep it handy while working proofs.