Introduction to
Logic Programming
What
versus
How
 

Chapter 9 - Examples


9.1 Introduction

In this chapter, we look at some simple examples of view definitions. The examples here are simple in that do not involve constructors or compound terms. In the following chapters, we look at more complicated examples where constructors and compound terms play an essential role.

9.2 Example - Kinship

To illustrate the use of rules in defining views, consider once again the world of kinship relations. Starting with some base relations, we can define various interesting view relations.

For example, the first sentence below defines the father relation in terms of parent and male. The second sentence defines mother in terms of parent and female.

father(X,Y) :- parent(X,Y) & male(X)
mother(X,Y) :- parent(X,Y) & female(X)

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.

grandparent(X,Z) :- parent(X,Y) & parent(Y,Z)

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).

person(X) :- parent(X,Y)
person(Y) :- parent(X,Y)

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 a parent of Y and Y is an ancestor of Z. This example shows that it is possible for a relation to appear in its own definition. (See below for a discussion of stratification for a restriction on this capability.)

ancestor(X,Y) :- parent(X,Y)
ancestor(X,Z) :- parent(X,Y) & ancestor(Y,Z)

A person is a parent if and only if the person has children, and a childless person is one who has no children. We can define these properties with the rules shown below. The first rule says that isparent is true of X if X is the parent of some person Y. The second rule states that a person X is childless if X is a person and it is not the case that X is a parent.

isparent(X) :- parent(X,Y)
childless(X) :- person(X) & ~isparent(X)

Note the use of the relation isparent in defining childless. 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.

9.3 Example - Blocks World

Once again, consider the Blocks World introduced in Chapter 2. The Blocks World scene described earlier is repeated below.

A
B
D
C
E
 
Figure 1 - One state of Blocks World.

As before, we adopt a vocabulary with five symbols to denote the five blocks in the scene - a, b, c, d, and e. We use the unary predicate block to state that an object is a block. We use the binary predicate on to express the fact that one block is directly on another. We use above to say that a block is somewhere above another block. We use the unary predicate cluttered to a block has other blocks on top of it, and we use the unary predicate clear to say that a block has nothing on top of it. We use the unary predicate supported to say that a block is resting on another block, and we use the unary predicate table to say that a block is resting on the table.

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.

block(a)
block(b)
block(c)
block(d)
block(e)

Some of these blocks are on top of each other, and some are not. The following sentences capture the relationships in Figure 1.

on(a,b)
on(b,c)
on(d,e)

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.

cluttered(Y) :- on(X,Y)
clear(X) :- block(X) & ~cluttered(X)

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.

supported(X) :- on(X,Y)
table(X) :- block(X) & ~supported(X)

Three blocks satisfy the stack relation if and only if the first is on the second and the second is on the third.

stack(X,Y,Z) :- on(X,Y) & on(Y,Z)

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 rules determine a unique above relation.

above(X,Y) :- on(X,Y)
above(X,Z) :- on(X,Y) & above(Y,Z)

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.

9.4 Example - Modular Arithmetic

In this example, we show how to define Modular Arithmetic. In Modular Arithmetic, there are only finitely many numbers. For example, in Modular Arithmetic with modulus 4, we have just four integers - 0, 1, 2, 3 - and that's all. Our goal here is to define addition. Admittedly, this is a modest goal; but, once we see how to do this; we can use the same approach to define other arithmetic concepts.

Let's start with the number relation, which is true of every number. We can completely characterize the number relation by writing ground relational sentences, one sentence for each number.

number(0)
number(1)
number(2)
number(3)

Now, let's define the next relation, which, for each number, gives the next larger number, wrapping back to 0 after we reach 3.

next(0,1)
next(1,2)
next(2,3)
next(3,0)

The addition table for Modular Arithmetic is the usual addition table for arbitrary numbers except that we wrap around whenever we get past 3. For such a small arithmetic, it is easy to write out the ground facts for addition, as shown below.

add(0,0,0) add(1,0,1) add(2,0,2) add(3,0,3)
add(0,1,1) add(1,1,2) add(2,1,3) add(3,1,0)
add(0,2,2) add(1,2,3) add(2,2,0) add(3,2,1)
add(0,3,3) add(1,3,0) add(2,3,1) add(3,3,2)

That's one way to do things, but we can do better. Rather than writing out all of those facts, we can use rules to define add in terms of number and next and use those rules to facts about add. The relevant rules are shown below.

add(0,Y,Y) :- number(Y)
add(X2,Y,Z2) :- next(X,X2) & distinct(X2,0) & add(X,Y,Z) & next(Z,Z2)

First, we have an identity rule. Adding 0 to any number results in the same number. Second we have a successor rule. If X2 is the successor of X and Z is the sum of X and Y and Z2 is the successor of Z, then Z2 is the sum of X2 and Y.

As mentioned earlier, one advantage of doing things this way is economy. With these sentences, we do not need to write out the facts about add given above. They can all be computed from by the facts about next and the rules defining add. A second advantage is versatility. Our sentences define add in terms of next for arithmetic with any modulus, not just modulus 4.

9.5 Example - Directed Graphs

Consider the problem of describing finite graphs and defining properties of those graphs. Let's start by describing a small directed graph. We use symbols to refer to the nodes of the graph; and we use the edge relation to designate the arcs of the graph. For example, the dataset below describes a graph with 4 nodes and 4 arcs - an arc from a to b, an arc from b to c, an arc from c to d, and an arc from d to c.

node(a)
node(b)
node(c)
node(d)
 
edge(a,b)
edge(b,c)
edge(c,d)
edge(d,c)

Now, let's augment this program with some rules defining various relations on the nodes in our graph.

p(X) :- edge(X,X)
q(X,Y) :- edge(X,Y)
q(X,Y) :- edge(Y,X)
r(X,Y,Z) :- edge(X,Y) & edge(Y,Z)
s(X,Y) :- edge(X,Y)
s(X,Z) :- edge(X,Y) & s(Y,Z)

Here, the relation p is true of every node that has an arc to itself. The relation q is true of two nodes if and only if there is an edge from the first to the second or from the second to the first. The relation r is true of three nodes if and only if there is an edge from the first to the second and an edge from the second to the third. The relation s is the transitive closure of the edge relation.

Defining properties of a graph as a whole is often tricker than defining properties of individual nodes since we must usually ensure that the properties apply to all of the nodes in the graph. The trick in such situations is to characterize those cases when the graph does not have the desired property and then define the desired property as the negation of those cases.

Suppose, for example, we wanted to define the concept of reflexivity. A graph is reflexive if and only if every node has an arc to itself. To define this notion, we would first define what it means for a graph to be non-reflexive. A graph is non-reflexive if and only if there is a node that does not have a self-arc. Given this definition, we can then define reflexivity as the negation of this property.

nonreflexive :- node(X) & ~edge(X,X)
reflexive :- ~nonreflexive

We could also define this notion using the countofall aggregate as shown below. A graph is non-reflexive if and only if the count of all nodes with arcs to themselves is 0.

nonreflexive :- evaluate(countofall(X,edge(X,X)),0)

With this approach, we do not need to define a helper relation as in the version above. However, it involves the use of an aggregate operator, which some people find more complicated.

Exercises

Exercise 9.1: Two people are siblings if and only if they share a common parent. Write rules defining the binary sibling relation in terms of the parent relation. (Hint: you will need the built-in relation distinct to get the definition of sibling correct.)

Exercise 9.2: Write rules defining the binary uncle relation and the binary aunt relation in terms of parent and male and female.

Exercise 9.3: Two blocks are at the same height if and only if they are resting on the same number of blocks. Define the sameheight relation in terms of block and on in such a way that it works no matter how many blocks there are in the Blocks World.

Exercise 9.4: Define multiplication mul for Modular Arithmetic in terms of number and next. To simplify the task, you may define additional predicates in terms of number and next.

Exercise 9.5: Consider a directed graph defined with a unary relation node and a binary base relation edge. Write rules to determine if the graph is asymmetric, i.e. if there is an arc from one node to a second node, then the graph does not contain an arc from the second to the first.

Exercise 9.6: Consider a directed graph defined with a unary relation node and a binary base relation edge. Write rules to to determine if the graph is symmetric, i.e. if there is an arc from one node to a second node, then there is also an arc from the second to the first.

Exercise 9.7: Consider a directed graph defined with a unary relation node and a binary base relation edge. Write rules to to determine if the graph is transitive, i.e. whenever there is an arc from x to y and an arc from y to z, then there is an arc from x to z.

Exercise 9.8: Consider a directed graph defined with a unary relation node and a binary base relation edge. Write rules to to determine if the graph is acyclic, i.e. there is no sequence of arcs connecting a node to itself.