# Herbrand Theorem

No replies to this topic

### #1mexicanwings

New Member

• Members
• 5 posts

Posted 15 October 2005 - 07:13 AM

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!

Thanks!!

---

#### 1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users