*Example.*

The example isp(a,f(X),Y) <- q(X), r(Y)q(X) <- s(X)s(a) <-s(b) <-s(g(b,a)) <-r(b) <-r(c) <-

Let us start with an abstract specification of what a positive rule is supposed to be and progressively specifiy all of the component structures that are required. Our convention will be that concrete rules will be written for the reader to read using fixed-width font (as displayed above) and the abstract forms (following below) will be displayed using variable-width font. (The actual appearance on your web page may vary slightly.) This terminology suggests that when one reads variable-width displays what is intended is a general abstract form, which when "filled in" gives actual concrete structures.

A positive *rule* has the form

Hwhere H, B<-B_{1}, B_{2}, ..., B_{n}

HH is referred to as the<-

A *positive literal* has the form

P(Twhere P is a predicate symbol and T_{1},T_{2},...,T_{k})

PLastly a

Cor a

Xor has the symbolic form

F(Twhere F is a function symbol and T_{1},T_{2},...,T_{m})

FNote that literals and terms have essentially the same abstract formation.

Now, in the example presented above the constant symbols (concrete terms or names) are

the variables area b c

the function symbols areX Y

the predicate symbols aref g

What are the literals? It is implicit that one must specify what the constants, variables, function symbols and predicate symbols are actually supposed to be. In these notes we will use the convention of using Prolog-like versions of these symbolic expressions. (Constants are alphabetic word-like expresions beginning with lower-case, variable are alphabetic word-like expresions beginning with upper-case, function and predicate symbols take the same form as constants but are kept distinct from constants and from each other.)p q r s

More generally, we will say that t is a *term for the rulebase***R**
(or *of* the rulebase) provided that t simply follows the general
formation rules for terms of **R**, but t might contain a variable that
did not explicitly occur when **R** was presented. For example,
`f(g(S,a),f(W))`,
where `S` and `W` are taken as variables is considered to
be a term for the example rulebase, because it is formed using **R**'s
constants, function symbols and some new variables. Similarly, *a
literal for ***R** needs to use a predicate symbol actually
occuring in **R**, follow the general formation rules for a prediact,
but is allowed to use generally formed terms. Thus `p(T,g(a,D),f(c))`
is a literal for **R**, even though it did not specifically occur when
**R**
was presented.

Gwhere G is a positive literal for

Gwhere k >= 1 and each_{1}, G_{2}, ..., G_{k}.

As an example, for the rulebase at the beginning of this chapter, the following are simple goals:

Notice that we are following the convention that a term ofp(X,Y,Z) p(a,g(b,X),c) s(Z)

The first state goal corresponds to asking the question whetherq(a), s(b), r(c)p(X,X,X), r(X)

**universe**(**R**) =

For some rulebases,{a,b,c,f(a), f(b), f(c),f(f(a)), f(f(b)), f(f(c)),...g(a,a), g(a,b), g(a,c), g(b,a), g(b,b), g(b,c), g(c,a), g(c,b), g(c,c),g(f(a),a), ... g(g(b,b), f(a)),... }

p(a) <- q(b)q(b) <-

If rulebase **R** has no constant symbols, it is conventional to
supply one "dummy" constant. Let us use d
for this dummy symbol. Then in the case of the rulebase

we havep(X) <- q(h(X))q(Z) <-

** Exercise 1.** Formulate a recursive mathematical definition
for

In the literature, **universe**(**R**) is called the *Herbrand
universe* of the rulebase, and is named after the mathematical logician
Jacques Herbrand.

s = {X/T}where X is a variable and T is a term for

A simple substitution *acts* on a symbolic experession (term, literal,
rule, etc.) to produce a new form. For example, if s
= {`X`/`g(c,c)`} then for the first sample rulebase

that is, '(p(a,f(X),Y) <- q(X), r(Y))s= p(a,f(g(c,c)),Y) <- q(g(c,c)), r(Y)

A (general) *substitution* can be specified as

s = swhere each s_{1}s_{2}... s_{k}

If all of the variables in a symbolic form are substituted for, then the resulting symbolic form is said to be(p(a,f(X),Y) <- q(X), r(Y))s =p(a,f(g(c,a)),g(f(a),f(f(b)))) <- q(g(c,a)), r(g(f(a),f(f(b))))

Notice that `s(g(a,a),c)` is a ground literal of **R**.
We can think of this ground literal as having been produced in many ways.
It is, in its own right, a literal of **R** (using the liberal definition)
that is in fact ground so. Or, we could observe that

` s(g(a,a),c)`=
`s(g(X,Y),Z)`s
where s = { `X/a`,
`Y/a`, `Z/c
`}.

** Exercise 2.** Specify some substitutions that could
be used to entirely ground the first clause of the example rulebase.

Roughly speaking, an interpretation of a positive rulebase assigns certain
meanings or values to the arguments in the

rulebase clauses and gives truth values {true, false} to all clauses
of the rulebase and all goal expressions for the rulebase. A positive rulebase
is consistent provided that it has a model, that is, if there is an interpretation
of the rulebase which makes all of the rules in the rulebase true. A goal
is a consequence of a positive rulebase provided that every interpretation
that assigns true to every rule must also assign true to the goal. More
precise, technical definitions follow.

All of the interpretations that we will define will use **universe**(**R**)
to assign meanings to the variables of clauses of **R**. It is possible
to define interpretations over other domains, but this will not be necessary
for our present purposes.

The *base ***base**(**R**) of a positive rulebase **R**
is the collection of all grounded literals for **R**.

For the example rulebase, the base would be

base(R) = {p(U,V,W),q(U),r(U),s(U)|U,V,Winuniverse(R)}

The set **base**(**R**) represents all of the things that might
or might not be true, relative to the rulebase R, depending on the actual,
specific interpretation of **R** that one considers.

An *interpretation ***I*** *of **R** is a mapping from
**base**(**R**)
into the set {**true**,**false**}. Such a mapping
**I** assigns
specific truth values to the grounded literals of **R**.

For example, one interpretation for the example rulebase describe is
**I**_{1}(B)
= **true **for every B in **base**(**R**). Now it will turn out
that this interpretation will satisfy (make **true**) every clause of
the rulebase. Thus interpretation
**I**_{1}is a model
for the rulebase. It should be clear that the example rulebase has infinitely
many interpretations. We need to define precisely how an interpretation
is used to determine truth values for clauses and positive goals for a
rulebase.

Suppose that **I **is an interpretation of positive rulebase **R**.
The following definitions show how **I **determines a truth value for
each clause of R. If `C `is a clause of **R** having the following
form

Athen<-B_{1}, B_{2}, ... B_{n}

A'of<-B_{1}', B_{2}', ... B_{n}'

In particular, if clause C has the fact form

Athen<-

A'of<-

An interpretation *satisfies ***R** provided
that it assigns **true **to each clause of P. In this case, the interpretation
is a *model *for the rulebase.

** Exercise 4.** Fully specify
an interpretation that does

*Theorem 1.**Every positive
rulebase has at least one model.*

** Exercise 5.** Prove Theorem
1.

Now, we also want to define the truth value that
an interpretation **I **of a positive rulebase determines for a general
goal for the rulebase. Assume that general goal `G `has the form

GThen_{1}, G_{2}, ..., G_{k}

Gof G,_{1}', G_{2}', ..., G_{k}'

A goal G` `is a *consequence *of rulebase **R** if, and
only if, for every interpretation **I **of **R**, if **I **satifies
**R**
then **I **must also satisfy G. When this is the case, we will write
**R**
=> G.

Note that *an interpretation is completely determined by the values
that it asssigns to the base* of the rulebase. When we write **I**(`C`),
`C
`a
clause, or **I**(`G`), `G `a goal, we are referring to
a well-defined *extension *of the original mapping **I**.

For the example rulebase **R**, let us argue
that **R **=> `q(b)` -- that is, that `q(b)` is a consequence
of **R**. Accordingly, assume that **I** is an interpretation of
R that satisfies every clause of R. Then, in particular **I**(`s(b)
<-`) = **true** and **I**(`q(b) <- s(b)`) = **true**
since **I** must assign **true** to each of the clauses of **R**.
Consequently, **I**(`s(b)`) = **true** and **I**(`q(b)`)
= **true**.

** Exercise 6.** Prove in detail
that

** Exercise 7.** Prove in detail
that

** Exercise 8.** Prove in detail
that

For example, for example rulebase, s = {`X/a`,
`Y/f(b)`,
`Z/c`}
is an answer substitution for goal G = `p(X,Y,Z)` because **R**
=>
`p(X,Y,Z)`s .

The empty substitution is an answer substitution for a grounded goal
that is a consequence of the rulebase. For example, s
= {} is an answer substitution for the goal `G `= `p(a,f(b),c)`.

** Exercise 9.** List all answers for the goal p(X,Y,Z)
of the example rulebase.

M_{1}(R) = { L | L<-is a ground instance of a rule inR}M_{2}(R) = { L | L<-B_{1}, B_{2}, ... B_{n}is a ground instance of a rule inRand B_{1}, B_{2}, ..., B_{n}are inM_{1}(R) } ∪M_{1}(R)

...M_{k}(R) = { L | L<-B_{1}, B_{2}, ... B_{n}is a ground instance of a rule inRand B_{1}, B_{2}, ..., B_{n}are inM_{k-1}(R) } ∪M(_{k-1}R)

The *minimal (Herbrand) model* of **R** is defined
as the union of all of these sets

M(R) = ∪M_{k}(R) {k = 1,2,3,4, ...}

For the example rulebase from the beginning of this section, let us
determine
**M**(**R**).

Notice thatM_{1}(R) = {s(a), s(b), s(g(b,a)), r(b), r(c) }M_{2}(R) = { q(a), q(b), q(g(b,a)) } ∪M_{1}(R)M_{3}(R) = {p(a,f(b),q(a)), p(a,f(b),q(b)), p(a,f(b),q(g(b,a))), p(a,f(c),q(a)), p(a,f(c),q(b)), p(a,f(c),q(g(b,a))) } ∪M_{2}(R)

M(R) =M_{3}(R)

If **I** is any model of **R** then consider the set

Thus,M= {B | B in_{I}base(R) andI(B) =true}

Then, if we takeI_{M}(B) =trueif B is a member of MI_{M}(B) =falseif B is not a member of M

The folowing theorem justifies the terminology *the minimal model*
which was used when **M**(**R**) was defined.

**Theorem 2.** Suppose that **I** is a model of positive
rulebase **R**. Then **M**(**R**) is a subset of **M _{I}**.

*proof.* We use induction to show that each **M**_{k}
(in the definition of **M**(**R**))is a subset of **M _{I}**
for each k. Suppose that A belongs to

Now assume that each of **M**_{1}, ..., **M**_{k}
is a subset of **M _{I}**, and suppose that A belongs to

Awhere each B<-B_{1},...,B_{n}

Thus each **M**_{k} is a subset of **M _{I}**,
and so

In mathematical logic, it is common to talk about interpretations of logical rulebases over universes other than the Herbrand universe. However, the most important relationships are fully captured using just the Herbrand universe. The student is referred to the literature for the more general approach. See [Lloyd] in particular.

1. Suppose that `A <- ` is a grounded rule of **R**.
Then

is a rule tree. The root of this tree is `A`, the leaf is '`true`'.
The tree reflects the fact that the rule says that A is true.

2. Suppose that `A <- B _{1}, B_{2}, ..., B_{n}`is
a grounded rule of

is a rule tree. The root of this tree is A, the leaves are
`B _{1},
B_{2}, ..., B_{n}`.

3. Suppose that

is a rule tree having root `A` and leaves L={`B _{j}`} ∪
L

is also a rule tree rooted at `A`, and having leaves L_{1} ∪
L_{2}.

**Example. **Take as our positive rulebase the following sequence
of rules.

According to the defintion that we have given for rule trees, the trees that we have in mind are built up from the bottom. From the third and fourth rules we can make the rule treesa <- b, cb <- dc <-d <-

From the second rule we make rule treec d| |true true

and then use part 3 of the definition of rule tree to extend this last tree so that we get the treeb|d

Now use the first weighted rule of the rulebase to produce the rule treeb|d|true

and then use part 3 of the definition twice (using the previously constructed trees) to produce the following rule treea/ \/ \b c

We will see below that such a rule tree can be taken to suggest a kind of inference of its root from the rules of the rulebase.a/ \/ \b c| || |d true||true

Now for the formal mathematical definition of a rule tree. Rule trees will have a mathematical representation as triples <r,D> where r is the root of the tree (which is either a proposition or a disjunction of same) and D is a set of descendants of the root r; the descendants are either leaves or are themselves rule trees. Then, parts 1 through 3 of the defintion of rule tree are formulated as follows (this time without the graphical representations).

1. `If` A <- is a grounded rule then <A,{true}> is
a rule tree.

2. If A `<-` B_{1}, B_{2}, ..., B_{n}` `
is a grounded rule then <A,{B_{1}, B_{2}, ...,
B_{n}}> is a rule tree.

3. Suppose that <A,D> is a rule tree having descendants D = {B} ∪
D_{1} and leaves {B} ∪
L_{1} and suppose that T is a rule tree rooted at B having
leaves L_{2}. Then <A,{T} ∪
D1> is a rule tree having leaves L_{1} ∪
L_{2}.

Define a rule tree T or positive rulebase **R** to be a *closed*
provided that every leaf is 'true'. Also define

There are several closed rule trees displayed for the example above.C(R) = { B | B belongs tobase(R) and there is a closed rule tree T rooted at B }

The height of a rule tree is (informally) defined to be the length of the longest path in the tree from root to a leaf. The height of the last rule tree displayed above is 3. Let us further define

The relationship between C(R) and M(R), the minimal model is probably apparent to the student.C_{h}(R) = { B | B belongs tobase(R) and there is a closed rule tree T of height h rooted at B }

**Theorem 3.** Supose that R is a positive rulebase.
Then

i)C_{h}(R) =M_{h}(R) , h = 1, 2, 3, ...ii)C(R) =M(R)

** Exercise 10.** Prove Theorem 3.

A ruletree is **not** actually a specification of a procedure for
proving a consequence of a rulebase. Rule trees are an alternate
form of specification of the **semantics** of a positive rulebase.
The semantics not set-based, like for **M**(**R**), but the
semantics are **tree-based**. Both sets and trees are mathematical
structures and both can be legitimately used in the specification of logical
semantics. For positive rulebases, the two approaches have been shown
to be fully equivalent.

We are not going to characterize algorithms (procedures) for computing answers for positive rulebases in a general way. See [Lloyd] for this. We are going to study procedures for computing rule trees however, in the following sunsections.

We will exploit this connection between set-based and tree-based semantics in the later section on normal rulebases. Normal rulebases are a generalization of positive rulebases which allow for classical negation.

** Exercise 11.** Draw a closed rule tree rooted at

** Exercise 12.** Carefully list

A positive rulebase corresponds very closely to what is called a *datalog*
rulebase for Prolog. (We will try to remember to call the abstract
sequence of logical rules a *rulebase*, and the corresponding concrete
Prolog rulebase a *program*! The distinction is somewhat academic.)
Here is the datalog program form of the example rulebase first used at
the top of this section

Assume that this program in contained in file namedp(a,f(X),Y) :- q(X), r(Y).q(X) :- s(X).s(a).s(b).s(g(b,a)).r(b).r(c).

C:\xsb\logic>xsb

C:\xsb\logic>c:\xsb\emu\xsb.exe -i -D \xsb[sysinitrc loaded]XSB Version 1.8.1 (0/0/0)[Windows NT, optimal mode]| ?- [example].[example loaded]

yes| ?- p(X,Y,Z).

X = aY = f(a)Z = b;

X = aY = f(a)Z = c;

X = aY = f(b)Z = b;

X = aY = f(b)Z = c;

X = aY = f(g(b,a))Z = b;

X = aY = f(g(b,a))Z = c;

no| ?-

An *answer computing algorithm* is any algorithm that produces
answers for goals. Prolog (in a general sense) uses a modification
of what is called SLD resolution (see [Lloyd] for theoretical details).
XSB is a kind of Prolog engine that implements an abstract machine
(WAM - Warren Abstract Machine) that compiles logical rules, but XSB does
not specifically implement the SLD procedure itself. XSB essentially
computes the same answers as standard Prolog, only better. Better
because XSB uses "enhancements". The primary enhancement is called
"tabling", which is a way to save previous goal attempts for later use
(e.g., avoid recomputing or detect some repeats). Tabling is a declared
option for compiling a predicate; without using the option, one gets Prolog
behavior. We will not concern ourselves with the tabling at this
point. Most of what we now present should be reproducable using any
brand of Prolog, with slight modifications.

An answer computing algorithm is *sound* provided that every answer
s
that it computes is really an answer (i.e.,
**R** => Gs).
An answer computing algoritm is *complete* provided that it does in
fact compute every possible actual answer (every s
such that R => Gs for all goals G).

For simplicity, we start with an XSB program that does not actually produce rule trees (as an explicit part of an answer), but which does "process" rule trees. The program (in this first simple form) appears in many Prolog textbooks. It does not simulate SLD deduction; it does implement a procedural form of tree semantics.

Assume that this program is in the file% rt1.P -- compute via rule_treesrule_tree(true) :- !. /* true leaf */ rule_tree((G,R)) :- !, rule_tree(G), rule_tree(R). /* search each branch */ rule_tree(G) :- clause(G,Body), rule_tree(Body). /* grow branches */

This 1st, 2nd, and 3rd clauses in this program corresponds closely to
conditions 1,2,3 in the definition of how to form a rule tree, except that
the 2nd and 3rd reversed in the program. The reason for the reversal
is this: We do not want XSB to try to find a dynamic clause for a
(G,R) sequence (illegal in XSB, but simple failure for most Prologs).
Now, to use this program with XSB we need to find a way to load a rulebase
as a *dynamic* program. A *dynamic* program actually stores
the clauses and interprets them piecemeal via the built-in predicate 'clause(+Head,-Body)'.
Use the following additional program to do the dynamic loading

Supose that this auxialliary program has been included in fileknow(File) :- see(File),repeat,read(C),process(C),seen.

process(end_of_file):- !.process(C) :- assert(C), fail.

Notice that we get exactly the same answers as we got for the previous XSB session for the same goal executing the compiled program ('example.P').C:\xsb\logic>xsb

C:\xsb\logic>c:\xsb\emu\xsb.exe -i -D \xsb[sysinitrc loaded]XSB Version 1.8.1 (0/0/0)[Windows NT, optimal mode]| ?- [rt].[Compiling .\rt][rt compiled, cpu time used: 0.6600 seconds][rt loaded]

yes| ?- know('example.P').

yes| ?- rule_tree(p(X,Y,Z)).

X = aY = f(a)Z = b;

X = aY = f(a)Z = c;

X = aY = f(b)Z = b;

X = aY = f(b)Z = c;

X = aY = f(g(b,a))Z = b;

X = aY = f(g(b,a))Z = c;

no| ?-

An example program to try is the following% rt2.P -- add evaluation to rt1

rule_tree(true) :- !. /* true leaf */rule_tree((G,R)) :-!,rule_tree(G),rule_tree(R). /* search each branch */rule_tree(G) :-predicate_property(G,built_in),!,call(G). /* let XSB do it */rule_tree(G) :-clause(G,Body),rule_tree(Body). /* grow branches */

The program uses evaluation for 'level(X,Y) :- X < Y,write('Raise left by '),Z is Y - X,writeln(Z).level(X,Y) :- X > Y,write('Raise right by '),Z is X - Y,writeln(Z).level(X,Y) :- X == Y,write('Yes, level.').

C:\xsb\logic>xsb

C:\xsb\logic>c:\xsb\emu\xsb.exe -i -D \xsb[sysinitrc loaded]XSB Version 1.8.1 (0/0/0)[Windows NT, optimal mode]| ?- [rt2].[rt2 loaded]

yes| ?- know('level.P').

yes| ?- rule_tree(level(4.3, 6.8)).Raise left by 2.5000

yes| ?- rule_tree(level(2.5,2.5)).Yes, level.yes| ?-

Consider the following test program,% rt3.P rule_tree(true,true) :- !. /* true leaf */ rule_tree((G,R),(TG,TR)) :- !, rule_tree(G,TG), rule_tree(R,TR). /* search each branch */ rule_tree(G,eval(G)) :- predicate_property(G,built_in), !, call(G). /* let XSB do it */ rule_tree(G,tree(G,T)) :- clause(G,Body), rule_tree(Body,T). /* grow branches */

Load% tree_test.Pp(X) :- q(X), r(Y), X < Y. q(3). r(2). r(5). r(10).

Here is a program to draw any clause tree that is generated ...?- rule_tree(p(X),Tree) Tree = tree(p(3),(tree(q(3),true),tree(r(5),true),eval(3 < 5))) X = 3 ; Tree = tree(p(3),(tree(q(3),true),tree(r(10),true),eval(3 < 10))) X = 3 ; no

Assume that we have addedwhy(G) :- rule_tree(G,T), nl, draw_tree(T,5). draw_tree(tree(Root,Branches),Tab) :- !, tab(Tab), write('|-- '), write(Root), nl, Tab5 is Tab + 5, draw_tree(Branches,Tab5). draw_tree((B,Bs),Tab) :- !, draw_tree(B,Tab), draw_tree(Bs,Tab). draw_tree(Node,Tab) :- tab(Tab), write('|-- '), write(Node), nl.

The tree corresponding to the first answer would be drawn ("vertically oriented") as follows...?- why(p(X)). |-- p(3) |-- q(3) |-- true |-- r(5) |-- true |-- eval(3 < 5) X = 3 ; |-- p(3) |-- q(3) |-- true |-- r(10) |-- true |-- eval(3 < 10) X = 3 ; no

** Exercise 15.** Use the program

Gatherp(a,f(X),Y) <- q(X), r(Y)q(X) <- s(X)s(a) <-s(b) <-s(g(b,a)) <-r(b) <-r(c) <-

** Exercise 16.** Design a new 'why' program that also
explains "why not" for goals that can be started but not completely satisfied.

This section does not consider the possiblity of programs with loops
and algorithms for simple loop detection. These topics are considered
in Section 6.5.

Prolog Tutorial Contents