15.3 Predicate Calculus

Predicate calculus, often just known as predicate logic, extends propositional calculus in two ways:

  • atoms have structure and can include constants and logical variables

  • quantification of logical variables.

This book follows the syntactic conventions of Prolog, where variables start with an upper-case letter. In mathematics, variables typically are x, y, and z. In Prolog, as in other programming languages, longer names are typically used to make code more readable. The upper case is used to make variables stand out.

The syntax of the predicate calculus extends the syntax of the propositional calculus as follows, where a symbol is a sequence of letters, digits, or an underscore (“_”):

  • A logical variable is a symbol starting with an upper-case letter or with “_”. For example, X, Room, _B4, Raths, and The_big_guy are all variables.

  • A constant is a symbol that starts with a lower-case letter, or is a number constant or a string.

  • A predicate symbol is a symbol that starts with a lower-case letter. Constants and predicate symbols are distinguishable by their context in a knowledge base.

    For example, kim, r123, f, grandfather, and borogroves can be constants or predicate symbols, depending on the context; 725 is a constant.

  • A term is either a variable or a constant.

    For example, X, kim, cs422, mome, or Raths can be terms.

  • An atomic symbol, or simply an atom, is of the form p or p(t1,,tn), where p is a predicate symbol and each ti is a term. Each ti is called an argument to the predicate.

    For example, teaches(sue,cs422), in(kim,r123), father(bill,Y), happy(C), outgrabe(mome,Raths), and sunny can all be atoms. From context in the atom outgrabe(mome,Raths), the symbol outgrabe is a predicate symbol and mome is a constant.

A logical formula is built from the atoms using the connectives of the propositional calculus, and the quantifiers. The following are also logical formula:

  • Xp, where X is a variable, and p is a logical formula (typically containing X), is read “for all X, p”. Variable X is said to be universally quantified.

  • Xp, where X is a variable, and p is a logical formula, is read “there exists an X such that p”. Variable X is said to be existentially quantified.

Example 15.3.

The following are logical formulas:


From context, sam, toves, and mome are constants; grandfather, father, parent, in, part_of, slithy, mimsy, borogroves, and outgrabe are predicate symbols; and G, P, X, Y, Z, and Raths are variables.

The first two formulas may make some intuitive sense, even without an explicitly provided formal specification for the meaning of formulas. However, regardless of the mnemonic names’ suggestiveness, as far as the computer is concerned, the first two formulas have no more meaning than the third. Meaning is provided only by virtue of a semantics.

An expression is ground if it does not contain any variables. For example, teaches(chris,cs322) is ground, but teaches(Prof,Course) is not ground.

The next sections define the semantics. First consider ground expressions and then extend the semantics to include variables.

15.3.1 Semantics of Ground Logical Formulas

The first step in giving the semantics of predicate calculus is to give the semantics for the ground (variable-free) case.

An interpretation is a triple I=D,ϕ,π:

  • D is a non-empty set called the domain. Elements of D are individuals.

  • ϕ is a mapping that assigns to each constant an element of D.

  • π is a mapping that assigns to each n-ary predicate symbol a function from Dn into {true,false}.

ϕ is a function from names into individuals in the world. The constant c is said to denote the individual ϕ(c). Here c is a symbol but ϕ(c) can be anything: a real physical individual such as a person or a virus, an abstract concept such as a course, love, the number 2, or a symbol.

π(p) specifies whether the relation denoted by the n-ary predicate symbol p is true or false for each n-tuple of individuals. If predicate symbol p has no arguments, then π(p) is either true or false. Thus, for predicate symbols with no arguments, this semantics reduces to the semantics of the propositional calculus.

Example 15.4.

Consider the world consisting of three individuals on a table:

 ✂   ✈         ✎  

These are drawn in this way because they are things in the world, not symbols. ✂ is a pair of scissors, ✈ is a model airplane, and ✎ is a pencil.

Suppose the constants in our language are plane, pencil, and model, and predicate symbols are noisy and left_of. Assume noisy is a unary predicate (it takes a single argument) and that left_of is a binary predicate (it takes two arguments).

An example interpretation that represents the individuals on the table is

  • D={,,}.

  • ϕ(plane)=, ϕ(pencil)=, ϕ(model)=.

  • π(noisy): false true false
    π(left_of): , false , true , true , false , false , true , false , false , false

    Because noisy is unary, it takes a singleton individual and has a truth value for each individual.

    Because left_of is a binary predicate, it takes a pair of individuals and is true when the first element of the pair is left of the second element. Thus, for example, π(left_of)(,)=true, because the scissors are to the left of the model; π(left_of)(,)=false, because the pencil is not to the left of itself.

Note how the D is a set of things in the world. The relations are among the individuals in the world, not among the names. As ϕ specifies that plane and model refer to the same individual, exactly the same statements are true about them in this interpretation.

Example 15.5.

Consider the interpretation of Figure 15.1.

D is the set with four elements: the person Kim, room 123, room 023, and the CS building. This is not a set of four symbols, but it is the set containing the actual person, the actual rooms, and the actual building. It is difficult to write down this set and, fortunately, you never really have to. To remember the meaning and to convey the meaning to another person, knowledge base designers typically describe D, ϕ, and π by pointing to the physical individuals, or a depiction of them (as is done in Figure 15.1), or describe the meaning in natural language.

The constants are kim, r123, r023, and cs_building. The mapping ϕ is defined by the gray arcs from each of these constants to an individual in the world in Figure 15.1.

The predicate symbols are person, in, and part_of. The meanings of these are meant to be conveyed in the figure by the arcs from the predicate symbols.

Thus, the person called Kim is in room r123 and is also in the CS building, and these are the only instances of the in relation that are true. Similarly, room r123 and room r023 are part of the CS building, and there are no other part_of relationships that are true in this interpretation.

Each ground term denotes an individual in an interpretation. A constant c denotes in I the individual ϕ(c).

A ground atom is either true or false in an interpretation. Atom p(t1,,tn) is true in I if π(p)(t1,,tn)=true, where ti is the individual denoted by term ti, and is false in I otherwise.

Example 15.6.

The atom in(kim,r123) is true in the interpretation of Example 15.5, because the person denoted by kim is indeed in the room denoted by r123. Similarly, person(kim) is true, as is part_of(r123,cs_building). The atoms in(cs_building,r123) and person(r123) are false in this interpretation.

Logical connectives have the same meaning as in the propositional calculus; see Figure 5.1 for the truth tables for the logical connectives.

15.3.2 Interpreting Variables

To define the semantics of logical formulas with variables, a variable assignment, ρ, is a function from the variables into the domain D. Thus, a variable assignment assigns an element of the domain to each variable. Given interpretation D,ϕ,π and variable assignment ρ, each term denotes an individual in the domain. If the term is a constant, the individual is given by ϕ. If the term is a variable, the individual is given by ρ. Given an interpretation and a variable assignment for all variables, each atom is either true or false, using the same definition as earlier.

The semantics of quantification is as follows:

  • Universally quantified formula Xp is true in an interpretation if p is true for all variable assignments of X to an individual. Thus, a formula is false in an interpretation whenever there is a variable assignment to X under which the formula is false. The formula p is the scope of X.

  • Existentially quantified formula Xp is true in an interpretation if p is true for some variable assignment of X to an individual. The individual that exists can depend on universally quantified variables that Xp is in the scope of. For example, in Y(Xp), the X can depend on Y; for every number Y there is an X such that X=Y+1. In X(Yp), the X cannot depend on Y because X is not in the scope of Y; there does not exist an X such that for every number Y, X=Y+1.

A formula that contains a variable that does not have an enclosing qualification is said to be open, and does not have a truth value, because not all variables have a variable assignment.

Example 15.7.

The formula


is false in the interpretation of Example 15.5, because under the variable assignment with X denoting Kim and Y denoting Room 123, in(X,Y) is true and part_of(X,Y) is false.

The formula


is true in that interpretation, because in(X,Y) is true in all variable assignments where part_of(Z,Y)in(X,Z) is true.

Logical consequence is defined in the same way as it was for propositional calculus in Section 5.1.2: g is a logical consequence of KB, written KBg, if g is true in every model of KB.

Example 15.8.

Suppose the knowledge base KB is the conjunction of the formulas


The interpretation defined in Example 15.5 is a model of KB, because each formula is true in that interpretation.

KBin(kim,r123), because this is stated explicitly in the knowledge base. If every formula in KB is true in an interpretation, then in(kim,r123) must be true in that interpretation.

KB⊧̸in(kim,r023). The interpretation defined in Example 15.5 is a model of KB, in which in(kim,r023) is false.

KB⊧̸part_of(r023,cs_building). Although part_of(r023,cs_building) is true in the interpretation of Example 15.5, there is another model of KB in which part_of(r023,cs_building) is false. In particular, the interpretation which is like the interpretation of Example 15.5, but where


is a model of KB in which part_of(r023,cs_building) is false.

KBin(kim,cs_building). If the formula in KB are true in interpretation I, it must be the case that in(kim,cs_building) is true in I, otherwise, there is an instance of the third formula of KB that is false in I – a contradiction to I being a model of KB.

The Human’s View of Semantics

The formal description of semantics does not tell us why semantics is interesting or how it can be used as a basis to build intelligent systems. The methodology for using semantics for propositional logic programs can be extended to predicate logic:

Step 1

Select the task domain or world to represent. This could be some aspect of the real world, for example, the structure of courses and students at a university or a laboratory environment at a particular point in time, some imaginary world, such as the world of Alice in Wonderland, or the state of the electrical environment if a switch breaks, or an abstract world, for example, the world of money, numbers, and sets. Within this world, let the domain D be the set of all individuals or things that you want to be able to refer to and reason about. Also, select which relations to represent.

Step 2

Associate constants in the language with individuals in the world that you want to name. For each element of D you want to refer to by name, assign a constant in the language. For example, you may select the name “kim” to denote a particular professor and the name “cs322” for a particular introductory AI course. Each of these names denotes the corresponding individual in the world.

Step 3

For each relation that you may want to represent, associate a predicate symbol in the language. Each n-ary predicate symbol denotes a function from Dn into {true,false}, which specifies the subset of Dn for which the relation is true. For example, the predicate symbol “teaches” of two arguments (a teacher and a course) may correspond to the binary relation that is true when the individual denoted by the first argument teaches the course denoted by the second argument.

The association of symbols with their meanings forms an intended interpretation. This specifies what the symbols are intended to mean.

Step 4

Write formulas that are true in the intended interpretation. This is often called axiomatizing the domain, where the given formulas are the axioms of the domain, or the knowledge base. For example, if the person denoted by the symbol kim teaches the course denoted by the symbol cs322, you can assert the formula teaches(kim,cs322) as being true in the intended interpretation. Not everything that is true needs to be written down; there is no need to state what is implied by other axioms.

Step 5

Ask queries about the intended interpretation. The system gives answers that you can interpret using the meaning assigned to the symbols.

Following this methodology, the knowledge base designer does not actually tell the computer anything until step 4. The first three steps are carried out in the head of the designer. Of course, the designer should document the denotations to make their knowledge base understandable to other people, so that they remember each symbol’s denotation, and so that they can check the truth of the formulas.

The world itself does not prescribe what the individuals are.

Example 15.9.

In one conceptualization of a domain, pink may be a predicate symbol of one argument that is true when the individual denoted by that argument is pink. In another conceptualization, pink may be an individual that is the color pink, and it may be used as the second argument to a binary predicate color, which says that the individual denoted by the first argument has the color denoted by the second argument. Alternatively, someone may want to describe the world at a level of detail where various shades of red are not distinguished, and so the color pink would not be included. Someone else may describe the world in more detail, and decide that pink is too general a term, and use the terms coral and salmon.

When the individuals in the domain are real physical things, it is usually difficult to give the denotation without physically pointing at the individual. When the individual is an abstract individual – for example, a university course or the concept of love – it is virtually impossible to write the denotation. However, this does not prevent the system from representing and reasoning about such concepts.