Prove that the following is a logical truth (tautology) using a natural deduction derivation: (B → C) ˅ (¬B → C)
How do I prove this using statement logic? I know I need to start with a supposition but don't know where to go from there
-
Are you sure you wrote this down correctly? You can't just add connectives where they don't belong. You wrote down one premise with no conclusion. How are you to do that? You would need a premise and a conclusion usually. Here you are to prove two distinct formulas are a tautology by your question but you combined them with connectives. I think you wrote it down incorrectly. Should it be (if b then c) is equivalent to (not b or c) ? That is a tautology & logically equivalent. Please check the writing. If it is written correctly then you need to say it is indeed written correctly so we know. – Logikal Oct 26 '20 at 4:21
-
Use Excluded Middle: ¬B or B – Mauro ALLEGRANZA Oct 26 '20 at 7:37
-
1@Logikal Bearers of truth needn't be conclusions of arguments. Propositions themselves express truths which is the foundation for establishing whether or not an argument is sound or cogent within the context of deduction and induction, respectively. – J D Oct 26 '20 at 19:12
-
As @MauroALLEGRANZA said, use the law of the excluded middle to conclude that one of B and ¬B must be true and the other must be false, then look at the truth table for material implication and see what you can conclude about a statement of the form P -> Q if you know for a fact that P is true, and also what you can conclude if you know for a fact that P is false. Hint: in one of those cases, the truth-value of P -> Q doesn't depend on whether Q is true or false. – Hypnosifl Oct 26 '20 at 21:41
Add a comment
|
A hint, rather than a full solution:
Start by assuming B
Prove ¬B → C
Prove (B → C) v (¬B → C)
Discharge your assumption to get: B → ((B → C) v (¬B → C))
Now assume ¬B
Prove B → C
Prove (B → C) v (¬B → C)
Discharge your assumption to get: ¬B → ((B → C) v (¬B → C))
Now use (or prove) the law of excluded middle to get: B v ¬B
Then use disjunction elimination to get (B → C) v (¬B → C)
There are two strategies for proving a disjunction: (1) directly prove one from the disjuncts, and (2) use an indirect proof.
We have no premises to work with, thus an indirect proof is indicated.
So start with the assumption that it is not true, then derive a contradiction. That is: A proof by reduction to absurdity.
|_
| |_ ¬((B → C) ˅ (¬B → C))
| | :
| | :
| | # Negation Elimination ... of what?
| ¬¬((B → C) ˅ (¬B → C)) Negation Introduction
| (B → C) ˅ (¬B → C) Double Negation Elimination
Since the only thing to contradict is the assumption, we should derive one of the disjuncts then use disjunction introduction to get that.
|_
| |_ ¬((B → C) ˅ (¬B → C))
| | :
| | B → C Derived Somehow
| | (B → C) ˅ (¬B → C) Disjunction Introduction
| | # Negation Elimination
| ¬¬((B → C) ˅ (¬B → C)) Negation Introduction
| (B → C) ˅ (¬B → C) Double Negation Elimination
Both the disjuncts, B→C and ¬B→C, are both conditionals, so we would derive one with a conditional proof. The only way to derive C under the assumption of one from the antecedents (say B) would be if we could derive a contradiction and explode it.
|_
| |_ ¬((B → C) ˅ (¬B → C))
| | |_ B
| | | :
| | | :
| | | # Negation Elimination ... of what?
| | | C Explosion (Ex Falso Quodlibet)
| | B → C Conditional Introduction
| | (B → C) ˅ (¬B → C) Disjunction Introduction
| | # Negation Elimination
| ¬¬((B → C) ˅ (¬B → C)) Negation Introduction
| (B → C) ˅ (¬B → C) Double Negation Elimination
Again the only thing to contradict are the assumptions. It seems like we are going in circles, but we are making actual progress.
|_
| |_ ¬((B → C) ˅ (¬B → C))
| | |_ B
| | | :
| | | :
| | | :
| | | :
| | | (B → C) ˅ (¬B → C) derived somehow
| | | # Negation Elimination
| | | C Explosion (Ex Falso Quodlibet)
| | B → C Conditional Introduction
| | (B → C) ˅ (¬B → C) Disjunction Introduction
| | # Negation Elimination
| ¬¬((B → C) ˅ (¬B → C)) Negation Introduction
| (B → C) ˅ (¬B → C) Double Negation Elimination
Indirect proofs of disjunctions usually look like this.
Completing this should not be too hard.
