Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 4.1.7 Quantifiers

Quantifiers are what give predicate logic a new kind of power that Boolean logic doesn’t have.

We’ll use two quantifiers:

• The universal quantifier ∀, which can be read as “for all”. It is an upside down A (as in All).

• The existential quantifier ∃, which can be read as “there exists”. It is a backwards E (as in Exists).

We can build wffs that correspond to general statements by exploiting these two quantifiers: If P is a wff, then:

∀x (P), and

∃x (P)

are wffs. Any free (unbound) instance of x in P is bound by the quantifier and is then no longer free. We’ll call P the scope of the quantifier. Notice that we put a pair of parentheses around P to remove any possible ambiguity about what the quantifier’s scope is.

Examples of wffs with quantifiers:

1. \(\forall \) x (Bear(x) \(\rightarrow \) HasTail(x))

   We have a single variable x. It is bound by the universal quantifier \(\forall \text{.}\) The scope of that \(\forall \) is all of the wff to its right. There are now no unbound variables. So this wff is a logical statement. It’s either true or false (depending on whether there are any tailless bears out there).

2. \(\exists \) x (USAPresident(x))

   We have a single variable x. It is bound by the existential quantifier \(\exists \text{.}\) The scope of that \(\exists \) is all of the wff to its right. There are now no unbound variables. So this wff is a logical statement. It happens to be true in the world in which we live.

3. \(\forall \) x ( \(\forall \) y (MotherOf(y, x) \(\vee \) FatherOf(y, x) \(\rightarrow \) ParentOf(y, x)))

   Now there are two variables, x and y. The variable x is bound by the universal quantifier \(\forall \) . The scope of that \(\forall \) is all of the wff to its right, including the second quantifier and its scope. The variable y is bound by the second universal quantifier. The scope of that \(\forall \) is all of the wff to its right. So we have that, for any pair of values x and y, if y is either the mother or the father of x, then y is also a parent of x. Both of the variables are bound, so this wff is a statement (that happens to be true).

4. \(\forall \) x ( \(\exists \) y (MotherOf(y, x)))

   Now there are two variables, x and y. The variable x is bound by the universal quantifier \(\forall \) . The scope of that \(\forall \) is all of the wff to its right, including the second quantifier and its scope. The variable y is bound by the existential quantifier \(\exists \) . The scope of that \(\exists \) is all of the wff to its right. Both of the variables are bound, so this wff is a statement (that happens to be true). Notice that the existentially quantified expression occurs inside the scope of the universally quantified one. This is important. It means that, given any particular x, there exists some y who is x’s mother. Critically, we are not claiming that it’s the same y for all possible x’s. That claim, of course, would be false.

Big Idea

The scope of a quantifier is the subexpression over which it exerts control

When the number of objects in our domain is finite, we can think of these quantifiers simply as shorthands for large Boolean expressions. In particular, let n be the number of objects in our domain.

Then:

• Think of the quantifier ∀ as shorthand for a large conjunction. When we say:

∀x (P(x)), what we’re really saying is:

P(x1) ∧ P(x2) ∧ P(x3) ∧ P(x4) ∧ … ∧ P(xn)

• Think of the quantifier ∃ as shorthand for a large disjunction. When we say:

∃x (P(x)), what we’re really saying is:

P(x1) ∨ P(x2) ∨ P(x3) ∨ P(x4) ∨ … ∨ P(xn)

Remember that ∨ means inclusive-or, so it’s possible that two or more of the disjuncts are true.

While looking at the two quantifiers, ∀ and ∃, in this way helps us to understand their meaning, it may obscure their importance. We must note:

• Even when it would be possible to write out a long conjunction or disjunction, the quantifiers can make expressions short enough that we, as people, can reason with them. There’s very little chance that we could get it right if we had to write out something like this:

MustPayTaxes(Citizen1) \(\wedge \) MustPayTaxes(Citizen2) \(\wedge \) MustPayTaxes(Citizen3) \(\wedge \cdot \)

But we should note that, when computers are doing the reasoning, it is possible to work with Boolean expressions with hundreds of thousands of terms. For example, this happens when reasoning about computer circuits.

• Even when it would be possible to write out a long conjunction or disjunction, the quantifiers give us a more enlightening way to say what we need to say. They capture key generalizations.

  For example, we might want to assert that, in a fair society, we all share the load. That claim isn’t captured by the long conjunction shown above. It is captured by the generalization:

  \(\forall \) x (Citizen(x) \(\rightarrow \) MustPayTaxes(x))

  Similarly, when we write, \(\forall \) x (Bear(x) \(\rightarrow \) Mammal(x)), we can see an essential property of being a bear.

• Even when it would be possible to write out a long conjunction or disjunction, the quantifiers make it unnecessary to change what we’re saying when our domain changes.

  Again, the tax-paying example comes to mind. We certainly don’t want to have to add every new citizen by hand to the rule.

  Here’s another example. Suppose that we want to write integrity constraints that describe properties that must be maintained as we work with an important database. For example, we might require that every employee have an emergency contact:

  \(\forall \)x (Employee(x) \(\rightarrow \)\(\exists \)y (EmergencyContact(y, x)))

  At any given time, we have a finite number of employees, so we could write this out as a long conjunction in which we state that each individual employee must have an emergency contact. But then, every time we hired someone, we’d have to go in and change that statement.

• (Most important) The quantifiers make it possible to make general claims about infinite domains whose elements can’t be written in a finite length list. If we cared only about finite domains, we could, in principle, stick with Boolean logic. While introducing quantifiers can, in that case, make some things more convenient, it adds no formal power. Not so for infinite domains. Quantified logic lets us make claims that simply cannot be made in Boolean logic.

You might think that you don’t care about infinite domains. After all, the number of atoms in the observable universe is finite. True. But there are infinite sets that we very much want to reason about. As an example, think about numbers.

Consider the set of positive integers (an infinite set). Define:

PositiveInteger(i): True whenever i is a positive integer.

HasSuccessor(i): True whenever i+1 is a positive integer.

Now we can assert that every positive integer has a successor:

\(\forall \)x (PositiveInteger(x) \(\rightarrow \) HasSucessor(x))

This claim cannot be represented in Boolean logic.

Big Idea

Quantifiers are the reason predicate logic is more powerful than Boolean logic.