A Gentle Introduction to Herbrand Models

Almost related pun of the day: Some interpretations are more equal than others.

I’ve not yet encountered a single person — including myself — who have grasped the concept and utilities of Herbrand interpretations at a first glance. This might lead one to believe that the theory is so hard and abstract that it’s not really related to every day logic programming anyway, but nothing could be further from the truth. On the contrary, the problem is rather that the definition of a Herbrand interpretation is too simple to make any sense — a wolf in sheep’s clothing. Hence we have a good subject at hand and a splendid opportunity for me to confuse you further with deceptive didacticism.

A logic program is a finite set of rules and facts. Let’s not bother ourselves by giving a formal definition and instead cut right to the chase with an example:

natural(zero).
natural(s(N)) \leftarrow natural(N).

From a pragmatic perspective it should be construed as: zero is natural (i.e. a natural number), and if it is known that N is a natural number, then it’s the case that s(N) is a natural number. I’ll be the first one to admit that it’s not a very interesting program, but it’ll have to do for the moment. Following this intuition it’s possible to answer queries to the program in two different ways: top-down and bottom-up. Let our query be natural(s(zero)). Here’s how the two different strategies differ:

Top-down

To solve natural(s(zero)), we unify natural(s(zero)) with natural(s(N)) and obtain the unifier \{N= zero\}. Then we recursively solve the new goal obtained from the right-hand side of the rule: natural(zero). This can be done in one step, and since there are no more goals to resolve we’re done.

Bottom-up

We begin to note that natural(zero) holds. A solid start! Then, since the body of the second clause is true with the unifier \{N= zero\} (the same as before), we conclude that natural(s(zero)) must also be true. Since this is the same as the original query there’s no reason to continue.

I’ve admittingly danced over a lot of intricate details, but I should at least mention that the top-down approach corresponds to SLD-resolution while the bottom-up approach corresponds to unit-resolution (sometimes called hyper-resolution). The difference between the two lies in the application of the resolution rule: in SLD-resolution we produce resolvents between a head of clause and a goal clause, in unit-resolution we produce resolvents between a unit-clause and the body of a clause. So we have two ways of answering a query, but how do we know that they are correct? For that we need to backtrack (pun not intended) and carefully explicate the meaning of the program. This is formally done with a model. The content of this particular program is:

  1. A single constant: zero.
  2. A single function symbol of arity 1: s.
  3. A single predicate symbol of arity 1: natural.

And to provide a meaning to the program we need to explain exactly what these symbols mean. We need two functions: one for the constant symbol, f_{zero}, and one for the function symbol, f_s. In the domain of the natural numbers these can be defined as:

  1. f_{zero}(zero) = 0
  2. f_s(N) = N + 1

Which may then be combined into a single function, f, that allows us to recursively compute the value of any term in the program. It is defined as:

f(zero) = f_{zero}(zero)

f(s(N)) = f_s(f(N))

For example:

f(s(zero)) = f_s(f_{zero}(zero)) = f_s(0) = 0 + 1 = 1

The only predicate symbol, natural, must be mapped to a relation on the domain. The simplest such is just the set \{0, 1, ...\}. And we’re done with this particular model.

Is it a good model? That depends. In the context of our logic program it seems to be a bit overkill. Previously we only had to worry about the symbols that actually appeared in the program: s, zero and natural; but now we’ve introduced arithmetical notation that so to speak goes beyond the original interpretation. There’s really no reason at all to demand that zero must be evaluated to 0 and that s(zero) must be evaluated to 1. They are just two different representations. With this in mind we can construct a simpler model:

  1. f_{zero}(zero) = zero
  2. f_s(N) = s(N)

And in the same vein as before this may be combined into a single function f. Applied to the same term as before we obtain:
f(s(zero)) = f_s(f_{zero}(zero)) = f_s(zero) = s(zero)

We’re back with what we started with! This means that the terms in the program are just mapped to themselves, and why not? The predicate symbol natural will now be mapped to the relation \{zero, s(zero),...\} instead of \{0, 1, ...\}.

These kinds of models are known as Herbrand models. The general definition closely mimics the earlier one, with the effect that all terms are mapped to themselves and that predicates are mapped to relations over the universe of terms (the Herbrand universe). Since the only interesting part of a Herbrand model is the mapping of predicates, it’s often presented as a set that enumerates the values for which the predicates should be true. In our example, which is in fact a least Herbrand model, this was \{natural(zero), natural(s(zero)), ...\}. As should be evident by now this is precisely the set that we already had in mind as programmers, it’s the intended meaning of the program.

But was this just a fluke? Could there be cases where it’s impossible to find a Herbrand model even though there’s exists another model? Fortunately the answer is no: if there exists a model for a logic program then there also exists a Herbrand model. This provides a theoretical justification for both SLD- and unit-resolution. In the first case we use this in our search for unsatisfiable sets of ground clauses from the Herbrand universe, in the second case we actually build the (least) Herbrand model from bottom up.

Advertisements

4 responses to “A Gentle Introduction to Herbrand Models”

  1. poissonbreaker says :

    Nice post. I have one question though, how would you map the formal concept of a model, as M = (D,F) to your simple program. D should be the set { zero, s, natural } but what about F. My initial guess is that all symbols in the vocabulary are needed as s(zero), s(s(zero)).. so D = { zero, natural, s, s(zero),s(s(zero)),…}; then F would be as follows:

    F(zero) = 0,
    F(s) = {0,1,2,…},
    F(s(zero)) = 1,
    F(s(s(zero)) = 2,

    F(natural) = {0,1,2,….}

    Cheers,
    Jesus

    • Victor Lagerkvist says :

      Thanks for your comment! You’re almost there, but some pieces seems to be missing. First we define a function mapping each constant to a value in the domain. In this trivial program this just means that we assign ‘zero’ the value 0. Then we need a function mapping each term to a natural number, i.e mapping s(N) to N + 1. Note that we do not need to assign s to the set of natural numbers. Then we assign our single unary predicate to the domain values for which it should hold: all natural numbers. Did this make anything clearer?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: