# A proof involving the Law of Excluded Middle

• Oct 22nd 2011, 07:02 PM
darthn
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
• Oct 23rd 2011, 08:19 AM
emakarov
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.
• Oct 23rd 2011, 09:14 AM
darthn
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:
http://img708.imageshack.us/img708/5...11023at113.png

``` 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```