by Brian Bosse, Copyright July 24, 2008, all rights reserved.
Existential Generalization: "Brian is mortal" leads to "Something is mortal." In other words, M(B) leads to ∃x(M(x)). Let's now present the abstract rule -
φζ leads to ∃α(φα) where α is a variable, ζ is symbolic term, φα and φζ are symbolic formulas, and φζ comes from φα by proper substitution of ζ for α.
"Brian is mortal" translates to M(B). Now our rule is that φζ leads to ∃α(φα). In this case, φζ stands for M(B). α stands for 'x', φα stands for M(x). Since ζ is a proper substitution for α in φα, then we are allowed to conclude to ∃α(φα) , which is ∃x(M(x)).
-----Posted in Logic • 0 Comments • Permalink • 48 views
by Brian Bosse, Copyright July 23, 2008, all rights reserved.
Now that we have identified what constitutes a proper substitution for variables and name letters we are able to define three new inference rules in the predicate calculus. This post will deal with the first one: universal instantiation.
Universal Instantiation: "Everything is mortal" leads to "Brian is mortal." In other words, ∀x(M(x)) leads to M(B). Let's now present the abstract rule -
∀α(φα) leads to φζ where α is a variable, ζ is symbolic term, φα and φζ are symbolic formulas, and φζ comes from φα by proper substitution of ζ for α.
The key point here is that the resulting φζ comes from φα by proper substitution of ζ for α. That means the resulting formula only substitutes ζ for α in those cases where α is free within φα. Notice, it does not say within ∀α(φα), for then α is not free. Do not confuse φα with ∀α(φα) - they are not the same. Let's go back and illustrate this using our previous example.
"Everything is mortal" translates to ∀x(M(x)). Now our rule is that ∀α(φα) leads to φζ. In this case, α stands for 'x', φα stands M(x). We now let ζ stand for 'B', which is itself the name place for 'Brian'. Since we want to do a proper substitution of ζ for α in φα, we are doing a proper substitution of 'B' for 'x' in M(x). This means our φζ becomes M(B). M(B) says, "Brian is mortal." As such, we can go from "Everything is mortal" to "Brian is mortal" by the universal instantiation of 'Brian'.
-----Posted in Logic • 0 Comments • Permalink • 55 views
by Brian Bosse, Copyright July 22, 2008, all rights reserved.
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.
-----Posted in Logic • 0 Comments • Permalink • 54 views
Page 1 of 8 pages 1 2 3 > Last »