How to use natural deduction to show $\neg (P \land Q) \vdash \neg P \lor \neg Q$?

Question

How to use natural deduction to show $\lnot (P \land Q) \vdash \lnot P \lor \lnot Q$? I think I need to first assume $\neg(\neg P \lor \neg Q)$ and then find a contradiction but I cannot see how to do it. Can anyone help?

Answer 1

How to use natural deduction to show $¬(P∧Q)⊢¬P∨¬Q$? I think I need to first assume $¬(¬P∨¬Q)$ and then find a contradiction but I cannot see how to do it.

To show that assuming $\lnot(\lnot P\lor\lnot Q)$ contradicts the premise of $\lnot(P\land Q)$, you clearly need to show that that assumption entails $P\land Q$.

You can show $\lnot(\lnot P\lor\lnot Q)$ entails $P$ by reduction to absurdity.   Assume $\lnot P$, then use disjunction introduction, negation elimination, negation introduction (to discharge the assumption), and double negation elimination.

The rest should be obvious.   Here's the fitch style skeleton.

$$\def\fitch#1#2{\quad\begin{array}{|l} #1\\ \hline #2\end{array}}\fitch{\lnot(P\land Q)\hspace{10ex}\textsf{Premise}}{\fitch{\lnot(\lnot P\lor\lnot Q)\hspace{3ex}\textsf{Assumption}}{\fitch{\lnot P\hspace{9ex}\textsf{Assumption}}{\lnot P\lor\lnot Q\hspace{3ex}\textsf{Disjunction Introduction}\\\bot\hspace{10.5ex}\textsf{Negation Elimination}}\\\lnot\lnot P\hspace{11ex}\textsf{Negation Introduction}\\P\hspace{14ex}\textsf{Double Negation Elimination}\\\vdots }\\ \vdots\\\lnot P\lor\lnot Q}$$

Answer 2

The following is a derivation in natural deduction proving that $\lnot(P \land Q) \vdash \lnot P \lor \lnot Q$. The notation $[A]^*$ marks an assumption discharged by the inference rule $*$. \begin{align} \dfrac{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\dfrac{[\lnot(\lnot P \lor \lnot Q)]^* \quad \dfrac{\dfrac{\dfrac{\lnot(P \land Q) \quad \dfrac{[P]^+ \quad \dfrac{\dfrac{[\lnot(\lnot P \lor \lnot Q)]^* \quad \dfrac{[\lnot Q]^{**}}{\lnot P \lor \lnot Q}\lor_{i_2}}{\bot}\lnot_e\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}{Q}\text{raa}^{**}\!\!\!\!\!\!\!\!\!\!\!\!\!\!}{P \land Q}\land_i\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}{\bot}\lnot_e}{\lnot P}\lnot_i^+}{\lnot P \lor \lnot Q}\lor_{i_1}\!\!\!\!\!\!\!\!}{\bot}\lnot_e\!\!\!\!\!\!\!\!\!\!\!}{\lnot P \lor \lnot Q}\text{raa}^* \end{align}

The idea is a reasoning by contradiction: in addition to the hypothesis $\lnot (P \land Q)$, we suppose $\lnot (\lnot P \lor \lnot Q)$ (the negation of what we want to prove) and we show that this leads to a contradiction. More precisely, we show that $P \land Q$ follows from $\lnot (\lnot P \lor \lnot Q)$, which contradicts our hypothesis $\lnot (P \land Q)$. To show this, we need some additional assumptions ($\lnot Q$ and $P$), which we can discharge at the right moment: this complicates a bit the reasoning.

Note the application of the inference rule raa (reductio ad absurdum), used twice. Actually, $\lnot(P \land Q) \vdash \lnot P \lor \lnot Q$ cannot be proved without this rule (or another inference rule equivalent to it).