## 3.1 IntroductionConsider 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 SyntaxThe 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 In the context of logic programs, a An A A
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 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 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 ## 3.3 SafetyUnfortunately, 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 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
To see why safety is matters in the case of the first rule, suppose we had a database in which To see why safety matters in the second rule, suppose we had a database with just two facts, viz. The main problem with this is that many people incorrectly interpret that negation as meaning there is no 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. ## 3.4 StratificationThe second restriction is called We say that a logic program is As an example, assume we have a unary relation
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
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 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 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 SemanticsThe 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
Now, let's augment this program with some rules defining various relations on the nodes in our graph. Here, the relation
We start the computation by initializing our dataset to the
Looking at the
Looking at the
Looking at the
Finally, looking at the first rule for
With these additions, we can use the second rule to derive the following additional data.
However, we are not done. Using the
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
Since this rule contains a negated relation, it would appear at a higher stratum than the
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 - KinshipTo 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
The rule below defines the grandparent relation in terms of the parent relation. A person
Note that the same relation can appear in the head of more than one rule. For example, the
A person
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
Note the use of the helper relation ## 3.7 Example - Blocks WorldThe 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. a, b, c, d, e}
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, above, stack, block, cluttered, clear, supported, table}
The arities of these relation constants are determined by their intended use. Since 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
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 A block satisfies the
A block satisfies the
Three blocks satisfy the
The
One advantage to defining relations in terms of other relations is economy. If we record 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 ## 3.8 Example - Simple ArithmeticSimple 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. 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
The
Once we have
Using
Before we leave our discussion of arithmetic, it is instructive to look at the concept of Diophantine equations. A x^{2} + 2y = 4z
A 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 ListsA list is a finite sequence of objects. Lists can be flat, e.g. [ 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(a, cons(b, cons(c, nil)))
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
We can also define relations that depend on the structure of the elements of a list. For example, the
In similar fashion, we can define functions to manipulate lists in different ways. For example, the following axioms define a relation called
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 LanguagePseudo 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
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
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 ( ## 3.11 Special RelationsIn practical logic programming languages, it is common to "build in" commonly used relations. These typically include arithmetic functions (such as Special functions are often represented as relations. For example, the the binary addition operator
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 ## 3.12 Aggregate OperatorsIn practical logic programming languages, it is also common to include pre-defined aggregate operators, such as 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
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. ## ExercisesExercise 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.) |