Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Help with an indirect proof (RAA)

  1. Jul 7, 2004 #1
    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!
  2. jcsd
  3. Jul 8, 2004 #2
    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:

    ->=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)

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook