# Natural deduction, from premise: $\,\lnot p \lor \lnot q,\,$ to conclusion : $\,\lnot(p \land q)$

What's the natural deduction of this exercise?

Premise: $\lnot p \lor \lnot q$
Conclusion: $\lnot(p\land q)$

I must have something like the following, but I do not know how to start.

Proof sketch:

1. $\lnot p \lor \lnot q$ (premise)

2. $\quad |\underline{\text{(Assume)}\; p\land q}\;$ (Assumption)

3. $\quad |\;p\;$ ("$\land$-elimination")

4. $\quad |\; q\;$ (simplification/$\land$-elimination)

5. $\qquad |\underline{\;\; \lnot p\;}$ (assumption)

6. $\qquad | \;\;p \land \lnot p\;$ $\land$-Intro (3, 6)

7. $\qquad | \;\;$ Contradition. (6)

8. $\qquad | \underline{\;\; \lnot q\;}$ (assumption)

9. $\qquad | \;\;q\land \lnot q\;\;\land$-Intro (4, 8)

10. $\qquad | \;\;$Contradiction (9)

11. $\quad |\;\;$ Contradiction $\lor$-Elimination (1, 5-10)

12. $\lnot (p\land q)$ (2-10). Our assumption $p\land q$ leads to a contradiction, so that $\lnot(p \land q)$ is therefore true.

• Sophie, the last step, 12 (conclusion) is justified by "negation introduction". – Namaste Aug 6 '14 at 14:40