by Brian Bosse, Copyright July 22, 2008, all rights reserved. 55 views
Proper substitutions for variables are just like proper substitutions for name letters with one exception. A name letter can be substituted for all free occurrences of a variable. A variable can be substituted for all free occurrences of another variable as long as the substituting variable remains free. This last phrase is the only difference between variable substitution and name substitution. Let me use an example from our last post.
1. ∀x(F(x) → G(y))
The only free occurrence of a variable is the 'y'. As such, I could take the variable 'z' and substitute it as follows…
2. ∀x(F(x) → G(z))
However, I cannot substitute the variable 'x' for the variable 'y' because the result would be a bound variable…
3. ∀x(F(x) → G(x))
Notice, the 'x' in G(x) is bound by the quantifier ∀x. Therefore, 3 is not a proper substitution. Let's provide one more example…
4. ∃(z)(F(x) ∧ G(y)) → ∃(x)(H(x)) ∨ G(x)
Now, I want to substitute a variable for 'x'. The free occurrences of 'x' are in F(x), and G(x). Can I use the variable 'z'? No I can't. The reason is that when I substitue 'z' for 'x' in F(x) the resulting variable is bound by ∃(z). As such, I need to choose a different variable. Let's choose 'y'.
5. ∃(z)(F(y) ∧ G(y)) → ∃(x)(H(x)) ∨ G(y)
Here is our formal definition for the proper substitution of a variable…
Definition: A symbolic formula φβ comes from a symbolic formula φα by proper substitution of a variable β for a variable α if φβ is like φαexcept for having free occurrences of β wherever φαhas free occurrences of α.
Notice, in our definition we made sure to say that the substituting variable β is always a free occurrence.
-----No comments yet.