foundations of computational agents
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
is a non-empty set called the domain. Elements of are individuals.
is a mapping that assigns to each constant an element of .
is a mapping that assigns to each n-ary predicate symbol a function from into .
is a function from names into individuals in the world. The constant is said to denote the individual . Here is a symbol but 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.
specifies whether the relation denoted by the -ary predicate symbol is true or false for each -tuple of individuals. If predicate symbol has no arguments, then is either true or false. Thus, for predicate symbols with no arguments, this semantics reduces to the semantics of propositional definite clauses.
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 , , and . We have the predicate symbols and . Assume is a unary predicate (it takes a single argument) and that is a binary predicate (it takes two arguments).
An example interpretation that represents the individuals on the table is
, , .
: false true true false false true false false false
Because is unary, it takes a singleton individual and has a truth value for each individual.
Because 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, , because the scissors are to the left of the telephone; , because the pencil is not to the left of itself.
Note how the is a set of things in the world. The relations are among the individuals in the world, not among the names. As specifies that and refer to the same individual, exactly the same statements are true about them in this interpretation.
Consider the interpretation of Figure 13.1.
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 , , and 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 , , , and . The mapping 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 , , and . 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 and is also in the CS building, and these are the only instances of the relation that are true. Similarly, room and room are part of the CS building, and there are no other relationships that are true in this interpretation.
Each ground term denotes an individual in an interpretation. A constant denotes in the individual .
A ground atom is either true or false in an interpretation. Atom is true in if , where is the individual denoted by term , and is false in otherwise.
The atom is true in the interpretation of Example 13.5, because the person denoted by is indeed in the room denoted by . Similarly, is true, as is . The atoms and 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 is an interpretation in which all the clauses in are true.
If is a knowledge base and is a proposition, is a logical consequence of , written , if is true in every model of . Thus , meaning is not a logical consequence of , when there is a model of in which is false.