Prove $\neg (p \land q) \vdash \neg p \lor \neg q$ by natural deduction I have tried solving this by negating $\neg p \lor \neg q$ to get to a pbc, but apparently you need to use a few lem's (law of excluded middle) to solve the problem. Where (and how) have I gone wrong in the following deduction? 


*

*$\neg(p \land q)$ .............................hyp


*$\neg(\neg p \lor \neg q)$ .................hyp



*$\neg p$ ........................hyp



*¬p ∨ ¬q ....... vIL, $3$

*$F$ ...................$\neg$E, $2$, $4$


*$\neg q$ ........................hyp



*$\neg p \lor \neg q$ .......$\lor$ER, $6$

*$F$...................$\neg$E, $2$, $7$



*$F$ .................................$\lor$E, $2$, $3-5$, $6-8$


*$\neg p \lor \neg q$ .............................pbc $2-9$
Any help would be greatly appreciated!
 A: Fairly close.    Always keep an eye on the prize.   You want to be able to contradict the first premise, $\lnot(p\land q)$, so that requires deriving $p$ and $q$, then introducing a conjunction.
Thus the purpose of those subproof are to be proofs by contradiction too. 
$$\def\bot{\mathcal F}\def\fitch#1#2{\quad\begin{array}{|l} #1\\\hline #2\end{array}}
\fitch{~~1.~\lnot(p\land q)}{\fitch{~~2.~\lnot(\lnot p\lor\lnot q)}{\\\fitch{~~3.~\lnot p}{~~4.~\lnot p\lor \lnot q\hspace{4ex}\lor\mathsf I, 3\\~~5.~\bot\hspace{9ex}\lnot\mathsf E,2,4}\\~~6.~p\hspace{13ex}\mathsf {PBC},3{-}5\\\\\fitch{~~7.~\lnot q}{~~8.~\lnot p\lor \lnot q\hspace{4ex}\lor\mathsf I, 7\\~~9.~\bot\hspace{9ex}\lnot\mathsf E,2,8}\\10.~q\hspace{13ex}\mathsf {PBC},7{-}9\\\\11.~p\land q\hspace{9ex}\land\mathsf I, 6,10\\12.~\bot\hspace{12ex}\lnot\mathsf E,1,11}\\13.~~\lnot p\lor\lnot q\hspace{9ex}\mathsf {PBC},2{-}12}$$

PS: The PBC steps contain the LEM, in the form of double negation elimination (DNE).
$$\begin{array}{|l}\fitch{~~3.~\lnot p}{~~4.~\lnot p\lor \lnot q\hspace{4ex}\lor\mathsf I, 3\\~~5.~\bot\hspace{9ex}\lnot\mathsf E,2,4}\\~~6.1.~~\lnot\lnot p\hspace{10ex}\neg\mathsf I, 3{-}5\\~~6.2.~p\hspace{13ex}\lnot\lnot\,\mathsf E,6.1\end{array}$$
A: The following proof is patterned on the one provided in section 19.6 of the forallx text as a proof of the first De Morgan rule. 

Note the use of the law of the excluded middle (LEM) on line 10 which references the two cases for $P$ on lines 2-7 and $¬P$ on lines 8-9.  The links to the proof checker and the textbook are provided below.

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/
P. D. Magnus, Tim Button with additions by J. Robert Loftis remixed and revised by Aaron Thomas-Bolduc, Richard Zach, forallx Calgary Remix: An Introduction to Formal Logic, Fall 2019. http://forallx.openlogicproject.org/forallxyyc.pdf
