It's simpler to have a direct proof rather than a proof by contradiction. You need to apply disjunction elimination (reasoning by cases) to . If holds, then p and so . The other case is similar.
Hi,
I am trying to answer the following exam question:
Let be .
Show that but that neither nor
(Note: this question is using Propositional logic)
My current attempt is this:
1. Given
2. Assume
3. Assume
4. Using "OR introduction"
5. Contradiction in lines 2 and 4
6. Derive using Reductio Ad Absurdum
7. Assume
8. Using "OR introduction"
9. Contradiction in lines 2 and 8
10. Derive using Reductio Ad Absurdum
11. Using "AND introduction"
I'm not sure where to go from here.
Can anyone help?
Thanks
I'm not sure if we're allowed to reason by cases in the exam.
The rules that we're allowed to use are:
1. (Given Statements Rule) Any may be deduced from in one step
2. (Top Rule) The statement may be deduced from any in one step
3. ( -Introduction) If and have been derived from then may be deduced from in one further step
4. ( -Introduction) If has been deduced from then either , may be deduced from in one further step
5. ( -Elimination) If has been deduced from the either or may be deduced from in one further step
6. ( -Elimination) If and have been deduced from then may be deduced from in one further step
7. ( -Elimination) If has been deduced from then may be deduced from in one further step
8. (Contradiction Rule) If and have been deduced from then may be deduced from in one further step
9. (Reductio Ad Absurdum Rule) If has been deduced from then may be deduced from in one further step
Using these rules, could you possibly suggest how to approach the proof?
Thanks
What you have listed as disjunction elimination is in fact disjunctive syllogism, or modus tollendo ponens. A more standard disjunction elimination rule has the form
(taken from the book "Proofs and Types" by Girard, Lafont, Taylor, p. 72). This rule can be simulated in your system as follows.
Numbers in parentheses indicate where corresponding assumptions have been closed. Now you can proceed using reasoning by cases.
I'm not too sure I understand what you said, but I think I may have derived a proof as follows:
1. Given
2. Assume15. by RAA
3. Assume6. by RAA
4. -Introduction
5. from lines 2 and 4
7. Assume10. by RAA
8. by -Elimination
9. from lines 6 and 8
11. by -Elimination on lines 1 and 10
12. by -Elimination
13. by -Introduction
14. from lines 2 and 13
How does this seem to you?
Thanks
Not bad. Strictly speaking, you need to first derive using RAA in step 15 and then derive using -Elimination.
I think that tree representations of derivations are much simpler to understand than Fitch-style text that you are using. One writes premises above the line and the conclusion below the line. For example, -Introduction looks like
I used vertical dots to hide some subderivations in post #4.
Your derivation can be simplified a little. In steps 2-9 you derive from and (left picture):
You can move the subderivation as the arrow shows to get a shorter derivation on the right. If the result is substituted into your complete derivation, then you get exactly the picture from post #4 where , and .