Is this (tricky) natural deduction with De Morgan's laws correct?

Question

Just a practice question, however just wondering if this natural deduction proof is correct? I have put brackets in 2.2 and not in 2.3 however this shouldn't make a difference?

Answer 1

Your proof is wrong because the application of the rule $\lnot_E$ at step 2.4 is not correct.

I assume that the schema of the rule $\lnot_E$ is the following: \begin{equation} \frac{\lnot A \to B \quad \lnot A \to \lnot B}{A} \end{equation} (this is the way you have applied it at step 4). This schema is one of the possible formalizations of the classical law known as reductio ad absurdum.

At step 2.2 you have proved that $(\lnot P \land \lnot Q) \to \lnot(\lnot P \lor \lnot Q)$. At step 2.3 you have proved that $(\lnot P \land \lnot Q) \to (\lnot P \lor \lnot Q)$. But you cannot apply $\lnot_E$ at step 2.4 because $\lnot P \land \lnot Q$ is not a formula of the shape $\lnot A$.

Actually, at step 2.4 you can apply $\lnot_I$ and derive $\lnot (\lnot P \land \lnot Q)$, but this allow you at step 2 to conclude only that $\lnot (\lnot P \land \lnot Q) \to \lnot(P \land Q)$ (the same as you have proved at step 3).

Answer 2

1. ¬(P∧Q)          [premise]
2.1. ¬(¬P∨¬Q)      [assumption]
2.2.1. ¬P          [assumption]
2.2.2. ¬P∨¬Q       [∨intro 2.2.1]
2.2. ¬P→(¬P∨¬Q)    [→intro 2.2.1-2.2.2]
2.3.1. ¬P          [assumption]
2.3.2. ¬(¬P∨¬Q)    [restate 2.1]
2.3. ¬P→¬(¬P∨¬Q)   [→intro 2.3.1-2.3.2]
2.4. P             [RAA 2.2 2.3]
2.5.1. ¬Q          [assumption]
2.5.2. ¬P∨¬Q       [∨intro 2.5.1]
2.5. ¬Q→(¬P∨¬Q)    [→intro 2.5.1-2.5.2]
2.6.1. ¬Q          [assumption]
2.6.2. ¬(¬P∨¬Q)    [restate 2.1]
2.6. ¬Q→¬(¬P∨¬Q)   [→intro 2.6.1-2.6.2]
2.7. Q             [RAA 2.5 2.6]
2.8. P∧Q           [∧intro 2.4 2.7]
2. ¬(¬P∨¬Q)→(P∧Q)  [→intro 2.1-2.8]
3.1. ¬(¬P∨¬Q)      [assumption]
3.2. ¬(P∧Q)        [restate 1]
3. ¬(¬P∨¬Q)→¬(P∧Q) [→intro 2.1-2.8]
4. ¬P∨¬Q           [RAA 2 3]