17.4.3 Variables and Quantifiers

We now have all the machinery necessary to return to our earlier discussion of variables. As noted above, variables are used in two ways in FOPC: to refer to particular anonymous objects and to refer generically to all objects in a collection. These two uses are made possible through the use of operators known as quantifiers. The two operators that are basic to FOPC are the existential quantifier, which is denoted $ \exists $, and is pronounced as “there exists”, and the universal quantifier, which is denoted $ \forall $, and is pronounced as “for all”.

The need for an existentially quantified variable is often signaled by the presence of an indefinite noun phrase in English. Consider the following example:

a restaurant that serves Mexican food near ICSI.

Here reference is being made to an anonymous object of a specified category with particular properties. The following would be a reasonable representation of the meaning of such a phrase:

$ \exists x $Restaurant(x)

$$ \begin{array}{l}\land Serves(x,MexicanFood)\\\land Near((LocationOf(x),LocationOf(ICSI)))\end{array} $$

The existential quantifier at the head of this sentence instructs us on how to interpret the variable x in the context of this sentence. Informally, it says that for this sentence to be true there must be at least one object such that if we were to substitute it for the variable x, the resulting sentence would be true. For example,

if AyCaramba is a Mexican restaurant near ICSI, then substituting AyCaramba for x results in the following logical formula:

Restaurant (AyCaramba)

$$ \land S e r v e s(A y C a r a m b a,M e x i c a n F o o d) $$

$$ \land Near((LocationOf(AyCaramba),LocationOf(ICSI)) $$

Based on the semantics of the $ \wedge $ operator, this sentence will be true if all of its three component atomic formulas are true. These in turn will be true if they are either present in the system's knowledge base or can be inferred from other facts in the knowledge base.

The use of the universal quantifier also has an interpretation based on substitution of known objects for variables. The substitution semantics for the universal quantifier takes the expression for all quite literally; the $ \forall $ operator states that for the logical formula in question to be true the substitution of any object in the knowledge base for the universally quantified variable should result in a true formula. This is in marked contrast to the $ \exists $ operator which only insists on a single valid substitution for the sentence to be true.

Consider the following example:

(17.24) All vegetarian restaurants serve vegetarian food.

A reasonable representation for this sentence would be something like the following:

$$ \forall xVegetarianRestaurant(x)\Rightarrow Serves(x,VegetarianFood) $$

For this sentence to be true, it must be the case that every substitution of a known object for x must result in a sentence that is true. We can divide up the set of all possible substitutions into the set of objects consisting of vegetarian restaurants and the set consisting of everything else. Let us first consider the case where the substituted object actually is a vegetarian restaurant; one such substitution would result in the following sentence:

$$ \begin{array}{l}Vegetarian Restaurant(Maharani)\\ \quad\Rightarrow Serves(Maharani,Vegetarian Food)\end{array} $$

If we assume that we know that the consequent clause,

Serves(Maharani, VegetarianFood)

is true then this sentence as a whole must be true. Both the antecedent and the consequent have the value True and, therefore, according to the first two rows of Fig. 17.4 the sentence itself can have the value True. This result will, of course, be the same for all possible substitutions of Terms representing vegetarian restaurants for x.

Remember, however, that for this sentence to be true it must be true for all possible substitutions. What happens when we consider a substitution from the set of objects that are not vegetarian restaurants? Consider the substitution of a non-vegetarian restaurant such as Ay Caramba's for the variable x:

$$ \begin{array}{l}Vegetarian Restaurant(Ay Caramba)\\ \quad\Rightarrow Serves(Ay Caramba,Vegetarian Food)\end{array} $$

Since the antecedent of the implication is False, we can determine from Fig. 17.4 that the sentence is always True, again satisfying the $ \forall $ constraint.

Note, that it may still be the case that Ay Caramba serves vegetarian food without actually being a vegetarian restaurant. Note also, that despite our choice of examples, there are no implied categorical restrictions on the objects that can be substituted for x by this kind of reasoning. In other words, there is no restriction of x to restaurants or concepts related to them. Consider the following substitution:

$$ \begin{array}{l}Vegetarian Restaurant(Carburetor)\\ \quad\Rightarrow Serves(Carburetor,Vegetarian Food)\end{array} $$

Here the antecedent is still false and hence the rule remains true under this kind of irrelevant substitution.

To review, variables in logical formulas must be either existentially (∃) or universally (∀) quantified. To satisfy an existentially quantified variable, there must be at least one substitution that results in a true sentence. Sentences with universally quantified variables must be true under all possible substitutions.