by Brian Bosse, Copyright May 01, 2010, all rights reserved.
In the last post we looked at a direct derivation (DD) in the propositional calculus. In this post we will consider an indirect derivation (ID). ID is based on the idea that if φ leads to a contradiction, then φ cannot be, and if φ cannot be, then ¬φ is the case. It is rooted in the law of non-contradiction and the law of excluded middle, which are as follows…
Law of Non-Contradiction (LCN): Something cannot be both A and not-A at the same time and in the same relationship.
Law of Excluded Middle (LEM): You either have A or not-A.
So, here is the reasoning:
If B leads to both A and not-A, and you cannot have both A and not-A (LCN), then you cannot have B. If you cannot have B, then by LEM you have not-B. As such, this line of reasoning can be used to establish not-B indirectly by assuming B, and from this deriving a contradiction. In other words, if one assumes B and arrives at a contradiction, then not-B has been established. Let’s visit again the following argument…
Premise 1: If Socrates did not die of old age, then the Athenians condemned Socrates to death.
Premise 2: The Athenians did not condemn Socrates to death.
Show: Socrates did die of old age.
To begin, we need to translate this argument into symbolic sentences. Here is the translation…
P: Socrates did die of old age.
Q: The Athenians condemned Socrates to death.
Premise 1: ¬P → Q
Premise 2: ¬Q
Show: P
Now, in our previous post we proved this very argument directly by using MT. This time we are not going to use MT, but rather we will use ID.
1. Show P [ID]
Since we want to prove P by the ID method, we will assume ¬P and attempt to derive a contradiction. Since our assumption is not a premise or does not follow directly from an inference rule, but only is being assumed “for the sake of the argument,” we will indicate this by indenting the line.
2. Assume ¬P [Assumption for ID]
At this point we introduce our first premise…
3. ¬P → Q [Premise 1]
(Technically, 3 does not need to be indented as our assumption was. However, I want to use 3 within the framework of our assumption, and as such have indented it. The same can be said for 5 below.)
From here we can now apply an instance of MP on 2 and 3…
4. Q [MP – 2 and 3]
We now introduce our second premise…
5. ¬Q [Premise 2]
We have derived our contradiction (lines 4 and 5), and by the reasoning of ID we have established what we set out to prove. We can now cross through ‘Show’ in line 1. Here is the full proof…
1.ShowP [ID] 2. Assume ¬P [Assumption for ID] 3. ¬P → Q [Premise 1] 4. Q [MP – 2 and 3] 5. ¬Q [Premise 2] Q.E.D.
Posted in Logic • 0 Comments • Permalink • 622 views
by Brian Bosse, Copyright May 01, 2010, all rights reserved.
There are three types of derivations that we will use in our propositional calculus: (1) Direct Derivation (DD), (2) Conditional Derivation (CD), and (3) Indirect Derivation (ID). The following is a proof in the propositional calculus using the direct derivation method.
Premise 1: If Socrates did not die of old age, then the Athenians condemned Socrates to death.
Premise 2: The Athenians did not condemn Socrates to death.
Show: Socrates did die of old age.
To begin, we need to translate this argument into symbolic sentences. Here is the translation…
P: Socrates did die of old age.
Q: The Athenians condemned Socrates to death.
Premise 1: ¬P → Q
Premise 2: ¬Q
Show: P
To begin our proof we begin with what it is we are trying to show. As such, our first line is…
1. Show P [DD]
At this point we will list our two premises…
2. ¬P → Q [Premise 1] 3. ¬Q [Premise 2]
We now consider what inference rules we can use, and see that MT can be applied to 2 and 3. If we let φ stand for ¬P and ψ stand for Q, then by MT we can conclude ¬ φ, which when we translate back is ¬¬P. This is our line 4.
4. ¬¬P [MT – 2 and 3]
We now are able to apply the rule of DN to line four and get…
5. P [DN – 4]
At this point we have derived P from our premises, and as such have shown P. To indicate this we put a line through ‘Show’ in line 1. This would be the full proof…
1.ShowP [DD] 2. ¬P → Q [Premise 1] 3. ¬Q [Premise 2] 4. ¬¬P [MT – 2 and 3] 5. P [DN – 4] Q.E.D.
This is considered a direct derivation because each line follows directly from previous lines (with the exception of the first line). Note: the brackets next to each line are not part of the propositional calculus. They simply are an aid to the reader to show which rule is being used to account for the symbolic sentence. Also, ‘Q.E.D.’ stands for the Latin phrase “quod erat demonstrandum,” which means, “which was to be demonstrated.”
Posted in Logic • 0 Comments • Permalink • 784 views
by Brian Bosse, Copyright April 20, 2010, all rights reserved.
The following are four inference rules we shall use with the propositional calculus. We will add more rules as we introduce the different sentential connectives. (It is assumed throughout that both φ and ψ represent symbolic sentences.)
1. Modus Ponens (MP): If one has both (φ → ψ) and φ, then one may conclude ψ.
Premise 1: If you believe, then you will be saved.
Premise 2: You believe.
If we let A stand for “you believe” and B stand for “you will be saved”, then we can symbolize the above premises as follows…
Premise 1: (A → B)
Premise 2: A
By the rule of MP we can conclude…
Conclusion: B (You believe.)
2. Modus Tollens (MT): If one has both (φ → ψ) and ¬ ψ, then one may conclude ¬φ.
Premise 1: If you believe, then you will be saved.
Premise 2: It is not the case you will be saved.
If we let A stand for “you believe” and B stand for “you will be saved”, then we can symbolize the above premises as follows…
Premise 1: (A → B)
Premise 2: ¬B
By the rule of MT we can conclude…
Conclusion: ¬A (It is not the case you believe.)
3. Double Negation (DN): If one has ¬¬φ, then one may conclude φ; or, if one has φ, then one may conclude ¬¬φ.
4. Repetition (R): If one has φ, then one may conclude φ.
We have simply asserted these four rules; although, we did provide some justification for MP and MT by referring to their use in the Bible. Hopefully, these rules are all intuitively obvious to the reader.
Posted in Logic • 0 Comments • Permalink • 458 views
Page 2 of 4 pages < 1 2 3 4 >