32
Formal Logic
Deduction Method and other rules
Suppose the argument we seek to prove has the form
P 1 ` P 2 ` P 3 ` … ` P n S (R S S)
where the conclusion is itself an implication. Instead of using P 1 , … , P n as the hypotheses and deriving R S S, the deduction method lets us add R as an additional
hypothesis and then derive S. In other words, we can instead prove
P 1 ` P 2 ` P 3 ` … ` P n ` R S S
This change is to our advantage because it gives us one more hypothesis, i.e.,
additional ammunition for the proof, and it simplifies the desired conclusion.
The deduction method approach agrees with our understanding of implication, but Exercise 55 at the end of this section provides a formal justification.
ReMIndeR
Use the deduction method
when the conclusion of
what you want to prove is
an implication.
eXAMPLe 15
Use propositional logic to prove
[A S (A S B)] S (A S B)
Using the deduction method, we get two hypotheses instead of one, and we want
to derive B.
1. A S (A S B) hyp
2. A
hyp
3. A S B
1, 2, mp
4. B
2, 3, mp
pRaCtiCe 12 Use propositional logic to prove
(A S B) ` (B S C ) S (A S C )
The formal system we have described is correct and complete. Every argument we can prove is a tautology (the system is correct), and every implication that
is a tautology is provable (the system is complete). We can easily argue for correctness because each of the derivation rules is truth-preserving. Completeness would
be more difficult to prove, and we will not do so.
Correctness and completeness say that the set of derivation rules we have
used is exactly right—not too strong, not too weak. Nonetheless, many formal
systems for propositional logic use additional truth-preserving inference rules.
We can prove these additional rules using our original rule set. Once such a
rule is proved, it can be used as justification in a proof sequence because, if
required, the single step invoking this rule could be replaced with the proof
sequence for the rule. Nothing more can be proved by the addition of these
rules, but the proof sequences might be shorter. (See Exercises 1.2 for a list of
additional rules.)
Formal Logic
Deduction Method and other rules
Suppose the argument we seek to prove has the form
P 1 ` P 2 ` P 3 ` … ` P n S (R S S)
where the conclusion is itself an implication. Instead of using P 1 , … , P n as the hypotheses and deriving R S S, the deduction method lets us add R as an additional
hypothesis and then derive S. In other words, we can instead prove
P 1 ` P 2 ` P 3 ` … ` P n ` R S S
This change is to our advantage because it gives us one more hypothesis, i.e.,
additional ammunition for the proof, and it simplifies the desired conclusion.
The deduction method approach agrees with our understanding of implication, but Exercise 55 at the end of this section provides a formal justification.
ReMIndeR
Use the deduction method
when the conclusion of
what you want to prove is
an implication.
eXAMPLe 15
Use propositional logic to prove
[A S (A S B)] S (A S B)
Using the deduction method, we get two hypotheses instead of one, and we want
to derive B.
1. A S (A S B) hyp
2. A
hyp
3. A S B
1, 2, mp
4. B
2, 3, mp
pRaCtiCe 12 Use propositional logic to prove
(A S B) ` (B S C ) S (A S C )
The formal system we have described is correct and complete. Every argument we can prove is a tautology (the system is correct), and every implication that
is a tautology is provable (the system is complete). We can easily argue for correctness because each of the derivation rules is truth-preserving. Completeness would
be more difficult to prove, and we will not do so.
Correctness and completeness say that the set of derivation rules we have
used is exactly right—not too strong, not too weak. Nonetheless, many formal
systems for propositional logic use additional truth-preserving inference rules.
We can prove these additional rules using our original rule set. Once such a
rule is proved, it can be used as justification in a proof sequence because, if
required, the single step invoking this rule could be replaced with the proof
sequence for the rule. Nothing more can be proved by the addition of these
rules, but the proof sequences might be shorter. (See Exercises 1.2 for a list of
additional rules.)