MODULE: Predicate logic

TUTORIAL Q02: Quantifiers

In predicate logic quantifiers are constructed by prefixing either the symbol "∀" or "∃" to a variable. Here are some examples :

∀x     ∃x     ∀y     ∃z

Any quantifier that starts with "∃" (such as "∃x") is an existential quantifier. "∃x" is translated as "there exists an x such that ..." We can combine a quantifier with a predicate to make a well-formed formula, as in :

∃xBx

To understand such a wff, we can rewrite it as a semi-formal statement :

   There exists an x such that Bx.

Or alternatively,

   There is at least one x such that Bx.

So what it says is that there is some object x, and x is B. In other words, it simply says that something is B. If the predicate "Bx" means x is a boy, then the wff can be translated as there is at least one boy, or a boy exists. Notice that "∃xBx", "∃yBy", "∃zBz", etc. all say the same thing. They are different wffs since they employ different variables. But they are logically equivalent nonetheless. Notice also that the truth of "∃xBx" is consistent with the claim that there is more than one B. It is just that this is not what "∃xBx" says. The latter wff says that there is one or more. It might be the case that there is just one, or it might be that there is more than one.

Any quantifier that starts with "∀" is a universal quantifer. "∀x" means "for all x, ... ". Again we can combine a universal quantifier with a predicate to form a wff, such as :

∀xBx

In semi-formal notation, this means the same as "for all x, Bx". What this says is that for any object x, x is B. If "Bx" means x is a boy, this wff would mean for every x, x is a boy. In other words, take any object whatsoever, it is a boy, which is just the same as saying that everything is a boy. Under such a translation, the wff is of course actually false.

Now consider the following formula, what do you think it means? (Suppose "Dy" means y is dirty, and "By" as before.)

∀y(By→Dy)

To work out what this wff is saying, we can rewrite the wff step-by-step as follows :

For all y, (By→Dy)
For all y, if y is a boy, then y is dirty.
Everything is such that if it is a boy, then it is dirty.

You might find the interpretation of wffs difficult at first, but if you try to understand them step-by-step, then it might become easier. We can see in the above example that the last sentence says the same as "Every boy is dirty", which is just what the wff means.

Exercises

What do these wffs mean? Use the same translation scheme as before.

• ∀zDz [Show answer]
  Everything is dirty.
• ∀z(Dz→Dz) [Show answer]
  Everything that is dirty is dirty.

---

More examples

Here are more examples. Make sure that you understand why the wffs are translated the way they are.

• ∀y~Dy: Everything is not D
• ~∀yDy: Not everything is D

The second wff above actually means "It is not the case that EVERYTHING IS D." So it says that not everything is D. This is of course the same as saying that something is not D. If you are not sure why that is the case, look at the following diagram :

Suppose the yellow region represents everything that is D. The area outside the yellow region represents things that are not D. To say that not everything is D is to say that something exists in the class represented by the region outside the D circle. So this is the same as saying that something is not D.

• ~∀y~Dy: It is not the case that everything is not D (In other words, something is D!)
• ∃yDy: Something is D
• ∃y~Dy: Something is not D
• ~∃yDy: It is not the case that something is D (So everything is not D)
• ~∃y~Dy: It is not the case that something is not D (So everything is D)

As you can see, some of these wffs are equivalent to each other :

• ∀yDy ≡ ~∃y~Dy
• ~∀yDy ≡ ∃y~Dy
• ∀y~Dy ≡ ~∃yDy
• ~∀y~Dy ≡ ∃yDy

If you are not sure why, use the diagram above to help you. What the table of equivalence tells us is that the existential quantifier can be defined in terms of the universal quantifier, and vice versa. In general, we can assume these quantifer exchange rules :

quantifier exchange rules :

(QE1) Whenever a wff in PL contains "∀x", we can replace it with "~∃x~" and the new wff is logically equivalent to the old one.

(QE2) Whenever a wff in PL contains "∃x", we can replace it with "~∀x~" and the new wff is logically equivalent to the old one.

Exercises

1. Translate these wffs in PL into English. "Bz" means z is a bird and "Fz" means z can fly.

• ∀zBz
• ~∀z~Bz
• ~∃zFz
• ∃z~Fz
• ∀z~~Bz

2. Use the quantifier exchange rules to rewrite each of above wffs into a different but logically equivalent wff.

[ ANSWERS ]

<< previous page

---

---