58
Formal Logic
S e c t I o n 1 . 4 pRediCate logiC
We can imagine arguments of the form
P 1 ` P 2 ` P 3 ` … ` P n S Q
where the wffs are built from predicates and quantifiers as well as logical connectives and grouping symbols. For a valid argument, Q must follow logically from
P 1 , … , P n based solely on the internal structure of the argument, not on the truth
or falsity of Q in any particular interpretation. In other words, the wff
P 1 ` P 2 ` P 3 ` … ` P n S Q
must be valid—true in all possible interpretations. No equivalent of the truth table
exists to easily prove validity, so we turn to a formal logic system called predicate
logic. We again use a system of derivation rules to build a proof sequence leading from the hypotheses to the conclusion. The rules should once more be truthpreserving, so that if in some interpretation, all the hypotheses are true, then the
conclusion will also be true in that interpretation. The system will then be correct
(only valid arguments will be provable). We also want the system to be complete
(every valid argument should be provable), yet at the same time the rule set should
be minimal.
Derivation rules for Predicate Logic
4
The equivalence rules and inference rules of propositional logic are still part of
predicate logic. An argument of the form
P ` (P S Q) S Q
is still valid by modus ponens, even if the wffs involved are predicate wffs.
eXAMPLe 25
Use predicate logic to prove the validity of the argument
(4x)R(x) ` [(4x)R(x) S (4x)S(x)] S (4x)S(x)
A proof sequence is
1. (4x)R(x)
hyp
2. (4x)R(x) S (4x)S(x) hyp
3. (4x)S(x)
1, 2, mp
However, there are many arguments with predicate wffs that are not tautologies but are still valid because of their structure and the meaning of the universal and existential quantifiers (see Example 24). The overall approach to proving
these arguments is to strip off the quantifiers, manipulate the unquantified wffs,
4 A complete list of derivation rules for propositional and predicate logic is given in Appendix A.
Formal Logic
S e c t I o n 1 . 4 pRediCate logiC
We can imagine arguments of the form
P 1 ` P 2 ` P 3 ` … ` P n S Q
where the wffs are built from predicates and quantifiers as well as logical connectives and grouping symbols. For a valid argument, Q must follow logically from
P 1 , … , P n based solely on the internal structure of the argument, not on the truth
or falsity of Q in any particular interpretation. In other words, the wff
P 1 ` P 2 ` P 3 ` … ` P n S Q
must be valid—true in all possible interpretations. No equivalent of the truth table
exists to easily prove validity, so we turn to a formal logic system called predicate
logic. We again use a system of derivation rules to build a proof sequence leading from the hypotheses to the conclusion. The rules should once more be truthpreserving, so that if in some interpretation, all the hypotheses are true, then the
conclusion will also be true in that interpretation. The system will then be correct
(only valid arguments will be provable). We also want the system to be complete
(every valid argument should be provable), yet at the same time the rule set should
be minimal.
Derivation rules for Predicate Logic
4
The equivalence rules and inference rules of propositional logic are still part of
predicate logic. An argument of the form
P ` (P S Q) S Q
is still valid by modus ponens, even if the wffs involved are predicate wffs.
eXAMPLe 25
Use predicate logic to prove the validity of the argument
(4x)R(x) ` [(4x)R(x) S (4x)S(x)] S (4x)S(x)
A proof sequence is
1. (4x)R(x)
hyp
2. (4x)R(x) S (4x)S(x) hyp
3. (4x)S(x)
1, 2, mp
However, there are many arguments with predicate wffs that are not tautologies but are still valid because of their structure and the meaning of the universal and existential quantifiers (see Example 24). The overall approach to proving
these arguments is to strip off the quantifiers, manipulate the unquantified wffs,
4 A complete list of derivation rules for propositional and predicate logic is given in Appendix A.