Thread: 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

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.

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

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