Results 1 to 6 of 6

Math Help - Formal proof (using Fitch Format) with an OR

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    31

    Formal proof (using Fitch Format) with an OR

    I want to prove that

    A /\ (B V C) => (A /\ B) V (A /\ C)

    using the Fitch system.

    I have done the following:

    1. A /\ (B V C)
    ------
    2. A /\ Elim : 1
    3 B V C /\ Elim: 1
    4. B
    -----
    5. A /\ B /\ Intro: 2, 4

    6. C
    -----
    7. A /\ C /\ Intro: 2, 6

    8. (A /\ B) V (A /\ C) V Intro : 3, 4-5, 6-7


    Can I do step 8)? Or am I cheating here? How should I do this?

    From what I've read on Logic and Proof, it gave me the impression that you must always conclude the same thing in all "paths" of the OR. I am not doing that, so that is why I'm a bit confused on how to approach this.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    I'm assuming 4-5 is a subproof, as is 6-7. You should use some sort of indentation to do Fitch subproofs. I realize it's difficult here. I use multiple periods with spaces in-between (see here for an example) to indicate indentation.

    My thoughts:
    1. The rule you're citing for Step 8 is incorrect. It should be OR elimination (which is the "By Cases" inference rule).
    2. Step 8 is not technically valid as yet, but your proof can be made valid by just including two more lines inserted in the right place. Hint: try OR intro.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    31
    OK. I think I did it. Here is another similar one:

    I have:
    1. B /\ C
    2. ~B V ~C V D
    -----
    2. B
    3. C

    4. ~B
    -----
    5. _|_

    6. ~C
    -----
    7. _|_

    8. D
    -----
    (here I want to be able to conclude D, but I can't with V Elim as all "paths" from the V should return the same thing! How am I to prove this?)

    From the 2 initial premisses, I want to prove that D follows from them. Am I taking a wrong approach here?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    I'm totally lost. What are you trying to prove?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2009
    Posts
    31
    that D follows from B /\ C and ~B V ~C V D

    edit: I actually did it. All I had to do was assume ~D and then do an OR Elim, which would yield a contradiction, thus proving D.

    Could you take a look at this twin thread, http://www.mathhelpforum.com/math-he...tch-v-b-b.html ? Thanks
    Last edited by devouredelysium; June 29th 2010 at 02:01 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Yes, you can do that. Also don't forget that you can derive anything from a contradiction. That is most useful in cases like this.

    Moving over to your other thread...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 9
    Last Post: December 10th 2011, 02:23 PM
  2. Formal proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 18th 2011, 01:05 PM
  3. Formal Proof
    Posted in the Geometry Forum
    Replies: 1
    Last Post: May 30th 2011, 02:12 PM
  4. formal proof of set
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 6th 2010, 11:36 PM
  5. Formal Proof
    Posted in the Calculus Forum
    Replies: 0
    Last Post: November 12th 2008, 03:43 PM

Search Tags


/mathhelpforum @mathhelpforum