Consider the kinship dataset shown below. The situation here is the same as that described in the preceding chapter. Art is the parent of Bob and Bea. Bob is the parent of Cal and Cam. Bea is the parent of Coe and Cory.
Suppose now that we wanted to express information about the grandparent relation as well as the parent relation. As illustrated in the preceding chapter, we can do this by adding facts to our dataset. In this case, we would add the facts shown below. Art is the grandparent of Cal and Cam and Coe and Cory.
One thing to notice about this approach to recording grandparent information is that it is redundant. The information about parentage completely determines the information about grandparenthood.
Rules provide us with a way to express these relationships in general. Once we have these rules, we can avoid the redundant data, safe in the knowledge that we can recompute it as necessary. In this case, rather than adding facts to our dataset, we can write the following rule defining the grandparent relation in terms of the parent relation. In what follows, we look at the details of our rule language.
In Basic Logic Programming, the states of the application environment are modeled as a dataset; additional relations are defined in the form of rules; and automated reasoning tools are used to derive conclusions from these facts and rules.
Doing things this way has multiple advantages over storing all information in the form of datasets and nothing else. First of all, there is economy. If relations are defined in terms of rules, we do not need to store as many facts in our datasets. Second, there is less chance of things getting out of sync, e.g. if we change the parent relation and forget to change the grandparent relation. Third, view definitions work for any number of objects; they even work for applications with infinitely many objects (e.g. the integers) without requiring infinite storage.
In this chapter, we introduce the syntax and semantics of rules. We then look at some examples of using rules to define views of datasets. After this, we describe the notions of safety and stratification - two properties that rule sets need to possess in order to avoid unpleasant complications. We close with a discussion of special relations and operators that extend our language and make it easier to write certain types of definitions.
3.2 Logic Program Syntax
The language of logic programs includes the language of databases but provides some additional features that make it more expressive.
One key difference is the inclusion of a new type of symbol, called a variable. Variables allow us to state relationships among objects without explicitly naming those objects. In what follows, we use individual capital letters as variables, e.g. X, Y, Z.
In the context of logic programs, a term is defined as an object constant, a variable, or a functional term, i.e. an expression consisting of an n-ary function constant and n simpler terms.
An atom in a logic program is analogous to a datum in a database except that the constituent terms may include variables.
A literal is either an atom or a negation of an atom (i.e. an expression stating that the atom is false). A simple atom is called a positive literal, The negation of an atom is called a negative literal. In what follows, we write negative literals using the negation sign ~. For example, if p(a,b) is an atom, then ~p(a,b) denotes the negation of this atom.
A rule is an expression consisting of a distinguished atom, called the head and a conjunction of zero or more literals, called the body. The literals in the body are called subgoals. In what follows, we write rules as in the example shown below. Here, r(a,b) is the head, p(a,b) & ~q(b) is the body; and p(a,b) and ~q(b) are subgoals.
Semantically, a rule is something like a reverse implication. It is a statement that the head of the rule is true whenever the subgoals are true. For example, the rule above states that r(a,b) is true if p(a,b) is true and q(b) is not true.
The expressive power of rules is greatly enhanced through the use of variables. Consider, for example, the rule shown below. This is a more general version of the rule shown above. Instead of applying to just the specific objects a and b it applies to all objects. In this case, the rule states that r is true of any object X and any object Y if p is true of X and Y and q is not true of Y.
A static logic program is a set of facts and rules of the form just described. Note that, for the purposes or analysis, it is sometimes useful to think about infinite sets of rules. However, we cannot write down such sets; so, in what follows, we restrict our attention to finite logic programs.
The principle use of rules is to define new relations in terms of existing relations. The new relations defined in this way are often called view relations (or simply views) to distinguish them from base relations, which are defined by explicit enumeration of instances.
Unfortunately, the language of rules, as defined so far, allows for logic programs with some unpleasant properties. To avoid programs of this sort, it is common in basic logic programming to add a couple of restrictions that together eliminate these problems.
The first restriction is safety. A rule in a logic program is safe if and only if every variable that appears in the head or in any negative literal in the body also appears in at least one positive literal in the body. A logic program is safe if and only if every rule in the program is safe.
The rule shown below is safe. Every variable in the head and every variable in the negative subgoal appears in a positive subgoal in the body. Note that it is okay for the body to contain variables that do not appear in the head.
By contrast, the two rules shown below are not safe. The first rule is not safe because the variable Z appears in the head but does not appear in any positive subgoal. The second rule is not safe because the variable Z appears in a negative subgoal but not in any positive subgoal.
To see why safety is matters in the case of the first rule, suppose we had a database in which p(a,b) is true. Then, the body of the first rule is satisfied if we let X be a and Y be b. In this case, we can conclude that every corresponding instance of the head is true. But what should we substitute for Z? Intuitively, we could put anything there; but there could be infinitely many possibilities. For example, we could write any number there. While this is conceptually okay, it is practically problematic.
To see why safety matters in the second rule, suppose we had a database with just two facts, viz. p(a,b) and q(b,c). In this case, if we let X be a and Y be b and Z be anything other than c, then both subgoals true, and we can conclude t(a,b).
The main problem with this is that many people incorrectly interpret that negation as meaning there is no Z for which q(Y,Z) is true, whereas the correct reading is that q(Y,Z) needs to be false for just one binding of Z. As we will see in our examples below, there is a simple way of expressing this other meaning without writing unsafe rules.
In logic programming, these problems are avoided by requiring all rules to be safe. While this does restrict what one can say, the good news is that it is usually possible to ensure safety by adding additional subgoals to rules to ensure that the restrictions are satisfied.
The second restriction is called stratified negation. As explained below, it is essential in order to avoid ambiguities. Unfortunately, it is a little more difficult to understand than safety, and a little patience is required to understand the condition and why it is important.
We say that a logic program is stratified with respect to negation if and only if its rules can be partitioned into strata in such a way that, for every rule, (1) all rules defining relations that appear in positive goals of that rule appear in the same stratum as that rule or in some lower stratum and (2) the rules defining relations that appear in negative subgoals of that rule occur in some lower stratum (not the same stratum).
As an example, assume we have a unary relation p that is true of all of the objects in some application area, and assume that q is an arbitrary binary relation. Now, consider the logic program shown below. The first two rules define r to be the transitive closure of q. The third rule defines s to be the complement of the transitive closure.
This is a complicated program, yet it is easy to see that it is stratified with respect to negation. The first two rules contain no negations at all, and so we can group them together in our lowest stratum. The third rule has a negated subgoal containing a relation defined in our lowest stratum, and so we put it into a stratum above this one, as shown below. This program satisfies the conditions of our definition and hence it is stratified with respect to negation.
By comparison, consider the following logic program. Here, the relation s is defined in terms of p and the negation of r, and the relation r is defined in terms of p and the negation of s.
There is no way of dividing the rules of this program into strata in a way that satisfies the definition above. Hence, the program is not stratified with respect to negation.
The problem with unstratified logic programs is that there is a potential ambiguity. As an example, consider the rules above and assume that our program also included the facts p(a), p(b), q(a,b), and q(b,a). From these facts, we can conclude r(a,b) and r(b,a) are both true. So far, so good. But what can we say about s? If we take s(a,b) to be true and s(b,a) to be false, then the second rule is satisfied. If we take s(a,b) to be false and s(b,a) to be true, then the second rule is again satisfied. The upshot is that there is ambiguity about s. By concentrating exclusively on programs that are stratified with respect to negation, we avoid such ambiguities.
It is common in logic programming to require that all logic programs be stratified with respect to negation. The restriction is easy to satisfy in most applications; and, by obeying the restriction, we ensure that our logic programs produce unambiguous answers for all questions.
3.5 Logic Program Semantics
The extension of a logic program is the set of all facts that can be "deduced" on the basis of the rules in the program. The precise definition is best understood by first looking at the case of logic programs without negation and then extending that definition to deal with programs including negation.
Suppose we have a logic program without negations. In this case, constructing the resulting dataset is easy. We initialize our dataset to the set of all ground atoms in the program. We then look at the rules in the program. If there is an instance of a rule whose body is satisfied by the atoms in our dataset, then we add the corresponding instance of the head to the dataset. This process continues until it reaches a fixpoint, i.e. there are no additional ground atoms added by any rule.
To illustrate this definition, let's start by describing a small directed graph. In the sentences below, we use the edge relation to designate the arcs of the graph.
Now, let's augment this program with some rules defining various relations on the nodes in our graph. Here, the relation p is true of all nodes with an outgoing arc. The relation q is true of two nodes if there is an edge from the first to the second or from the second to the first. The relation r is true of two nodes if there is an edge from the first to the second and an edge from the second to the first. The relation s is the transitive closure of the edge relation.
We start the computation by initializing our dataset to the edge facts listed above.
Looking at the p rule and matching its subgoals to the data in our dataset in all possible ways, we see that we can add the following data. In this case, every node in our graph has an outgoing edge, so there is one p fact for each node.
Looking at the q rules and matching their subgoals to the data in our dataset in all possible ways, we see that we can add the following data. In this case, we end up with the symmetric closure of the original graph.
Looking at the r rule and matching their subgoals to the data in our dataset in all possible ways, we see that we can add the following data.
Finally, looking at the first rule for s and matching its subgoals to the data in our dataset in all possible ways, we see that we can add the following data.
With these additions, we can use the second rule to derive the following additional data.
However, we are not done. Using the s rule again, we can derive the following fact.
At this point, none of the rules when applied to this collection of data produces any results that are not already in the set, and so the process terminates. The resulting collection of 25 facts is the extension of this program.
That completes our treatment of the case of logic programs without negation. Now, suppose we have a program with some rules containing negated subgoals. Imagine, for example, that our program also contained the rule shown below. The relation t is the complement of the transitive closure of the edge relation.
Since this rule contains a negated relation, it would appear at a higher stratum than the s relation, and so we would not compute the conclusions until after we were done with s. In this case, there are sixteen ways to satisfy the first two subgoals of our rule; and, as we have just seen, 9 of them satisfy the s relation, so the remaining seven facts satisfy the t relation.
Note that, in the presence of rules with negated subgoals, it is sometimes possible to stratify the rules in more than one way. The good news here is that does not cause any problems. So long as a program is stratified with respect to negation, the definition just given produces the same dataset no matter which stratification one uses. Consequently, there is just one extension for any safe, stratified logic program.
3.6 Example - Kinship
To illustrate the use of rules in defining views, consider once again the world of interpersonal relations. Starting with the base relations, we can define various interesting view relations.
For example, the first sentence defines the father relation in terms of parent and male. The second sentence defines mother in terms of parent and female.
The rule below defines the grandparent relation in terms of the parent relation. A person X is the grandparent of a person Z if X is the parent of a person Y and Y is the parent of Z. The variable Y here is a thread variable that connects the first subgoal to the second but does not itself appear in the head of the rule.
Note that the same relation can appear in the head of more than one rule. For example, the person relation is true of a person Y if there is an X such that X is the parent of Y or if Y is the parent of some person Z. Note that in this case the conditions are disjunctive (at least one must be true), whereas the conditions in the grandfather case are conjunctive (both must be true).
A person X is an ancestor of a person Z if X is the parent of Z or if there is a person Y such that X is an ancestor of and Y is an ancestor of Z. This example shows that is possible for a relation to appear in its own definition. (See below for a discussion of stratification for a restriction on this capability.)
A childless person is one who has no children. We can define the property of being childless with the rules shown below. The first rule states that a person X is childless if X is a person and it is not the case that X is a parent. The second rule says that isparent is true of X if X is the parent of some person Y.
Note the use of the helper relation isparent here. It is tempting to write the childless rule as childless(X) :- person(X) & ~parent(X,Y). However, this would be wrong. This would define X to be childless if X is a person and there is some Y such that X is ~parent(X,Y) is true. But we really want to say that ~parent(X,Y) holds for all Y. Defining isparent and using its negation in the definition of childless allows us to express this universal quantification.
3.7 Example - Blocks World
The Blocks World is a popular application area for illustrating ideas in the field of Artificial Intelligence. A typical Blocks World scene is shown in Figure 1.
Most people looking at this figure interpret it as a configuration of five toy blocks. Some people conceptualize the table on which the blocks are resting as an object as well; but, for simplicity, we ignore it here.
In order to describe this scene, we adopt a vocabulary with five object constants, as shown below, with one object constant for each of the five blocks in the scene. The intent here is for each of these object constants to represent the block marked with the corresponding capital letter in the scene.
In a spatial conceptualization of the Blocks World, there are numerous meaningful relations. For example, it makes sense to think about the relation that holds between two blocks if and only if one is resting on the other. In what follows, we use the relation constant on to refer to this relation. We might also think about the relation that holds between two blocks if and only if one is anywhere above the other, i.e. the first is resting on the second or is resting on a block that is resting on the second, and so forth. In what follows, we use the relation constant above to talk about this relation. There is the relation that holds of three blocks that are stacked one on top of the other. We use the relation constant stack as a name for this relation. We use the relation constant block to state that an object is a block. We use cluttered to denote the relation that holds of a block if and only if there is a block on top of it, and we use the relation constant clear to denote the relation that holds of a block if and only if there is nothing on top of it. We use the relation constant supported to denote the relation that holds of a block if and only if that block is resting on another block, and we use the relation constant table to denote the relation that holds of a block if and only if that block is resting on the table. The set of relation constants corresponding to this conceptualization is shown below.
The arities of these relation constants are determined by their intended use. Since on is intended to denote a relation between two blocks, it has arity 2. Similarly, above has arity 2. The stack relation constant has arity 3. Relation constants cluttered and clear and supported and table each have arity 1.
Given this vocabulary, we can describe the scene in Figure 1 by writing ground atomic sentences that state which relations hold of which objects or groups of objects. Let's start with block. There are five blocks in this case, named a, b, c, d, and e.
Some of these blocks are on top of each other, and some are not. The following sentences capture the relationships in Figure 1.
We can do the same for the other relations. However, there is an easier way. Each of the remaining relations can be defined in terms of block and on. These definitions together with our facts about the block and on relations logically entail every other ground relational sentence or its negation. Hence, given these definitions, we do not need to write out any additional data.
A block satisfies the cluttered relation if and only if there is a block resting on it. A block satisfies the clear relation if and only if there is nothing on it.
A block satisfies the supported relation if and only if it is resting on some block. A block satisfies the table relation if and only if it is not resting on some block.
Three blocks satisfy the stack relation if and only if the first is on the second and the second is on the third.
The above relation is a bit tricky to define correctly. One block is above another block if and only if the first block is on the second block or it it is on another block that is above the second block. Given a complete definition for the on relation, these two axioms determine a unique above relation.
One advantage to defining relations in terms of other relations is economy. If we record on information for every object and encode the relationship between the on relation and these other relations, there is no need to record any ground relational sentences for those relations.
Another advantage is that these general sentences apply to Blocks World scenes other than the one pictured here. It is possible to create a Blocks World scene in which none of the on sentences we have listed is true, but these general definitions are still correct.
3.8 Example - Simple Arithmetic
Simple Arithmetic is that branch of mathematics having to do with the non-negative integers and the operations of addition, multiplication, and comparison.
Simple arithmetic is more complicated than our previous examples in that we have infinitely many objects to consider, viz. the integers 0, 1, 2, 3, ... Since there are infinitely many such numbers, we need infinitely many terms to describe them in our language.
One way to get infinitely many terms is by expanding our vocabulary to include infinitely many object constants. Unfortunately, this makes the job of axiomatizing arithmetic impossible, as we would have to write out infinitely many sentences.
Fortunately, there is a better way. In particular, we can represent numbers using a single object constant (e.g. 0) and a single unary function constant (e.g. s). In this approach, we represent the number 0 with the object constant 0, and we represent every other natural number n by applying the function constant s exactly n times. For example, in this encoding, s(0) represents 1; s(s(0)) represents 2; s(s(s(0))) represents 3; and so forth. With this encoding, we automatically get an infinite universe of terms, and we can write axioms defining addition and multiplication as simple variations on the axioms of Modular Arithmetic.
Unfortunately, even with this representation, axiomatizing Arithmetic is more challenging than axiomatizing our previous examples. We cannot just write out ground relational sentences to characterize our relations, because there are infinitely many cases to consider. For Simple Arithmetic, we must rely on logical sentences and quantified sentences, not just because they are more economical but because they are the only way we can characterize our relations in finite space.
Let's look at the number relation first. The axioms shown here define the number relation in terms of 0 and s.
The next holds of any natural number and the number that follows it. For example, we have next(0,s(0)) and next(s(0)s(s(0))) and so forth. We can define next in general as shown below.
Once we have number and next, we can define the usual arithmetic functions and relations. For example, the following sentences define the plus relation. Adding 0 to any number results in that number. If adding a number x to a number y produces a number z, then adding the successor of x to y produces the successor of z.
Using next, we can define the "less than" relation in an analogous manner. A number x is less than a number z if the next relation holds of x and z or if there is a number y such that y is the number after x and y is less than z.
Before we leave our discussion of arithmetic, it is instructive to look at the concept of Diophantine equations. A polynomial equation is a sentence composed using only addition, multiplication, and exponentiation with fixed exponents (that is numbers not variables). For example, the expression shown below in traditional math notation is a polynomial equation.
A natural Diophantine equation is a polynomial equation in which the variables are restricted to the non-negative integers. For example, the polynomial equation here is also a Diophantine equation and happens to have a solution in the non-negative numbers, viz. x=4 and y=8 and z=8.
Diophantine equations can be readily expressed as sentences in Simple Arithmetic. For example, we can represent the Diophantine equation above with the rule shown below.
This is a little messy, but it is doable. And we can always clean things up by adding a little syntactic sugar to our notation to make it look like traditional math notation.
3.9 Example - Linked Lists
A list is a finite sequence of objects. Lists can be flat, e.g. [a, b, c]. Lists can also be nested within other lists, e.g. [a, [b, c], d].
A linked list is a way of representing nested lists of variable length and depth. Each element is represented by a cell containing a value and a pointer to the remainder of the list. Our goal in this example is to formalize linked lists and define some useful relations.
To talk about lists of arbitrary length and depth, we use the binary function constant cons, and we use the object constant nil to refer to the empty list. In particular, a term of the form cons(τ1, τ2) designates a sequence in which τ1 denotes the first element and τ2 denotes the rest of the list. With this function constant, we can encode the list [a, b, c] as follows.
The advantage of this representation is that it allows us to describe functions and relations on lists without regard to length or depth.
As an example, consider the definition of the binary relation member, which holds of an object and a list if the object is a top-level member of the list. Using the function constant cons, we can characterize the member relation as shown below. Obviously, an object is a member of a list if it is the first element; however, it is also a member if it is member of the rest of the list.
We can also define relations that depend on the structure of the elements of a list.
For example, the among relation is true of an object and a list if the object is a member of the list, if it is a member of a list that is itself a member of the list, and so on.
In similar fashion, we can define functions to manipulate lists in different ways. For example, the following axioms define a relation called append. The value of append (its last argument) is a list consisting of the elements in the list supplied as its first argument followed by the elements in the list supplied as its second. For example, we would have append(cons(a,nil), cons(b, cons(c, nil)), cons(a, cons(b, cons(c, nil)))). And, of course, we need negative axioms as well (omitted here).
Lists are an extremely versatile representational device, and the reader is encouraged to become as familiar as possible with the techniques of writing definitions for functions and relations on lists. As is true of many tasks, practice is the best approach to gaining skill.
3.10 Example - Natural Language
Pseudo English is a formal language that is intended to approximate the syntax of the English language. One way to define the syntax of Pseudo English is to write grammatical rules in Backus Naur Form (BNF). The rules shown below illustrate this approach for a small subset of Pseudo English. A sentence is a noun phrase followed by a verb phrase. A noun phrase is either a noun or two nouns separated by the word and. A verb phrase is a verb followed by a noun phrase. A noun is either the word mary or the word pat or the word quincy. A verb is either like or likes.
Alternatively, we can use rules to formalize the syntax of Pseudo English. The sentences shown below express the grammar described in the BNF rules above. (We have dropped the universal quantifiers here to make the rules a little more readable.) Here, we are using the append relation defined in the section of lists.
Using these sentences, we can test whether a given sequence of words is a syntactically legal sentence in Pseudo English and we can use our logical entailment procedures to enumerate syntactically legal sentences, like those shown below.
One weakness of our BNF and the corresponding axiomatization is that there is no concern for agreement in number between subjects and verbs. Hence, with these rules, we can get the following expressions, which in Natural English are ungrammatical.
Fortunately, we can fix this problem by elaborating our rules just a bit. In particular, we add an argument to some of our relations to indicate whether the expression is singular or plural. We then use this to block sequences of words where the numbers do not agree.
With these rules, the syntactically correct sentences shown above are still guaranteed to be sentences, but the ungrammatical sequences are blocked. Other grammatical features can be formalized in similar fashion, e.g. gender agreement in pronouns (he versus she), possessive adjectives (his versus her), reflexives (like himself and herself), and so forth.
3.11 Special Relations
In practical logic programming languages, it is common to "build in" commonly used relations. These typically include arithmetic functions (such as +, *, max, min), string functions (such as concatenation), comparison operators (such as < and >), and equality (=).
Special functions are often represented as relations. For example, the the binary addition operator + is often represented by the the ternary relation constant plus. For example, the following rule defines the combined age of two people. The combined age of X and Y is S if the age of X is M and the age of Y is N and S is the result of adding M and N.
In logic programming languages that provide such built-in concepts, there are usually syntactic restrictions on their use. For example, if a rule contains a subgoal with a comparison relation (such as < and >), then every variable that occurs in that subgoal must occur in at least one positive literal in the body and that occurrence must precede the subgoal with the comparison relation. If a rule mentions an arithmetic relation (such as + or *), then any variable that occurs in all but the last position of that subgoal must occur in at least one positive literal in the body and that occurrence must precede the subgoal with the arithmetic relation.
3.12 Aggregate Operators
In practical logic programming languages, it is also common to include pre-defined aggregate operators, such as countofall, avgofall sumofall, and so forth.
Aggregate operators are typically represented as relations with special syntax. For example the following rule defines the number of a person's grandchildren using the countofall relation in this way. N is the number of grandchildren of X if N is the count of all Z such that X is the grandparent of Z.
As with special relations, there are usually syntactic restrictions on on their use. In particular, aggregate subgoals must be safe in that all variables must be included in the first argument or must be used within positive subgoals that precede the aggregate subgoal.
Exercise 3.1: Say whether each of the following expressions is a syntactically legal rule.
Exercise 3.2: Say whether each of the following rules is safe.
Exercise 3.3: Say whether each of the following logic programs is stratified with respect to negation.
Exercise 3.4: Write rules defining the sibling relation in terms of the parent relation. (Hint: you will need the built-in relation distinct to get the definition of sibling correct.)