# Formal Proof for not (p or not q) implies not p and q

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.

• Does a truth-table counts as formal proof? – barak manos Nov 16 '16 at 22:09
• What is "Deductive System N" in your text? – Graham Kemp Nov 16 '16 at 22:10
• N represents the natural deduction system, and truth tables are not accepted – theycallmefm Nov 16 '16 at 22:10
• I meant: how is the natural deduction system defined by your texts? – 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.

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

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

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

and

$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 .