Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | |||
sav08:substitutions_for_first-order_logic [2008/03/19 16:04] vkuncak |
sav08:substitutions_for_first-order_logic [2008/03/19 22:31] damien |
||
---|---|---|---|
Line 18: | Line 18: | ||
\] | \] | ||
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$. | 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 34: | Line 35: | ||
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)) \\ | ||
nsubst(\sigma)(t_1 = t_2) &=& (nsubst(\sigma)(t_1) = nsubst(\sigma)(t_n)) \\ | nsubst(\sigma)(t_1 = t_2) &=& (nsubst(\sigma)(t_1) = nsubst(\sigma)(t_n)) \\ | ||
- | nsubst(\sigma)(\lnot F) &=& \\ | + | nsubst(\sigma)(\lnot F) &=& \neg nsubst(\sigma)(F) \\ |
- | nsubst(\sigma)(F_1 \land F_2) &=& \\ | + | nsubst(\sigma)(F_1 \land F_2) &=& nsubst(\sigma)(F_1) \wedge nsubst(\sigma)(F_2) \\ |
- | nsubst(\sigma)(\forall x.F) &=& \\ | + | nsubst(\sigma)(F_1 \lor F_2) &=& nsubst(\sigma)(F_1) \vee nsubst(\sigma)(F_2) \\ |
- | nsubst(\sigma)(\exists x.F) &=& | + | nsubst(\sigma)(\forall x.F) &=& \forall x.\ nsubst(\sigma)(F)\\ |
+ | nsubst(\sigma)(\exists x.F) &=& \exists x.\ nsubst(\sigma)(F) | ||
\end{array} | \end{array} | ||
\] | \] | ||
Line 46: | Line 48: | ||
\] | \] | ||
- | To avoid variable capture, we introduce in addition to $subst$ a safe substitution, $ssubst$. | + | To avoid variable capture, we introduce in addition to $subst$ a safe substitution, $sfsubst$. |
\[ | \[ | ||
\begin{array}{rcl} | \begin{array}{rcl} | ||
sfsubst(\sigma)(R(t_1,\ldots,t_n)) &=& R(nsubst(\sigma)(t_1),\ldots,nsubst(\sigma)(t_n)) \\ | sfsubst(\sigma)(R(t_1,\ldots,t_n)) &=& R(nsubst(\sigma)(t_1),\ldots,nsubst(\sigma)(t_n)) \\ | ||
sfsubst(\sigma)(t_1 = t_2) &=& (nsubst(\sigma)(t_1) = nsubst(\sigma)(t_n)) \\ | sfsubst(\sigma)(t_1 = t_2) &=& (nsubst(\sigma)(t_1) = nsubst(\sigma)(t_n)) \\ | ||
- | sfsubst(\sigma)(\lnot F) &=& \\ | + | sfsubst(\sigma)(\lnot F) &=& \neg sfsubst(\sigma)(F) \\ |
- | sfsubst(\sigma)(F_1 \land F_2) &=& \\ | + | sfsubst(\sigma)(F_1 \land F_2) &=& sfsubst(\sigma)(F_1) \wedge sfsubst(\sigma)(F_2) \\ |
- | sfsubst(\sigma)(\forall x.F) &=& \\ | + | sfsubst(\sigma)(F_1 \lor F_2) &=& sfsubst(\sigma)(F_1) \vee sfsubst(\sigma)(F_2) \\ |
- | sfsubst(\sigma)(\exists x.F) &=& | + | sfsubst(\sigma)(\forall x.F) &=& \left\{ \begin{array}{ll} |
+ | \forall x. sfsubst(\sigma)(F) & \text{if} ~ x \notin \text{domain}(\sigma) \wedge x \notin \bigcup_{v \in \text{domain}(\sigma)} FV(v) \\ | ||
+ | sfsubst(\sigma)(\forall x^\prime. sfsubst(\{x \mapsto x^\prime \})(F)) & \text{else}} | ||
+ | \end{array} \right.\\ | ||
+ | sfsubst(\sigma)(\exists x.F) &=& \left\{ \begin{array}{ll} | ||
+ | \exists x. sfsubst(\sigma)(F) & \text{if} ~ x \notin \text{domain}(\sigma) \wedge x \notin \bigcup_{v \in \text{domain}(\sigma)} FV(v) \\ | ||
+ | sfsubst(\sigma)(\exists x^\prime. sfsubst(\{x \mapsto x^\prime \})(F)) & \text{else}} | ||
+ | \end{array} \right. | ||
\end{array} | \end{array} | ||
\] | \] |