I've been trying to give a formal proof for $$ \lnot \left(p \lor \lnot q\right) \rightarrow \left(\lnot p \land q \right) $$

in deductive system N (natural deduction system) and got stuck. I've started by assuming $$A1 \Rightarrow\lnot \left(p \lor \lnot q\right) $$

and tried to prove by contradiction with $$A2 \Rightarrow \left(p \lor \lnot q\right) $$ but got stuck. Am I looking at this problem from the wrong point of view? Any assistance will be appreciated.

  • $\begingroup$ Does a truth-table counts as formal proof? $\endgroup$ – barak manos Nov 16 '16 at 22:09
  • $\begingroup$ What is "Deductive System N" in your text? $\endgroup$ – Graham Kemp Nov 16 '16 at 22:10
  • $\begingroup$ N represents the natural deduction system, and truth tables are not accepted $\endgroup$ – theycallmefm Nov 16 '16 at 22:10
  • $\begingroup$ I meant: how is the natural deduction system defined by your texts? $\endgroup$ – Graham Kemp Nov 17 '16 at 2:45

1) $¬(p∨¬q)$ --- premise

2) $p$ --- assumed [a]

3) $p∨¬q$ --- by $\lor$-intro

4) $\bot$ --- contradiction from 1) and 3)

5) $\lnot p$ --- from 4), discharging [a]

6) $\lnot q$ --- assumed [b]

7) $p \lor \lnot q$ --- by $\lor$-intro

8) $\bot$ --- contradiction from 1) and 7)

9) $q$ --- from 6) and 8) by double Negation, discharging [b]

10) $\lnot p \land q$ --- from 5) and 9) by $\land$-intro

$¬(p∨¬q) \to (\lnot p \land q)$ --- from 1) and 10 by $\to$-intro.

  • $\begingroup$ Thanks a lot! I have been trying to wrap my head around this for a long time. $\endgroup$ – theycallmefm Nov 16 '16 at 22:23

I hope i didnt make any mistakes there (I've added an image with my solution).

enter image description here


Let $S=\lnot(p \lor \lnot q)$


$R=\lnot p \land q.$

we want to prove that $S\implies R$

which is equivalent to $\lnot S \lor R$.

$\lnot S \lor R \iff$

$(p \lor \lnot q) \lor R \iff$

$(p \lor R) \lor (\lnot q \lor R) \iff$

$(p \lor (\lnot p \land q)) \lor (\lnot q \lor (\lnot p \land q)) \iff$

which is always true .


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.