natural deduction proof with De Morgan's laws

3.5k Views Asked by At

Struggling with this proof, any strategies for natural deduction?

$¬(P \land Q) \vdash ¬P \lor ¬Q$

1

There are 1 best solutions below

0
On BEST ANSWER

1) $\lnot (P \land Q)$ --- premise

2) $\lnot (\lnot P \lor \lnot Q)$ --- assumed [a]

3) $\lnot P$ --- assumed [b]

4) $\lnot P \lor \lnot Q$ --- from 3) by $\lor$-intro

5) $\bot$ --- from 2) and 4)

6) $P$ --- from 3) and 5) by RAA, discharging [b]

7) $\lnot Q$ --- assumed [c]

8) $\lnot P \lor \lnot Q$ --- from 7) by $\lor$-intro

9) $\bot$ --- from 2) and 8)

10) $Q$ --- from 7) and 9) by RAA,discharging [c]

11) $P \land Q$ --- from 6) and 10) by $\land$-intro

12) $\bot$

13) $\lnot P \lor \lnot Q$ --- discharging [a].