1
$\begingroup$

I was reading the book "Foundations of Logic Programming" written by J.W. Lloyd. In the book, there were definitions of interpretation and model, and when it comes to herbrand interpretation and model, I am having difficulties. It provided an example, but I did not understand it.

Example. Let $S$ be $\{ p(a), \exists x \lnot p(x) \}$. Note that the second formula $S$ is not a clause. We claim that $S$ has a model. It suffices to let $D$ be the set $\{ 0,1\}$, assign 0 to $a$ and assign to $p$ the mapping which maps 0 to true and 1 to false. Clearly this gives a model for $S$. However, $S$ does not have an Herbrand model. The only Herbrand interpretations for $S$ are $\emptyset$ and $\{ p(a)\}$. But neither of these is a model for $S$.

In my understanding, by assigning 0 to $a$ and 1 to $x$ to the formulas of $S$ make them true:

$$ p(0) = true $$

$$ \exists x \lnot p(x)[x/1] = \lnot p(1) = true $$

Therefore, $\{ 0,1\}$ is a model for $S$ But I did not really understand how do we know $[a=0,x=1]$ is not a herbrand model for $S$.

I asked the question in Theoretical Computer Science section, however was advised to post in CS. Could anyone explain it to me? Thanks in advance.

$\endgroup$
1
$\begingroup$

Herbrand models have special domains. The domain of every Herbrand model for $S$ (which is a set of formulas of $L$) is the Herbrand universe $U_L$ for $L$. The set $U_L$ cannot be $\{0, 1\}$, it has a totally different form, see the definition of Herbrand universe in Chapter 1 “Preliminaries”, §3 “Interpretations and models”. The set $U_L$ can contain $p(a)$, $p(b)$, $p(f(g(a)))$ where $a$ and $b$ are constants of $L$, $p$ is a predicate symbol of $L$, $f$ and $g$ are function symbols of $L$, such things. It cannot contain $0$ or $1$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.