6.2 Positive Logic

Positive rulebases

Example.

p(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

H <- B₁, B₂, ..., B_n

H <-

A positive literal has the form

P(T₁,T₂,...,T_k)

P

C

X

F(T₁,T₂,...,T_m)

F

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

a   b   c

X  Y

f  g

p  q  r  s

More generally, we will say that t is a term for the rulebaseR (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.

Goals for positive rulebases

G

G₁, G₂, ..., G_k.

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

p(X,Y,Z)
p(a,g(b,X),c)
s(Z)

q(a), s(b), r(c)
p(X,X,X), r(X)

The universe of a rulebase

universe(R) =

{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

p(X) <- q(h(X))
q(Z) <-

Exercise 1.  Formulate a recursive mathematical definition for universe(R) in general.

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

Substitutions

s = {X/T}

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

(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 = s₁s₂ ... s_k

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

Interpretations and models

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,W in universe(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₁(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₁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

A <- B₁, B₂, ... B_n

A' <- B₁', B₂', ... B_n'

In particular, if clause C has the fact form

A <-

A' <-

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 not satisfy the example rulebase.

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

G₁, G₂, ..., G_k

G₁', G₂', ..., 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 p(a,f(g(b,a),c) is a consequence of the example rulebase.

Exercise 7.  Prove in detail that p(a,f(g(a,b)),c) is not a consequence of the example rulebase.

Exercise 8.  Prove in detail that p(a,f(g(b,a),Z) is not a consequence of the example rulebase.  Are there any goals with variables that could be consequences of the example rulebase? Why?
 

Answers

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.
 

The minimal  model

M₁(R) = { L |  L <- is a ground instance of a rule in R }
M₂(R) = { L |  L <- B₁, B₂, ... B_n  is a ground instance of a rule in R  and B₁, B₂, ..., B_n are in M₁(R) } ∪ M₁(R)
...
M_k(R) = { L |  L <- B₁, B₂, ... B_n  is a ground instance of a rule in R  and B₁, B₂, ..., B_n are in M_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).

M₁(R) = { s(a), s(b), s(g(b,a)), r(b), r(c) }
M₂(R) = { q(a), q(b), q(g(b,a)) } ∪M₁(R)
M₃(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₂(R)

M(R) =  M₃(R)

If I is any model of R then consider the set

M_I = {B | B in base(R) and I(B) = true }

I_M(B) = true if B is a member of M
I_M(B) = false if 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 M₁ (case k=1). Then A <- is a ground instance a rule of R.  As such, since I is a model of R, I(A) = true, so A must belong to M_I.

Now assume that each of M₁, ..., M_k is a subset of M_I, and suppose that A belongs to M_k+1.  Then there must be a grounded rule of R of the form

A <- B₁,...,B_n

Thus each M_k is a subset of M_I, and so M(R), the union, must also be a subset of M_I.

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.

Rule Trees

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₁, B₂, ..., B_nis a grounded rule of R. Then

is a rule tree. The root of this tree is A, the leaves are B₁, B₂, ..., B_n.

3. Suppose that

is a rule tree having root A and leaves L={B_j} ∪ L₁. Suppose further that T is a rule tree rooted at B_j having leaves L₂. Then

is also a rule tree rooted at A, and having leaves L₁ ∪ L₂.
 

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

a <- b, c
b <- d
c <-
d <-

  c                d
  |                |
true              true

b
|
d

 b
 |
 d
 |
true

    a
   /  \
  /    \
  b    c

    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₁, B₂, ..., B_n  is a  grounded rule then <A,{B₁, B₂, ..., B_n}> is a rule tree.

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

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

C(R) = { B | B belongs to base(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

C_h(R) = { B | B belongs to base(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 p(a,f(g(a,b)),c) for the example rulebase at the top of this section.

Exercise 12.  Carefully list all of the answers for the goal p(X,Y,Z) for the same rulebase.  Explain how  you know that you have all the answers and only answers!

Prolog computation of rule trees -- 1st version of the meta-interpreter

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

p(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 = a
Y = f(a)
Z = b;

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

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

X = a
Y = f(b)
Z = c;

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

X = a
Y = 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.

% rt1.P  -- compute via rule_trees

rule_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

know(File) :- see(File),
              repeat,
              read(C),
              process(C),
              seen.

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

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 = a
Y = f(a)
Z = b;

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

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

X = a
Y = f(b)
Z = c;

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

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

no
| ?-

Built-in evaluations -- 2nd version of the meta-interpreter

% 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 */
 

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
| ?-

Explicitly computing and drawing rule trees -- 3rd version of the meta-interpreter

% 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 */

% tree_test.P

p(X) :- q(X), r(Y), X < Y.
q(3).
r(2).
r(5).
r(10).

?- 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

why(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.

?- 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 rt3.P to investigate goals for the (program version of the) rulebase at the top of this section.

p(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.