15 Individuals and Relations 15.2 Symbols and Semantics 15.4 Datalog: A Relational Rule Language

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$ , $R o o m$ , $\_B4$ , $R a t h s$ , 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, $k i m$ , $r123$ , $f$ , $g r a n d f a t h e r$ , and $b o r o g r o v e s$ 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$ , $k i m$ , $cs422$ , $m o m e$ , or $R a t h s$ can be terms.
•

An atomic symbol, or simply an atom, is of the form $p$ or $p(t_{1},\ldots,t_{n})$ , where $p$ is a predicate symbol and each $t_{i}$ is a term. Each $t_{i}$ is called an argument to the predicate.

For example, $teaches(sue,cs422)$ , $in(kim,r123)$ , $father(bill,Y)$ , $happy(C)$ , $outgrabe(mome,Raths)$ , and $s u n n y$ can all be atoms. From context in the atom $outgrabe(mome,Raths)$ , the symbol $o u t g r a b e$ is a predicate symbol and $m o m e$ 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:

•

$\forall X~{}p$ , 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.
•

$\exists X~{}p$ , 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:

\forall G~{}(grandfather(sam,G)\leftarrow\mbox{}\exists P~{}(father(sam,P)% \wedge\mbox{}parent(P,G))).

in(X,Y)\leftarrow\mbox{}part\_of(Z,Y)\wedge\mbox{}in(X,Z).

slithy(toves)\leftarrow\mbox{}\forall Raths~{}(mimsy\wedge\mbox{}borogroves% \wedge\mbox{}outgrabe(mome,Raths)).

From context, $s a m$ , $t o v e s$ , and $m o m e$ are constants; $g r a n d f a t h e r$ , $f a t h e r$ , $p a r e n t$ , $i n$ , $part\_of$ , $s l i t h y$ , $m i m s y$ , $b o r o g r o v e s$ , and $o u t g r a b e$ are predicate symbols; and $G$ , $P$ , $X$ , $Y$ , $Z$ , and $R a t h s$ 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=\left<D,\phi,\pi\right>$ :

•

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

$\phi$ is a mapping that assigns to each constant an element of $D$ .
•

$\pi$ is a mapping that assigns to each n-ary predicate symbol a function from $D^{n}$ into $\{\mbox{$true$},\mbox{$false$}\}$ .

$\phi$ is a function from names into individuals in the world. The constant $c$ is said to denote the individual $\phi(c)$ . Here $c$ is a symbol but $\phi(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.

$\pi(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 $\pi(p)$ is either $t r u e$ or $f a l s e$ . 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 $p l a n e$ , $p e n c i l$ , and $m o d e l$ , and predicate symbols are $n o i s y$ and $left\_of$ . Assume $n o i s y$ 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=\{\mbox{\mbox{\char 34}},\mbox{\mbox{\char 40}},\mbox{\mbox{\char 46}}\}$ .
•

$\phi(plane)=\mbox{\mbox{\char 40}}$ , $\phi(pencil)=\mbox{\mbox{\char 46}}$ , $\phi(model)=\mbox{\mbox{\char 40}}$ .
•

$\pi(noisy)$ : $\langle\mbox{\mbox{\char 34}}\rangle$ $f a l s e$ $\langle\mbox{\mbox{\char 40}}\rangle$ $t r u e$ $\langle\mbox{\mbox{\char 46}}\rangle$ $f a l s e$
$\pi(left\_of)$ : $\langle\mbox{\mbox{\char 34}},\mbox{\mbox{\char 34}}\rangle$ $f a l s e$ $\langle\mbox{\mbox{\char 34}},\mbox{\mbox{\char 40}}\rangle$ $t r u e$ $\langle\mbox{\mbox{\char 34}},\mbox{\mbox{\char 46}}\rangle$ $t r u e$ $\langle\mbox{\mbox{\char 40}},\mbox{\mbox{\char 34}}\rangle$ $f a l s e$ $\langle\mbox{\mbox{\char 40}},\mbox{\mbox{\char 40}}\rangle$ $f a l s e$ $\langle\mbox{\mbox{\char 40}},\mbox{\mbox{\char 46}}\rangle$ $t r u e$ $\langle\mbox{\mbox{\char 46}},\mbox{\mbox{\char 34}}\rangle$ $f a l s e$ $\langle\mbox{\mbox{\char 46}},\mbox{\mbox{\char 40}}\rangle$ $f a l s e$ $\langle\mbox{\mbox{\char 46}},\mbox{\mbox{\char 46}}\rangle$ $f a l s e$

Because $n o i s y$ 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, $\pi(left\_of)(\langle\mbox{\mbox{\char 34}},\mbox{\mbox{\char 40}}\rangle)=true$ , because the scissors are to the left of the model; $\pi(left\_of)(\langle\mbox{\mbox{\char 46}},\mbox{\mbox{\char 46}}\rangle)=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 $\phi$ specifies that $p l a n e$ and $m o d e l$ 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$ , $\phi$ , and $\pi$ 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 $k i m$ , $r123$ , $r023$ , and $cs\_building$ . The mapping $\phi$ 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 $p e r s o n$ , $i n$ , 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 $i n$ 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 $\phi(c)$ .

A ground atom is either true or false in an interpretation. Atom $p(t_{1},\ldots,t_{n})$ is true in $I$ if $\pi(p)(\left<t_{1}^{\prime},\ldots,t_{n}^{\prime}\right>)=\mbox{$true$}$ , where $t_{i}^{\prime}$ is the individual denoted by term $t_{i}$ , 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 $k i m$ 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, $\rho$ , 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 $\left<D,\phi,\pi\right>$ and variable assignment $\rho$ , each term denotes an individual in the domain. If the term is a constant, the individual is given by $\phi$ . If the term is a variable, the individual is given by $\rho$ . 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 $\forall X~{}p$ 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 $\exists X~{}p$ 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 $\exists X~{}p$ is in the scope of. For example, in $\forall Y~{}(\exists X~{}p)$ , the $X$ can depend on $Y$ ; for every number $Y$ there is an $X$ such that $X=Y+1$ . In $\exists X~{}(\forall Y~{}p)$ , 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

\forall X~{}\forall Y~{}~{}part\_of(X,Y)\leftarrow\mbox{}in(X,Y).

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

\forall X~{}\forall Y~{}\forall Z~{}~{}in(X,Y)\leftarrow\mbox{}part\_of(Z,Y)% \wedge\mbox{}in(X,Z).

is true in that interpretation, because $in(X,Y)$ is true in all variable assignments where $part\_of(Z,Y)\wedge\mbox{}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 $K B$ , written $KB\models g$ , if $g$ is true in every model of $K B$ .

Example 15.8.

Suppose the knowledge base $K B$ is the conjunction of the formulas

in(kim,r123).

part\_of(r123,cs\_building).

\forall X~{}\forall Y\forall Z~{}~{}in(X,Y)\leftarrow\mbox{}part\_of(Z,Y)% \wedge\mbox{}in(X,Z).

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

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

$KB\not\models in(kim,r023)$ . The interpretation defined in Example 15.5 is a model of $K B$ , in which $in(kim,r023)$ is false.

$KB\not\models 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 $K B$ in which $part\_of(r023,cs\_building)$ is false. In particular, the interpretation which is like the interpretation of Example 15.5, but where

\pi(part\_of)(\left<\phi(r023),\phi(cs\_building)\right>)=\mbox{$false$}

is a model of $K B$ in which $part\_of(r023,cs\_building)$ is false.

$KB\models in(kim,cs\_building)$ . If the formula in $K B$ 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 $K B$ that is false in $I$ – a contradiction to $I$ being a model of $K B$ .

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 “ $k i m$ ” 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 $D^{n}$ into $\{\mbox{$true$},\mbox{$false$}\}$ , which specifies the subset of $D^{n}$ for which the relation is true. For example, the predicate symbol “ $t e a c h e s$ ” 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 $k i m$ 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, $p i n k$ may be a predicate symbol of one argument that is true when the individual denoted by that argument is pink. In another conceptualization, $p i n k$ may be an individual that is the color pink, and it may be used as the second argument to a binary predicate $c o l o r$ , 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 $r e d$ are not distinguished, and so the color $p i n k$ would not be included. Someone else may describe the world in more detail, and decide that $p i n k$ is too general a term, and use the terms $c o r a l$ and $s a l m o n$ .

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.

Artificial Intelligence 3E