1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Logic Problem in a Proof

  1. May 15, 2009 #1
    1. The problem statement, all variables and given/known data

    Prove or disprove:

    "If you can prove [tex] ( y \wedge \neg c ) \rightarrow Contradiction [/tex], then
    [tex] y \rightarrow c [/tex] must be right."


    2. Relevant equations

    My teacher used the sign [tex] \wedge [/tex], instead of [tex] \vee [/tex], like:

    "If [tex]( a \wedge b \wedge \neg c ) \rightarrow Contradiction [/tex], then [tex] a \wedge b \rightarrow c [/tex] must be right."

    I feel it is not right.

    3. The attempt at a solution

    I proved in my replies:

    "If you can prove [tex] ( a \wedge b \vee \neg c ) \rightarrow Contradiction [/tex], then
    [tex] a \wedge b \rightarrow c [/tex] must be right."

    I used the facts in my proof:

    [tex] a \wedge \neg b = \neg ( a \rightarrow b ) = ( a \not \rightarrow b ) \not = \neg b \rightarrow \neg a \not = \neg a \not \rightarrow \neg b[/tex]
     
    Last edited: May 16, 2009
  2. jcsd
  3. May 16, 2009 #2
    I'm pretty sure you're either missing something or else you have mistyped it. (*) does not follow from the two contradictions given.
     
  4. May 16, 2009 #3
    Let's simplify. I know for sure:


    [tex]\neg ( a \rightarrow b ) = a \wedge \neg b [/tex]

    So

    [tex]( a \rightarrow b ) = \neg a \vee b[/tex]

    If I want to prove [tex]( a \rightarrow b )[/tex], then the finding [tex] a \wedge \neg b \rightarrow Contradiction[/tex] will prove it. Please, notice that [tex] \neg ( a \rightarrow b ) \rightarrow Contradiction [/tex] because the two statements are equivalent. As [tex] \neg ( a \rightarrow b ) [/tex] and [tex] ( a \rightarrow b ) [/tex] cannot be true at the same time, the conclusion must be valid.


    Let's compare its logic to the logic in the case:
    We notice that the argument is:
    [tex]a \wedge b \rightarrow c = \neg ( a \rightarrow \neg b ) \rightarrow c [/tex]

    So [tex] \neg ( \neg ( a \rightarrow \neg b ) \rightarrow c ) \rightarrow Contradiction [/tex] must prove it, by the logic above this reply.

    Let's write its part differently:

    [tex] \neg ( \neg ( a \rightarrow \neg b ) \rightarrow c ) = \neg ( a \rightarrow \neg b ) \not \rightarrow c = a \wedge b \not \rightarrow c [/tex]

    So I need to find that:

    [tex] ( a \wedge b \not \rightarrow c ) \rightarrow Contradiction = ( \neg a \vee \neg b \rightarrow \neg c ) \rightarrow Contradiction[/tex]

    Let's call [tex] d = \neg a \vee \neg b [/tex]. So

    [tex] ( d \rightarrow \neg c ) \rightarrow Contradiction[/tex]

    Let's use again:

    [tex]( a \rightarrow b ) = \neg a \vee b[/tex]

    So it becomes:
    [tex] ( d \rightarrow \neg c ) \rightarrow Contradiction = ( \neg d \vee \neg c ) \rightarrow Contradiction [/tex]

    It is equivalent to:

    [tex] ( a \wedge b \vee \neg c ) \rightarrow Contradiction [/tex]

    Conclusion

    My teacher probably had something wrong. It should be right:

    [tex] ( a \wedge b \vee \neg c ) \rightarrow Contradiction [/tex]
     
    Last edited: May 16, 2009
  5. May 16, 2009 #4
    New Problem

    Prove [tex] a \vee b \rightarrow c [/tex]

    Conjecture, according to my last proof:

    "If you can prove [tex] ( a \vee b \vee \neg c ) \rightarrow Contradiction [/tex], then
    [tex] a \vee b \rightarrow c [/tex] must be right."

    It is similar to the last proof by contradiction:

    "If you can prove [tex] ( a \wedge b \vee \neg c ) \rightarrow Contradiction [/tex], then
    [tex] a \wedge b \rightarrow c [/tex] must be right."
     
    Last edited: May 16, 2009
  6. May 16, 2009 #5
    Re: New Problem

    Let's analyse them. Let [tex] p = a \vee b [/tex] and [tex] y = a \wedge b[/tex]. So the problems become:

    "If you can prove [tex] ( p \vee \neg c ) \rightarrow Contradiction [/tex], then
    [tex] p \rightarrow c [/tex] must be right."

    "If you can prove [tex] ( y \vee \neg c ) \rightarrow Contradiction [/tex], then
    [tex] y \rightarrow c [/tex] must be right."

    I think the problem is now solved, because you can see it is basically of the same form.
     
  7. May 16, 2009 #6
    Re: New Problem

    Does the following method work?

    "If you can prove [tex] ( y \wedge \neg c ) \rightarrow Contradiction [/tex], then
    [tex] y \rightarrow c [/tex] must be right."
     
    Last edited: May 16, 2009
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Logic Problem in a Proof
  1. Logic and Proofs (Replies: 4)

  2. Logical Proof (Replies: 5)

  3. Logical Proof (Replies: 2)

  4. Logic Proof (Replies: 1)

Loading...