Is law of excluded middle necessary in this proof

logicnatural-deductionproof-theorypropositional-calculus

I'm currently learning natural deduction and here is my question.

Is it possible to prove this
$\vdash \neg(P \land Q)\rightarrow (\neg P \lor \neg Q)$
without referring to the law of excluded middle ?

More precisely, using only the following set of inference rules. These rules are being introduced in the book logic: the laws of truth Page 410.
I assume these rules are complete and have tried a long time , however, still cannot come up with a correct derivation without referring to the law of excluded middle which is not included in the following rules.
enter image description here

Best Answer

There is already a good answer about how the implication can be achieved with the rules you gave. This answer is for the initial question about the link to the law of excluded middle.

The implication in the question is exactly the part of De Morgan's laws that does not hold in intuitionistic logic, see also this question.

If the implication were to hold, then we would clearly have that a weaker version of the law of the excluded middle is true: $\neg P \vee \neg \neg P$. To see this, simply substitute $\neg P$ for $Q$ and note that $\neg (P \wedge \neg P)$ is trivially true.

The weak law of excluded middle is actually exactly what we would need to prove the implication from the question. That is, we do not need the full law of excluded middle, just $\neg P \vee \neg \neg P$. In particular the implication from the question is equivalent to the weak law of excluded middle. I will give a written proof, if you want you can try to formalise it in a deduction-system.

We assume $\neg (P \wedge Q)$ and also $\neg P \vee \neg \neg P$ and $\neg Q \vee \neg \neg Q$. So we can perform a proof by cases:

  1. If we have $\neg P$ or we have $\neg Q$, then we directly get $\neg P \vee \neg Q$.
  2. If we have $\neg \neg P$ and $\neg \neg Q$, then we have $\neg \neg P \wedge \neg \neg Q$. This is equivalent to $\neg \neg (P \wedge Q)$. So we get a contradiction with $\neg (P \wedge Q)$, and our result follows from the principle of explosion.
Related Question