Herbrand Theorem

mexicanwings 101 Oct 15, 2005 at 07:13

Hi Everone,

I have difficulties understanding Herbrand Theorem. There’re certain things which i just can’t seem to think through. Could i ask for some advise please. Thanks alot.

Lets say that given the following logic program P:

p(a) <- p(X), q(X)
p(f(X)) <- p(X)
q(b) <-
q(f(X)) <- q(X)

We know that the Herbrand Universe = {a, f(a), f(f(a)), b, f(b), f(f(b)),…}

We also know that the Herbrand Base = {p(a), p(f(a)), p(f(f(a))), p(b), p(f(b)), p(f(f(b))),…}

This is where i’m stuck. How do i go about finding the Least Herbrand Model? But before we get to least herbrand model, let me ask about the concept of a model. I read and understand that a model is an interpretation which makes all the formulae in the set simultaneously true. Given this interpretation, would the following be a model for the above program?

I = {q(b), p(b)}

To me, this seems logical, because if q(b) is true, the last statement would also be true. If both q(b) and p(b) are both true, then the first statement would be true. if p(b) is true, then the second statement would be true. So by merely making these 2 clauses true, every other formulae in the logic program is true. Is this considered a model?

My friend tells me that:

I = {q(b), q(f(b)), q(f(f(b)),….} is also a model, but i don’t quite seem to get the idea. where did q(f(b)) come from? what about q(f(f(b))? and why is it infinite?

I’m really confused and would really appreciate any help!


0 Replies

Please log in or register to post a reply.

No replies have been made yet.