= Solution
Under the negation of the desired disjunction, derive both negated propositions and contradict the premise. The <natural deduction> derivation is
$$
\begin{array}{rll}
1&\neg(\neg P\land\neg Q)&\text{premise}\\
2&\quad\neg(P\lor Q)&\text{assumption}\\
3&\qquad P&\text{assumption}\\
4&\qquad P\lor Q&\lor I\ 3\\
5&\qquad\bot&\neg E\ 4,2\\
6&\quad\neg P&\neg I\ 3\text{--}5\\
7&\qquad Q&\text{assumption}\\
8&\qquad P\lor Q&\lor I\ 7\\
9&\qquad\bot&\neg E\ 8,2\\
10&\quad\neg Q&\neg I\ 7\text{--}9\\
11&\quad\neg P\land\neg Q&\land I\ 6,10\\
12&\quad\bot&\neg E\ 11,1\\
13&P\lor Q&\mathrm{RAA}\ 2\text{--}12
\end{array}
$$
The proof uses <disjunction introduction>, <conjunction introduction> and the classical RAA rule; it does not silently replace the required derivation by a truth-table check.
Back to article page
