Section 1.4 Predicate Logic
63
1. (4x)(E y)Q(x, y) hyp
2. (4x)Q(x, a)
1, incorrect ei. The existential quantifier in step 1 is not at
the front.
Similarly, the rules to insert a quantifier put the quantifier in the front of a wff that
is then entirely within its scope.
The new derivation rules all have restrictions, but in practice, you are most
likely to violate the ei restriction. Pay special attention to this restriction and be
sure that when you substitute a constant using ei, it’s not a previously used constant.
Even though we have added only four new derivation rules, the rule set is
complete and correct. We can prove every valid argument and only valid arguments using these rules. Application of the rules, as in the case of propositional
logic, is somewhat mechanical because there are only a limited number of options
at each step. Again, the general plan of attack is usually as follows:
• Strip off the quantifiers.
• Work with the separate wffs.
• Insert quantifiers as necessary.
eXAMPLe 30
Using predicate logic, prove the argument
(4x)[P(x) ` Q(x)] S (4x)P(x) ` (4x)Q(x)
In Example 24(c ) we noted that this wff is valid, so if all valid arguments are provable, we should be able to find a proof sequence. As usual, the hypothesis gives us
a starting point.
1. (4x)[P(x) ` Q(x)] hyp
Stripping off the universal quantifier that appears in step 1 will yield access to
P(x) ` Q(x), which can then be separated. The universal quantifier can then be
inserted separately on each of those two wffs using universal generalization. The
conclusion (4x)P(x) ` (4x)Q(x) will follow. A proof sequence is
1. (4x)[P(x) ` Q(x)]
hyp
2. P(x) ` Q(x)
1, ui
3. P(x)
2, sim
4. Q(x)
2, sim
5. (4x)P(x)
3, ug
6. (4x)Q(x)
4, ug
7. (4x)P(x) ` (4x)Q(x) 5, 6, con
Neither restriction on universal generalization has been violated because x is not
free in the hypothesis and existential instantiation has not been used.
pRaCtiCe 24 Using predicate logic, prove the following argument. (Hint: The deduction
method still applies.)
(4y)[P(x) S Q(x, y)] S [P(x) S (4y)Q(x, y)]
63
1. (4x)(E y)Q(x, y) hyp
2. (4x)Q(x, a)
1, incorrect ei. The existential quantifier in step 1 is not at
the front.
Similarly, the rules to insert a quantifier put the quantifier in the front of a wff that
is then entirely within its scope.
The new derivation rules all have restrictions, but in practice, you are most
likely to violate the ei restriction. Pay special attention to this restriction and be
sure that when you substitute a constant using ei, it’s not a previously used constant.
Even though we have added only four new derivation rules, the rule set is
complete and correct. We can prove every valid argument and only valid arguments using these rules. Application of the rules, as in the case of propositional
logic, is somewhat mechanical because there are only a limited number of options
at each step. Again, the general plan of attack is usually as follows:
• Strip off the quantifiers.
• Work with the separate wffs.
• Insert quantifiers as necessary.
eXAMPLe 30
Using predicate logic, prove the argument
(4x)[P(x) ` Q(x)] S (4x)P(x) ` (4x)Q(x)
In Example 24(c ) we noted that this wff is valid, so if all valid arguments are provable, we should be able to find a proof sequence. As usual, the hypothesis gives us
a starting point.
1. (4x)[P(x) ` Q(x)] hyp
Stripping off the universal quantifier that appears in step 1 will yield access to
P(x) ` Q(x), which can then be separated. The universal quantifier can then be
inserted separately on each of those two wffs using universal generalization. The
conclusion (4x)P(x) ` (4x)Q(x) will follow. A proof sequence is
1. (4x)[P(x) ` Q(x)]
hyp
2. P(x) ` Q(x)
1, ui
3. P(x)
2, sim
4. Q(x)
2, sim
5. (4x)P(x)
3, ug
6. (4x)Q(x)
4, ug
7. (4x)P(x) ` (4x)Q(x) 5, 6, con
Neither restriction on universal generalization has been violated because x is not
free in the hypothesis and existential instantiation has not been used.
pRaCtiCe 24 Using predicate logic, prove the following argument. (Hint: The deduction
method still applies.)
(4y)[P(x) S Q(x, y)] S [P(x) S (4y)Q(x, y)]