15
The Predicate Calculus
15.1 Motivation
The propositional calculus has several limitations. We can’t, for example, express the fact that when we move block B, say, it is the same block that ON_B_C asserts is on block C. In the propositional calculus, atoms are strings that have no internal structure. In propositions about toy blocks, ON_A_B and ON_B_C are completely different with absolutely nothing in common. Even though I used mnemonic names for these atoms (to help us remember what I intend them to mean), I could just as well have used different proposition letters for them, say, P124 and Q23, respectively.
A more useful language would be one that could refer to objects in the world (such as blocks) as well as to propositions about the world. We need a language that has names for the objects about which we want to state propositions and names for the propositions we want to state. In our world of toy blocks (which I hereinafter call the “blocks world”), we might have had propositions such as ON_B_C ⊃ ¬CLEAR_C, where CLEAR_C is intended to mean that block C has nothing on it. To express a fact like this for each of several blocks would require several propositional formulas. It would be nice if we could simply say something like On(x, y) ⊃ ¬Clear(y), where x and y are variables that could refer to any blocks.
In this chapter, I present a language, called the first-order predicate calculus, which has these desired features. The predicate calculus has symbols called object constants, relation constants, and function constants, plus some other constructs that will be introduced later. These language entities will be used (when I discuss semantics) to refer to objects in the world and to propositions about the world.
15.2 The Language and Its Syntax
I first introduce a restricted version of the predicate calculus that I will later expand. Again, for now, resist the temptation to impute meanings to the constructs of the language. That way, you will be on the same footing as the computer programs that will have to manipulate these structures! All expressions in the language will be set in typewriter font. (There are many different typographical conventions for the predicate calculus used in books and papers. The one used here is not universal!)
Components
We have an infinite set of object constants. These will be strings of alphanumeric characters (often mnemonic, but that helps only us, not the computer). My convention will be that object constants begin with either a capital letter or a numeral.
Examples: Aa, 125, 13B, Q, John, EiffelTower
And we will have an infinite set of function constants of all “arities.”1 These will be strings of alphanumeric characters beginning always with a lowercase letter and (for now) superscripted by their arity.
Examples: fatherOf1, distanceBetween2, times2
We also have an infinite set of relation constants of all arities. These will be strings of alphanumeric characters beginning with a capital letter and (for now) superscripted by their arity. (I sometimes call a relation constant a predicate.)
Examples: B173, Parent2, Large1, Clear1, X114
I also will use the propositional connectives ∨, ∧, ¬, and ⊃, and delimiters (,), [,], and separator,.
Terms
A function constant of arity n, followed by n terms in parentheses and separated by commas, is a term. This type of term is called a functional expression. In displaying such a term, I usually omit the arity superscript when its value is obvious from context. We might think of object constants as function constants of arity 0.
Examples: fatherOf (John, Bill), times(4, plus(3, 6)), Sam
wffs
Atoms: a relation constant of arity n followed by n terms in parentheses and separated by commas is an atom (also called an atomic formula). A relation constant of arity 0 omits the parentheses. Again, I usually omit the arity superscript when its value is obvious from context.
An atom is a wff.
Examples: Greaterthan(7, 2), P(A, B, C, D), Q
Propositional wffs: any expression formed out of predicate-calculus wffs in the same way that the propositional calculus forms wffs out of other wffs is a wff, called a propositional wff.
Example: [Greaterthan(7, 2) ∧ Lessthan(15, 4)] ∨ ¬Brother(John, Sam) ∨ P
(Remember that the wffs used in these examples aren’t supposed to mean anything!)
I will also use the extensions I made in the propositional calculus (conjunctions with more than two conjuncts, disjunctions with more than two disjuncts, clauses, (conjunctive) sets of clauses, etc.) as wffs in the predicate calculus. For now, these are the only terms and wffs we will consider; I will introduce others (which will allow the promised variables) shortly.
15.3 Semantics
15.3.1 Worlds
We now have a language that can be used to refer to objects in the world as well as to propositions. Here is what we can talk about now.
• The world can have an infinite number of objects, also called individuals, in it. These can be individuals that are rather concrete, like Block A, Mt. Whitney, Julius Caesar, and so on. Or they can be abstract entities like the number 7, π, the set of all integers, and so on. They can even be fictional or invented entities (about whose actual existence people might argue), like beauty, Santa Claus, a unicorn, honesty, and so on. As long as we are willing to give it a name and say something about it, we can think of it as an actual individual in a world we want to talk about.
• Functions on individuals. We can have an infinite number of functions of all arities that map n tuples of individuals into individuals. For example, there might be a function that maps a person into his or her father or one that maps the numbers 10 and 2 into the quotient 5.
• Relations over individuals. The individuals can participate in an arbitrary number of relations. These will each have arities. (A relation of arity 1 is called a property.) Thus, individuals might have properties such as heavy, big, blue, and so on, and they might participate in relations like bigger, in between, and so on. To specify an n-ary relation extensionally, we explicitly list all of the n tuples of individuals that participate in that relation.
15.3.2 Interpretations
An interpretation of an expression in the predicate calculus is an assignment that maps object constants into objects in the world, n-ary function constants into n-ary functions, and n-ary relation constants into n-ary relations. These assignments are called the denotations of their corresponding predicate-calculus expressions. The set of objects to which object constant assignments are made is called the domain of the interpretation.
Given an interpretation for its component parts, an atom has the value True just in case the denoted relation holds for those individuals denoted by its terms. If the relation doesn’t hold, the atom has value False.
The values True and False of nonatomic wffs are determined by the same truth table used in the propositional calculus.
Example: Consider the blocks world again. It is a world in which there exist entities, A, B, C, and Floor.2 We will eventually be creating an assignment that maps elements of the predicate calculus into these world objects. Since we cannot actually make the world objects themselves be the values of assignments, we imagine that the world is a mathematical structure, which (among other things) contains the mathematical objects A, B, C, and Floor. (Try not to be bothered by the statement “the world is a mathematical structure.” Whatever the world really is, it won’t matter for our purposes that we consider it to be a mathematical structure.)
We also imagine relations among these objects. For example, we might have the relations On and Clear. These relations can be defined extensionally by the n tuples of objects that participate in them. For example, suppose we have the configuration of blocks shown in Figure 15.1. In this world, the relation On is given by the pairs <B, A>, <A, C>, and <C, Floor>. The relation Clear is given by the singleton, <B>.
Figure 15.1 A Configuration of Blocks
So, the individuals A, B, C, and Floor, and the relations On and Clear constitute the blocks world in this example. To describe that world in the predicate calculus, I employ the object constants A, B, C, and F1, the binary relation constant On, and the unary relation constant Clear. I am using mnemonic symbols here for convenience; probably it would be better pedagogy to use the relation constants G0045, G123, …, and so on in order to emphasize the notion that the symbols used in our predicate-calculus language do not have any preassigned meanings.
Our intended interpretation (which is just one of many possible interpretations) for these predicate-calculus expressions is given in Table 15.1. We can use these assignments to determine the value of some predicate-calculus wffs:
On(A, B) is False because <A,B> is not in the relation On.
Clear(B) is True because <B> is in the relation Clear.
On(C, F1) is True because <C, Floor> is in the relation On.
On(C, F1) ∧ On(α, B) is True because both On(C, F1) and ¬On(A, B) are True.
Table 15.1 A Mapping between Predicate Calculus and the World
| Predicate Calculus | World |
| A | A |
| B | B |
| C | C |
| F1 | Floor |
| On | On = {< B, A >, < A, C >, < C, Floor >} |
| Clear | Clear = {< B >} |
15.3.3 Models and Related Notions
Several semantic notions have the same definitions in the predicate calculus as they do in the propositional calculus. To review,
• An interpretation satisfies a wff if the wff has the value True under that interpretation.
• An interpretation that satisfies a wff is a model of that wff.
• Any wff that has the value True under all interpretations is valid.
• Any wff that does not have a model is inconsistent or unsatisfiable.
• If a wff ω has value True under all of those interpretations for which each of the wffs in a set Δ has value True, then Δ logically entails ω (Δ 
ω).
• Two wffs are equivalent if and only if their truth values are identical under all interpretations (that is, if and only if the two wffs logically entail one another).
15.3.4 Knowledge
Predicate-calculus formulas can be used to represent knowledge that an agent has about the world. A set, Δ, of such formulas is called a knowledge base of the agent, and if the formula ω is included in Δ, we say (loosely) that the agent “knows” ω. (It would be more accurate to say that the agent “believes” ω.)
Let’s examine more closely what might be meant when we say that a set of formulas embodies knowledge about the world. For example, do the following formulas embody knowledge about a possible blocks world?
Using the mnemonics as a hint, we can easily construct blocks-world interpretations that satisfy these formulas and thus are models of them. The situations we have in mind are illustrated pictorially in Figure 15.2. In all three of these, the model uses the same mapping of object constants to objects that was used in Table 15.1. The mappings between relation constants and relations in the world are different in the three models, however. In one, the relation constant On is mapped to the relation On = {< B, A >, < A, Floor >, < C, Floor >}, and the relation constant Clear is mapped to the relation Clear = {< C > < B >}. You can easily establish the models corresponding to the other two blocks-world situations.
Figure 15.2 Three Blocks-World Situations
There are also models of these formulas other than the ones suggested by the predicate-calculus mnenomics. For example, there is a model in which B and C are just different predicate-calculus names for the same object in the world, say, B. And there are models in which A, B, and C aren’t assigned to blocks at all but to numbers, say.3 Some of these alternative models might be ruled out by providing additional formulas. For example, we could rule out the models corresponding to two of the situations in Figure 15.2 by supplying the additional formula Clear (A), assuming again the assignment of object constants to objects given in Table 15.1. As I mentioned when discussing the propositional calculus, the more formulas we have, the fewer are their models. So, if we want to pin down the meanings of a set of formulas so that these formulas constitute “knowledge” about a particular world, we must have sufficient formulas so that their models not only include the world we have in mind but exclude worlds with which we do not want our world to be confused.
15.4 Quantification
Suppose we wanted to say that every object in the domain had a certain property (or participated in a certain relation). We could do this for finite domains by a conjunction such as Clear(B1) ∧ Clear(B2) ∧ Clear(B3) ∧ Clear(B4). But long conjunctions are cumbersome, and we can’t even write down infinite ones, which might be needed if the domain were infinite.
Or suppose we wanted to say that at least one object in the domain had a certain property. For finite domains, such a statement could be made by a disjunction such as Clear(B1) ∨ Clear(B2) ∨ Clear(B3) ∨ Clear(B4). Again, there is a problem with large or infinite domains.
I introduce new syntactic entities for these purposes, namely, variable symbols and quantifier symbols. In addition to the syntactic entities previously introduced:
1. We have an infinite set of variable symbols consisting of strings beginning with lowercase letters near the end of the alphabet, such as p, q, r, s, t,…, p1, p2,…, and so on. (These will be distinguished from function constants by their use in context.) A variable symbol is a term (in addition to the terms I defined previously). Thus f (x, Bob, C17) is a ternary functional expression, for example.
2. We have the quantifier symbols, ∀ and ∃. ∀ is called a universal quantifier, and ∃ is called an existential quantifier.
3. If ω is a wff and ξ is a variable symbol, then both (∀ξ)ω and (∃ξ)ω are wffs. ξ is called the variable quantified over, and ω is said to be within the scope of the quantifier. Wffs of the form (Qξ)ω where ξ is a variable symbol and Q is either ∀ or ∃ will most commonly (in our applications) be such that ω has the variable symbol ξ embedded somewhere within it as a term. If all variable symbols besides ξ in ω are quantified over in ω, then (Qξ)ω is called a closed wff or closed sentence. In all of our applications, wffs will be closed.
Examples: (∀x)[P(x) ⊃ R(x)], (∃x)[P(x) ⊃ (∃y)[R(x,y) ⊃ S(f(x))]]
We would be able to show (after describing the semantics of quantifiers below) that (∀x)[(∀y)ω is equivalent to (∀y)[(∀x)ω], so we could just as well group the universally quantified variables in a string in front of ω: (∀x, y)ω. In such a formula, ω is called the matrix. Similarly, for existential quantifiers. But mixtures of universal and existential quantifiers must retain their order! It is not the case that (∀x)[(∃y)ω] is equivalent to (∃y)[(∀x)ω].
We would also be able to show (after describing semantics below) that the variable of a quantifier is a kind of “dummy variable” and thus can be renamed without changing the value of the wff. Thus (∀x)ω is equivalent to (∀y)ω if all occurrences of x in ω are replaced by y. Similarly, for existential quantifiers.
Since quantifying over variable symbols gives the predicate calculus so much expressive power, you may ask whether or not we can quantify over relation and function symbols also. In the version of the predicate calculus we are using, such quantification is not allowed. For this reason, it is called the first-order predicate calculus. Second- and higher-order predicate calculi allow quantification over relation and function symbols, but at the expense of much more complex inference mechanisms.
15.5 Semantics of Quantifiers
15.5.1 Universal Quantifiers
(∀ξ)ω(ξ) has the value True (under a given assignment of object constants, function constants, and relation constants to objects, functions, and relations) just in case ω(ξ) has the value True for all assignments of the variable symbol ξ to objects in the domain.
Example: Suppose we use the two interpretations for Clear and On suggested by the configurations in Figure 15.2. Under each of these interpretations, what is the truth value of (∀x)[On(x, C) ¬Clear(C)]? In these interpretations, the variable x can be assigned either to A, B, C, or Floor. We must investigate each of these assignments in turn for each of the interpretations. For example, with x assigned to A, if On(x, C) ¬Clear(C) is to have value True, we would either have to have <A,C> not in the relation On or <C> not in the relation Clear. In fact, in each interpretation, <C> is in the relation Clear, but <A, C> is not in the relation On, so the first assignment (of x to A) results in the value True. I leave it to you to investigate the remaining assignments.
15.5.2 Existential Quantifiers
(∃ξ)ω(ξ) has the value True (under a given assignment to objects, functions, and relations) just in case ω(ξ) has the value True for at least one assignment of the variable symbol ξ to objects in the domain.
15.5.3 Useful Equivalences
The following equivalences, analogous to DeMorgan’s laws, can be established given the semantics of the quantifiers:
And I have already mentioned
15.5.4 Rules of Inference
The propositional-calculus rules of inference, suitably generalized, can also be used with the predicate calculus. These include modus ponens, ∧ introduction and elimination, ∨ introduction, ¬ elimination, and resolution. I generalize the resolution rule in the next chapter. In addition to the propositional rules, two important ones are
• Universal instantiation (UI). From (∀ξ)ω(ξ), infer ω(α), where ω(ξ) is any wff with variable ξ, α is any constant symbol, and ω(α) is ω(ξ) with α substituted for ξ throughout ω.
Example: From (∀x)P(x, f (x), B) infer P(A, f (A), B).
• Existential generalization (EG). From ω(α), infer (∀ξ)ω(ξ), where ω(α) is a wff containing a constant symbol α, and ω(ξ) is a form with ξ replacing every occurrence of α throughout ω.
Example: From (∀x)Q(A, g(A), x) infer (∃y)(∀x)Q(y, g(y), x).
It is easy to show that both UI and EG are sound rules of inference.
15.6 Predicate Calculus as a Language for Representing Knowledge
15.6.1 Conceptualizations
The big problem for AI is what to say, not how to say it. The predicate calculus does no more than provide a uniform language in which knowledge about the world (after we have it!) can be expressed and reasoned about. The consequences of the knowledge thus represented can be explored through logical deduction methods to be described in the next chapter.
The first step in representing knowledge about a world is to conceptualize it in terms of its objects, functions, and relations. Conceptualization usually involves an act of invention on the part of the conceptualizer. There are often many choices about what kinds of objects we think might exist in our worlds. We are free to conceptualize the world in any way we wish; however, some conceptualizations will be more useful (not necessarily more “correct”) than others.
Next, we invent predicate-calculus expressions whose intended meanings involve the objects, functions, and relations. Finally, we write wffs that are satisfied by the world as we have conceptualized it. These wffs will be satisfied by other interpretations as well; we need only to take care that they are not satisfied by interpretations that our state of knowledge about the world can preclude.
When designing agents that must reason about and interact with actual (rather than imagined) worlds, it is important that conceptualizations be grounded. That is, the truth values of at least some of the atoms used in a knowledge base must be evaluable through perceptual mechanisms connected to the world. Other atoms may be defined in terms of these primitive, perceptual ones, but the whole structure must rest on perception of some sort if the conclusions produced by logical methods are to have relevance to the world the robot inhabits. Mathematics, on the other hand, does not need to be grounded because mathematical statements need not be about the physical world.
The first serious proposal in AI to use the predicate calculus to represent knowledge about the world was by John McCarthy [McCarthy 1958]. A large project (the CYC project) to represent millions of commonsense facts about the world is described in [Guha & Lenat 1990, Lenat 1995, Lenat & Guha 1990]. For a more complete discussion of the role of logic in AI, see [Nilsson 1991]. For a textbook treatment of AI based on logic, see [Genesereth & Nilsson 1987].
15.6.2 Examples
I illustrate the process of conceptualizing knowledge about a world with some examples. Suppose we are designing an agent that delivers packages in an office building. Among other things, it will need to have a relation constant whose intended denotation is the property of something being a package. Let’s use Package(x). Most likely, it will need to have a relation constant whose intended denotation is that a certain object is in a certain room. Let’s use Inroom(x, y). And, to handle my examples, it will need to have a relation constant whose intended denotation is that a certain object is smaller than another certain object. With these, we can express in the predicate calculus the following sample statements about the world of this robot:
• “All of the packages in room 27 are smaller than any of the packages in room 28.”
• “Every package in room 27 is smaller than one of the packages in room 29.”
This statement is ambiguous as it stands (a common phenomenon when using everyday language). It could be represented by either of the following two formulas (which are not equivalent!):
Some knowledge about our robot’s world may require us to conceptualize the notion of time. Consider, for example, the statement “Package A arrived before Package B.” A reasonable conceptualization would have objects that are time intervals and ordering relations on the intervals. And we must have a way of stating the arrival time of an object. Let’s use Arrived(x, z), where x denotes an arriving object, and z denotes the time interval during which it arrived. With these, we can write
I discuss a conceptualization for time intervals in more detail in Chapter 18. There are also other methods, some involving temporal logics [Emerson 1989, Shoham 1987], that have been used in computer science and AI to deal with time.
Inventing conceptualizations can often involve rather thorny questions. For example, it is difficult to decide how to deal with so-called mass nouns such as “milk” in the statement, “The package in room 28 contains one quart of milk.” Is milk an object having the property, say, of being white? If so, what happens when we divide a quart into two pints? Does it become two objects (both of which are white), or does it remain as one? Many of these questions remain subjects for continuing research.
Later in the book, I will use conceptualizations that treat intangible things, such as situations and actions, as objects. I will also introduce extensions to the predicate calculus that will allow one agent to make statements about the knowledge of another agent, as in “Robot A knows that Package B is in room 28.”
15.7 Additional Readings and Discussion
As previously mentioned, the use of logical sentences to represent knowledge and the use of logical inference procedures to do reasoning has been controversial in AI. See [McDermott & Doyle 1980] and the associated discussion for examples of the points made by both sides. Some of the controversy has to do with the mismatch between the precise semantics of logical languages due to [Tarski 1935] (see [Tarski 1956] for an English translation) and the more fluid and context-dependent ideas of meaning that seem to be required for representations of real-world (as opposed to mathematical) knowledge.
Tarskian semantics associates definite world individuals with object constants in the language. An alternative view emphasizes the need for so-called indexical-functional representations. In the words of Agre and Chapman [Agre & Chapman 1990, p. 21]:
Whereas traditional representations posit a “semantic” correspondence between symbols in an agent’s head and objectively individuated objects in the world, our theory describes a causal relationship between the agent and indexically and functionally individuated entities in the world. For example, one of the entities Pengi [described in [Agre & Chapman 1987]] works with is the-bee-I-am-chasing. This entity is individuated indexically in that it is defined in terms of its relationship to the agent (“I”). It is also individuated functionally in that it is defined in terms of one of the agent’s ongoing projects (chasing a bee). Whereas in a traditional representation, the symbols BEE-34 and BEE-35 would always refer to the same two bees, different bees might be the-bee-I-am-chasing at different times.
Nevertheless, as we shall see in following chapters, researchers have been able to employ logical languages (with some extensions) to many AI representation and reasoning tasks.
[Enderton 1972, Pospesel 1976] are two books on logic—the first rather mathematical, and the second more informal. For a quite readable overview, which includes illustrative computer programs, see [Barwise & Etchemendy 1993].
Exercises
15.1 Give a model of the following formulas whose domain is the integers:
2. Clear(B) ∧ Clear(C) ⊃ On(A, F1)
15.2 Show that the wff (∃x)On(x, A) ⊃ ¬Clear(A) has value True in each of the interpretations suggested by the configurations of Figure 15.2.
15.3 The following wffs have an obvious “blocks-world” interpretation:
(∀x)[Clear(x) ⊃ ¬(∃y) 0n (y, x)]
Invent another interpretation (objects, relations, and a mapping) that satisfies the conjunction of these wffs.
15.4 For each of the following predicate-calculus expressions, say whether it can be a syntactically legal sentence (wff), and, if not, why not. For each legal sentence, say whether it is valid (necessarily true), unsatisfiable (necessarily false), or contingent (dependent on the interpretation). For each contingent sentence, give an interpretation for the symbols that makes the sentence true.
1. Won(Election, Clinton) ∧ Won(Election, Bush)
3. (∀ s) [Attends(s, (CS221 ∨ CS157))]
4. (∀ x) [Set(x) ⊃ (Subset(x, x) ∨ ¬Subset(x, x))]
5. (∀ x) [P(x) ∨ Q(x)] ⊃¬(∃ x) [(¬P(x) ∨ Q(x))]
7. (∃ x y z) [Equal(add(x, y), add(x, y, z))]
8. P (Igor) ∧ Q (Bertha) ∧ (∀ x) [-(P (x) ∨ Q(x))]
15.5 A steeple-building robot looks for two blocks that are clear and puts one of them on top of the other (if the block being moved can be located as being on some other block or on the floor). Write down a first-order predicate-calculus expression that might be used to determine whether or not there exist two such blocks.
15.6 A robot in grid world can move into a cell if that cell is one of the four adjacent cells and if that cell is free of obstacles. In that case, we say that the cell is available. Also, the grid world has no “tight spaces” (as defined in Chapter 2).
Invent predicate-calculus expressions that can be used to define when a cell is available and to describe the “no-tight-space” condition.
1 The made-up word arity comes from the “ary” suffix in binary (arity = 2), tertiary (arity = 3), and so on.
2 I will sometimes use boldface notation for objects, functions, and relations in the world—as contrasted with typewriter notation for language elements of the predicate calculus—when I want to emphasize the distinction between language elements and what these elements denote.
3 There is a theorem by Löwenheim that states that all consistent sets of predicate-calculus wffs have a model whose domain is the integers [Löwenheim 1915].