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

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.

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

Uploaded with ImageShack.us

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

Thank you

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