13.3.1 Semantics of Ground Datalog

The first step in giving the semantics of Datalog 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 true or false. Thus, for predicate symbols with no arguments, this semantics reduces to the semantics of propositional definite clauses.

Example 13.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 telephone, and ✎ is a pencil.

Suppose the constants in our language are $p h o n e$ , $p e n c i l$ , and $t e l e p h o n e$ . We have the predicate symbols $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 pzd}},\mbox{\mbox{\Large\char pzd}},\mbox{\mbox{\char pzd% }}\}$ .
•

$\phi(phone)=\mbox{\mbox{\Large\char pzd}}$ , $\phi(pencil)=\mbox{\mbox{\char pzd}}$ , $\phi(telephone)=\mbox{\mbox{\Large\char pzd}}$ .
•

$\pi(noisy)$ : $\langle\mbox{\mbox{\char pzd}}\rangle$ false $\langle\mbox{\mbox{\Large\char pzd}}\rangle$ true $\langle\mbox{\mbox{\char pzd}}\rangle$ false
$\pi(left\_of)$ : $\langle\mbox{\mbox{\char pzd}},\mbox{\mbox{\char pzd}}\rangle$ false $\langle\mbox{\mbox{\char pzd}},\mbox{\mbox{\Large\char pzd}}\rangle$ true $\langle\mbox{\mbox{\char pzd}},\mbox{\mbox{\char pzd}}\rangle$ true $\langle\mbox{\mbox{\Large\char pzd}},\mbox{\mbox{\char pzd}}\rangle$ false $\langle\mbox{\mbox{\Large\char pzd}},\mbox{\mbox{\Large\char pzd}}\rangle$ false $\langle\mbox{\mbox{\Large\char pzd}},\mbox{\mbox{\char pzd}}\rangle$ true $\langle\mbox{\mbox{\char pzd}},\mbox{\mbox{\char pzd}}\rangle$ false $\langle\mbox{\mbox{\char pzd}},\mbox{\mbox{\Large\char pzd}}\rangle$ false $\langle\mbox{\mbox{\char pzd}},\mbox{\mbox{\char pzd}}\rangle$ false

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 pzd}},\mbox{\mbox{\Large\char pzd}}% \rangle)=true$ , because the scissors are to the left of the telephone; $\pi(left\_of)(\langle\mbox{\mbox{\char pzd}},\mbox{\mbox{\char pzd}}\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 h o n e$ and $t e l e p h o n e$ refer to the same individual, exactly the same statements are true about them in this interpretation.

Example 13.5.

Consider the interpretation of Figure 13.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 13.1) and 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 13.1.

The predicate symbols are $p e r s o n$ , $i n$ , and $part\_of$ . The meaning of these are meant to be conveyed in the figure by the arcs from the predicate symbols.

Thus, the person called Kim is in the 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 13.6.

The atom $in(kim,r123)$ is true in the interpretation of Example 13.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, models and logical consequences have the same meaning as in the propositional calculus:

•

A ground clause is false in an interpretation if the head is false and the body is true (or is empty); otherwise, the clause is true in the interpretation.
•

A model of a knowledge base $K B$ is an interpretation in which all the clauses in $K B$ are true.
•

If $K B$ is a knowledge base and $g$ is a proposition, $g$ is a logical consequence of $K B$ , written $KB\models g$ , if $g$ is true in every model of $K B$ . Thus $KB\not\models g$ , meaning $g$ is not a logical consequence of $K B$ , when there is a model of $K B$ in which $g$ is false.

Artificial Intelligence 2E

13.3.1 Semantics of Ground Datalog

Example 13.4.

Example 13.5.

Example 13.6.

Artificial
Intelligence 2E