17.4.1 Elements of First Order Logic

We will explore FOL in a bottom-up fashion by first examining its various atomic elements and then showing how they can be composed to create larger meaning representations. Fig. 17.3, which provides a complete context-free grammar for the particular syntax of FOL that we will be using, will be our roadmap for this section.

Let's begin by examining the notion of a $ \text{Term} $, the FOL device for representing objects. As can be seen from Figure 17.3, FOL provides three ways to represent these basic building blocks: constants, functions, and variables. Each of these devices can be thought of as a way of naming, or pointing to, an object in the world under consideration.

Constants in FOL refer to specific objects in the world being described. Such constants are conventionally depicted as either single capitalized letters such as A and B or single capitalized words that are often reminiscent of proper nouns such as Maharani and Harry. Like programming language constants, FOL constants refer

to exactly one object. Objects can, however, have multiple constants that refer to them.

Functions in FOPC correspond to concepts that are often expressed in English as genitives such as Frasca's location. A FOL translation of such an expression might look like the following.

LocationOf(Frasca)

FOPC functions are syntactically the same as single argument predicates. It is important to remember, however, that while they have the appearance of predicates they are in fact Terms in that they refer to unique objects. Functions provide a convenient way to refer to specific objects without having to associate a named constant with them. This is particularly convenient in cases where many named objects, like restaurants, will have a unique concept such as a location associated

with them.

The notion of a $ \underline{variable} $ is our final FOPC mechanism for referring to objects. Variables, which are normally depicted as single lower-case letters, give us the ability to make assertions and draw inferences about objects without having to make reference to any particular named object. This ability to make statements about anonymous objects comes in two flavors: making statements about a particular unknown object and making statements about all the objects in some arbitrary world of objects. We will return to the topic of variables after we have presented quantifiers, the elements of FOPC that will make them useful.

Now that we have the means to refer to objects, we can move on to the FOPC mechanisms that are used to state relations that hold among objects. As one might guess from its name, FOPC is organized around the notion of the predicate. Predicates are symbols that refer to, or name, the relations that hold among some fixed number of objects in a given domain. Returning to the example introduced informally in Section 17.1, a reasonable FOPC representation for Maharani serves vegetarian food might look like the following formula:

Serves(Maharani, VegetarianFood)

This FOPC sentence asserts that Serves, a two-place predicate, holds between the objects denoted by the constants Maharani and VegetarianFood.

A somewhat different use of predicates is illustrated by the following typical representation for a sentence like Maharani is a restaurant:

Restaurant (Maharani)

This is an example of a one-place predicate that is used, not to relate multiple objects, but rather to assert a property of a single object. In this case, it encodes the category membership of Maharani. We should note that while this is a common-place way to deal with categories it is probably not the most useful. Section 17.5 will return to the topic of the representation of categories.

With the ability to refer to objects, to assert facts about objects, and to relate objects to one another, we have the ability to create rudimentary composite representations. These representations correspond to the atomic formula level in Figure 17.3. Recall that this ability to create composite meaning representations was one of the core components of the meaning structure of language described in Section 17.2.

This ability to compose complex representations is not limited to the use of single predicates. Larger composite representations can also be put together through the use of logical connectives. As can be seen from Figure 17.3, logical connectives give us the ability to create larger representations by conjoining logical formulas using one of three operators. Consider, for example, the following BERP sentence and one possible representation for it:

(17.21) I only have five dollars and I don't have a lot of time.

$$ Have(Speaker,FiveDollars)\land\neg Have(Speaker,LotOfTime) $$

The semantic representation for this example is built up in a straightforward way from semantics of the individual clauses through the use of the $ \land $ and $ \neg $ operators. Note that the recursive nature of the grammar in Figure 17.3 allows an infinite number of logical formulas to be created through the use of these connectives. Thus as with syntax, we have the ability to create an infinite number of representations using a finite device.