Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
sav08:substitutions_for_first-order_logic [2008/03/19 08:39] vkuncak |
sav08:substitutions_for_first-order_logic [2008/03/19 10:39] vkuncak |
||
---|---|---|---|
Line 17: | Line 17: | ||
\forall x_1. \exists y_1. x_1 < y_1 | \forall x_1. \exists y_1. x_1 < y_1 | ||
\] | \] | ||
- | and then after substitution we obtain $\exists y_1. y + 1 < y_1$, which is a correct consequence. | + | and then after substitution $\{x_1 \mapsto y+1\}$ we obtain $\exists y_1. y + 1 < y_1$, which is a correct consequence of $\forall x. \exists y. x < y$. |
===== Naive and Safe Substitutions ===== | ===== Naive and Safe Substitutions ===== | ||
Line 24: | Line 24: | ||
We define naive substitution recursively, first for terms: | We define naive substitution recursively, first for terms: | ||
- | \[ | + | |
- | \begin{array}{rcl} | + | $subst(\sigma)( x ) = \sigma( x ),\ \sigma {\rm defined at } x $ |
- | subst(\sigma)(x) &=& \sigma(x), \mbox{ if $\sigma$ defined at $x$} \\ | + | |
- | subst(\sigma)(x) &=& x, \mbox{ if $\sigma$ not defined at $x$} \\ | + | $subst(\sigma)( x ) = x,\ \sigma {\rm not defined at } x $ |
- | subst(\sigma)(f(t_1,\ldots,t_n)) &=& f(subst(\sigma)(t_1),\ldots,subst(\sigma)(t_n)) | + | |
- | \end{array} | + | $subst(\sigma)(f(t_1,\ldots,t_n)) = f(subst(\sigma)(t_1),\ldots,subst(\sigma)(t_n))$ |
- | \] | + | |
- | then for formulas: | + | and then for formulas: |
\[\begin{array}{rcl} | \[\begin{array}{rcl} | ||
nsubst(\sigma)(R(t_1,\ldots,t_n)) &=& R(nsubst(\sigma)(t_1),\ldots,nsubst(\sigma)(t_n)) \\ | nsubst(\sigma)(R(t_1,\ldots,t_n)) &=& R(nsubst(\sigma)(t_1),\ldots,nsubst(\sigma)(t_n)) \\ | ||
Line 39: | Line 39: | ||
nsubst(\sigma)(\forall x.F) &=& \\ | nsubst(\sigma)(\forall x.F) &=& \\ | ||
nsubst(\sigma)(\exists x.F) &=& | nsubst(\sigma)(\exists x.F) &=& | ||
+ | \end{array} | ||
\] | \] | ||
Line 64: | Line 65: | ||
**Lemma:** $(\forall x.F) \models sfsubst(\{x \mapsto t\}(F)$. | **Lemma:** $(\forall x.F) \models sfsubst(\{x \mapsto t\}(F)$. | ||
- |