Prove $\neg (p \land q) \vdash \neg p \lor \neg q$ by natural deduction

Question

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?

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

   2. $\neg(\neg p \lor \neg q)$ .................hyp
      3. $\neg p$ ........................hyp
         4. ¬p ∨ ¬q ....... vIL, $3$
         5. $F$ ...................$\neg$E, $2$, $4$
      4. $\neg q$ ........................hyp
         7. $\neg p \lor \neg q$ .......$\lor$ER, $6$
         8. $F$...................$\neg$E, $2$, $7$
   3. $F$ .................................$\lor$E, $2$, $3-5$, $6-8$

2. $\neg p \lor \neg q$ .............................pbc $2-9$

Any help would be greatly appreciated!

Answer 1

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}$$

Answer 2

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