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)
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'!