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

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?

• Do you know De Morgan's laws? – lightxbulb Jan 21 at 17:41
• @lightxbulb yes, it is what the sequent shows. – S0rin Jan 21 at 17:47
• What rules do you have? What proof system are you using? There are many different proof systems ..... – Bram28 Jan 21 at 19:45
• The statement isn't constructively true, so it is using LEM, so you may as well just learn how to do truth tables in whatever logic you are using. – DanielV Jan 21 at 21:34

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

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).