Differences

This shows you the differences between two versions of the page.

--- sav08:herbrand_s_expansion_theorem [2008/04/01 15:59]
giuliano
+++ sav08:herbrand_s_expansion_theorem [2009/05/26 10:28]
vkuncak
@@ Line 66: / Line 66: @@
   * set $propExpand(S)$ has a propositional model
   * set $S$ has a model with domain $GT$
+**Example:** Take the first three clauses our example (from [[Normal Forms for First-Order Logic]]):
+  * $R(x,g(x))$
+  * $\neg R(x,y) \lor R(x,f(y,z)))$
+  * $P(x) \lor P(f(x,a))$
+Taking as domain $D$ the set of natural numbers, the structure $(D,\alpha)$ is a model of the conjunction of these three clauses, where $\alpha$ is given by:
+  * $\alpha(a) = 1$
+  * $\alpha(c) = 2$
+  * $\alpha(g)(x) = (x + 1)$
+  * $\alpha(f)(y,z) = y+z$
+  * $\alpha(R) = \{(x,y).\ x < y\}$
+  * $\alpha(P) = \{x.\ x \mbox{ is even} \}$
+This model induces an Herbrand model $(GT,\alpha_H)$, in which $\alpha_H(P)$ is a set of ground terms and $\alpha_H(R)$ is a relation on ground terms, $\alpha_H(R) \subseteq GT^2$.
+To determine, for example, whether $(f(a,a),g(c)) \in \alpha_H(R)$ we check the truth value of the formula
+\[
+   R(f(a,a),g(c)))
+\]
+in the original interpretation $(D,\alpha)$. The truth value of the above formula in $\alpha$ reduces to $1+1 < 2+1$, which is true. Therefore, we define $\alpha_H(R)$ to contain the pair of ground terms $(f(a,a),g(c)))$. On the other hand, $R(f(a,a),c)$ evaluates to false in $(D,\alpha)$, so we define $\alpha_H(R)$ so that it does not contain the pair $(f(a,a),c)$.