# Proving $C \vdash D \lor \neg D$ using natural deduction, and WITHOUT any additional hypotheses/assumptions?

I proved $(A \land \neg A) \vdash B$ by doing the following:

\begin{array}{l l l} 1. & A \land \neg A & (\text{premise}) \\ 2. & A & (1, \text{ simplification}) \\ 3. & A \lor B & (2, \text{ addition}) \\ 4. & \neg A \land A & (1, \text{ commutative property}) \\ 5. & \neg A & (4, \text{ simplification}) \\ 6. & B & (3, 5, \text{ disjunctive syllogism}) \end{array} I heard it's also possible to prove $C \vdash D \lor \neg D$ like this - without using any additional hypotheses or assumptions. Could you guys give me some hints?

My natural deduction has:

• modus ponens
• modus tollens
• hypothetical syllogism
• disjunctive syllogism
• constructive dilemma
• simplification $((p \land q) \vdash p)$
• conjunction $(p, q \vdash p \land q)$
• addition $(p \vdash p \lor q)$
• absorption $(p \supset q \vdash p \supset (p \land q))$
• de Morgan's rule
• commutative property
• associative property
• distributive property
• double negation
• transposition
• material implication
• material equivalence
• exportation
• tautology ($p$ can be replaced with $p \land p$ and also the other way / $p$ can be replaced with $p \lor p$ and also the other way)
• Please, note that the rules for Natural Deduction are different. – Mauro ALLEGRANZA Jul 6 '17 at 7:31
• This is not natural deduction. I wish authors would quit calling every little system they invent that. – DanielV Jul 6 '17 at 9:57

## 1 Answer

Got the little bugger!! Took me a while, but I figured Absorption was the key ... and it was!

\begin{array}{l l l } 1. & C & (\text{Premise})\\ 2. &C \lor \neg D &(\text{Addition} \ 1)\\ 3. &\neg D \lor C &(\text{Commutation} \ 2)\\ 4. &D \rightarrow C &(\text{Material Implication} \ 3)\\ 5. &D \rightarrow (D \land C) &(\text{Absorption} \ 4)\\ 6. &\neg D \lor (D \land C) &(\text{Material Implication} \ 5)\\ 7. &(\neg D \lor D) \land (\neg D \lor C) &(\text{Distribution} \ 6)\\ 8. &\neg D \lor D &(\text{Simplification} \ 7)\\ 9. &D \lor \neg D &(\text{Commutation} \ 8)\\ \end{array}

And by the way, as others have commented already, if all you have is these 19 rules I would be very hesitant to call that Natural Deduction ... while there is no exact one agreed upon definition of what makes something 'Natural Deduction', surely the ability to make assumptions is a 'natural' thing to do. Indeed, note how without it, this proof became anything but 'natural'!

• Was there anything that hinted you absorption was the key? I want to be able to think of proofs like this as well myself :( – L J K Jul 7 '17 at 16:50
• @LJK Let me first say that this was absolutely not your 'typical' proof, so if your goal is to get better at these proofs, my advice is not to pay any attention to this very proof at all. I have done many hundreds of proofs and had a hard time finding this one, while for most other proofs there are strategies that you learn to use and that work well. So this was an oddball, for sure! So again, my advice is to find a book or text that lays out a formal proof system (and preferably an actual 'Natural Deduction' system!), and that has many practice proofs. – Bram28 Jul 7 '17 at 17:07