|Jul7-04, 12:40 PM||#1|
Help with an indirect proof (RAA)
I was hoping that I could get some help with an indirect proof we are doing in my logic class. It is an introductory class, and this was a homework question that I couldn't get. This isn't course-work that is graded, it is just practice for our exam that is tomorrow! I asked it in class today and the professor worked on it for about 45 minutes but he couldn't get it. He and I are both sure that it is something very simple that we aren't catching.
Here it is: (I will use = to show equivalence, and > to show implication).
1. (R*S) = (G*H)
2. R > S
3. H > G
The point is to use Reductio ad Absurdum (RAA) to solve this. We can use the 18 Rules of Inference (and Replacement), and also conditional proofs.
Here is one pathway I took that did not steer me towards the answer:
4. ~(R=H) by AP (first thing for the RAA)
5. [(R*S) > (G*H) * [(G*H) > (R*S)] by Equiv 1
6. (R*S) > (G*H) by Simp 5
7. (G*H) > (R*S) by Simp 5
8. ~[(R*H) v (~R*~H)] by Equiv 4
9. ~(R * H) * ~(~R * ~H) by DM 8
10. (~Rv~H) * ~(~R*~H) by DM 9
11. (~R v ~H) by Simp 10
12. ~(~R*~H) by simp 10
13. (RvH) by DM 12
14. (SvG) by CD(2,3,13)
Perhaps there is something to the constructive delimma that is set up on line 14? Also, it seems that I will have to at some point use a conditional proof or something to assume a sentence letter, or something, because I don't see how I can show the contradiction (we do the A*~A on the same line thing) without having some sentence letter to prove another?
I dunno, this should be really easy because this is a basic logic book (A Concise Introduction to Logic by Hurley) and a basic class, and the rest of the proofs are very easy in this section. But this one .. We couldn't get it. Does anyone have a suggestion?
|Jul8-04, 04:01 AM||#2|
->=the implication sign
~=the negation sign
=the equivalence sign
Lets' assume that ~(H=R) is true=1
We have H=R equivalent with (R->H)*(H->R)
Applying de Morgan's law ~(A*B)=~A \/ ~B --->
~(H=R)=~[(R->H)*(H->R)] =[~(R->H)] \/ [~(H->R)]
[~(R->H)] \/ [~(H->R)]=[~(~R \/ H)] \/ [~(~H \/ R)]
By applying again one of de Morgan's laws ~(A \/ B) = ~A * ~B --->
[~(~R \/ H)] \/ [~(~H \/ R)]=(R*~H) \/ (H * ~R)
(R* (~H)) \/ (H * (~R))=(R \/ H) * (R \/ ~R) * (~H \/ H) * (~H \/ ~R)
(R \/ ~R) and (~H \/ H) are tautotologies (their truth value is always 1)
(R \/ H) * (~H \/ ~R) is 1 only if H is different from R.
Therefore if ~(H=R) is true then H is different from R.
Now if we choose R=1 we have H=0
Next from R->S we have that S=1 and from H -> G we have that G is either 0 or 1 (not important anyway).
Thus (R*S)=1 and (G*H)=0.This is a contradiction with the premise that always R*S=G*H therefore ~(R=H) is false and R=H (in the virtue of excluded middle principle) is true.
|Similar Threads for: Help with an indirect proof (RAA)|
|Indirect Maximizing||Calculus & Beyond Homework||6|
|Indirect Proof||Precalculus Mathematics Homework||2|
|Indirect Proof||Calculus & Beyond Homework||5|
|Indirect Proofs||Precalculus Mathematics Homework||4|
|Indirect Proof (Logic question)||Set Theory, Logic, Probability, Statistics||6|