Results 1 to 4 of 4

Math Help - A proof involving the Law of Excluded Middle

  1. #1
    Newbie
    Joined
    Oct 2011
    Posts
    2

    A proof involving the Law of Excluded Middle

    Good evening everyone,

    With regards to ((A & B) V nA) V nB, I found this sentence to be a tautology, where the LEM applies. I am trying to create a formal proof in Fitch to show that it is indeed a tautology, but don't know which direction to go in.

    Any help is greatly appreciated. Thank you

    ---
    & represents the conjunctive
    V the disjunctive
    n is negation
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,554
    Thanks
    785

    Re: A proof involving the Law of Excluded Middle

    If you are allowed to use the LEM, then this is easy. Do a disjunction elimination on A V ~A and then on B V ~B. In each of the four possibilities it is easy to derive the necessary conclusion.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2011
    Posts
    2

    Re: A proof involving the Law of Excluded Middle

    Hi emakarov,

    Thank you for that hint. I can obtain the same conclusions from the A and nA subproofs, as well as the B and nB ones, but I can't figure out how to link them together properly.

    Here is where I am stuck:


    Uploaded with ImageShack.us

    I'm sure it's something really simple, I'm just at a block!

    Thank you
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,554
    Thanks
    785

    Re: A proof involving the Law of Excluded Middle

    You need to do \/E on B \/ ~B inside the \/E on A \/ ~A.

    Code:
     1.  A \/ ~A                     LEM
     2.    A                         Hyp
     3.    B \/ ~B                   LEM
     4.      B                       Hyp
     5.      A /\ B                  /\I: 2, 4
     6.      (A /\ B) \/ ~A          \/I: 5
     7.      ((A /\ B) \/ ~A) \/ ~B  \/I: 6
     8.      ~B                      Hyp
     9.      ((A /\ B) \/ ~A) \/ ~B  \/I: 8
    10.    ((A /\ B) \/ ~A) \/ ~B    \/E: 4-7, 8-9, 3
    11.    ~A                        Hyp
    12.    (A /\ B) \/ ~A            \/I: 11
    13.    ((A /\ B) \/ ~A) \/ ~B    \/I: 12
    14.  ((A /\ B) \/ ~A) \/ ~B      \/E: 2-10, 11-13, 1
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Excluded middle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 17th 2011, 01:18 AM
  2. Is the Excluded Point Topology a scattered space?
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: June 8th 2011, 02:29 PM
  3. Formal proof of "Law of ecxluded middle"
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: May 23rd 2011, 04:05 PM
  4. Help! The middle value theorem
    Posted in the Differential Geometry Forum
    Replies: 12
    Last Post: December 15th 2009, 11:06 PM
  5. Middle day in a year
    Posted in the Algebra Forum
    Replies: 1
    Last Post: July 23rd 2007, 07:32 AM

Search Tags


/mathhelpforum @mathhelpforum