Help with an indirect proof (RAA)

aychamo

Hey guys;

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

Conclusion: R=H

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?

Thank you!
AYCHAMO

metacristi

There is a simple solution using de Morgan laws and the definiton of implication (A->B is equivalent with (~A \/ B),if you are allowed to use them then my proposal might be of help:

*=AND
->=the implication sign
\/=OR
~=the negation sign
=the equivalence sign

Lets' assume that ~(H=R) is true=1

We have H=R equivalent with (R->H)*(H->R)

Thus ~(H=R)=~[(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.