62
Formal Logic
would be a proof of the wff (4x)(E y)Q(x, y) S (4x)Q(x, a). This is also not a valid
wff. For instance, in the interpretation where the domain consists of the integers
and Q(x, y) means that x + y = 0, then it is the case that for every integer x there
is an integer y (the negative of x) such that x + y = 0. However, if a is a particular
fixed element in the domain, then it will not be true that adding that same integer
a to every x will always produce zero.
pRaCtiCe 23 Prove the argument
(4x)[P(x) ` Q(x)] S (4x)[Q(x) ` P(x)].
Existential Generalization
The last rule allows insertion of an existential quantifier. From P(x) or P(a) we can
derive (E x)P(x); something has been named as having property P, so we can say
that there exists something that has property P.
eXAMPLe 29
Prove the argument (4x)P(x) S (E x)P(x).
Here is a proof sequence.
1. (4x)P(x) hyp
2. P(x)
1, ui
3. (E x)P(x) 2, eg
Without the restriction on existential generalization, from P(a, y) one could
derive (E y)P( y, y); here the quantified variable y, which replaced the constant symbol a, already appeared in the wff to which existential generalization was applied.
But the argument P(a, y) S (E y)P( y, y) is not valid. In the domain of integers, if
P(x, y) means “y > x” and a stands for 0, then if y > 0, this does not mean that
there is an integer y that is greater than itself.
More work with rules
As is the case with propositional logic rules, predicate logic rules can be applied
only when the exact pattern of the rule is matched (and, of course, when no
restrictions on use of the rule are violated). In particular, notice that the instantiation rules strip off a quantifier from the front of an entire wff that is in the
scope of that quantifier. Both of the following would be illegal uses of existential
instantiation:
1. (E x)P(x) ~ (E x)Q(x) hyp
2. P(a) ~ Q(a)
1, incorrect ei. The scope of the first existential quantifier in step 1 does not extend to the whole rest of
the wff.
Formal Logic
would be a proof of the wff (4x)(E y)Q(x, y) S (4x)Q(x, a). This is also not a valid
wff. For instance, in the interpretation where the domain consists of the integers
and Q(x, y) means that x + y = 0, then it is the case that for every integer x there
is an integer y (the negative of x) such that x + y = 0. However, if a is a particular
fixed element in the domain, then it will not be true that adding that same integer
a to every x will always produce zero.
pRaCtiCe 23 Prove the argument
(4x)[P(x) ` Q(x)] S (4x)[Q(x) ` P(x)].
Existential Generalization
The last rule allows insertion of an existential quantifier. From P(x) or P(a) we can
derive (E x)P(x); something has been named as having property P, so we can say
that there exists something that has property P.
eXAMPLe 29
Prove the argument (4x)P(x) S (E x)P(x).
Here is a proof sequence.
1. (4x)P(x) hyp
2. P(x)
1, ui
3. (E x)P(x) 2, eg
Without the restriction on existential generalization, from P(a, y) one could
derive (E y)P( y, y); here the quantified variable y, which replaced the constant symbol a, already appeared in the wff to which existential generalization was applied.
But the argument P(a, y) S (E y)P( y, y) is not valid. In the domain of integers, if
P(x, y) means “y > x” and a stands for 0, then if y > 0, this does not mean that
there is an integer y that is greater than itself.
More work with rules
As is the case with propositional logic rules, predicate logic rules can be applied
only when the exact pattern of the rule is matched (and, of course, when no
restrictions on use of the rule are violated). In particular, notice that the instantiation rules strip off a quantifier from the front of an entire wff that is in the
scope of that quantifier. Both of the following would be illegal uses of existential
instantiation:
1. (E x)P(x) ~ (E x)Q(x) hyp
2. P(a) ~ Q(a)
1, incorrect ei. The scope of the first existential quantifier in step 1 does not extend to the whole rest of
the wff.