Proving $ \lnot (A \Rightarrow B) \vDash A \land \lnot B $

Question

I need help trying to prove $$ \lnot (A \Rightarrow B) \vDash A \land \lnot B $$ in natural deduction.

I've come this far:

$$ \begin{array}{|l}\hline \lnot (A \Rightarrow B) \text{ premise} \\ ~~\begin{array}{|l}\hline B \text{ assumption} \\ ~~\begin{array}{|l}\hline A \text{ assumption} \\ B \text{ copy} \\\hline \end{array}\\ A \Rightarrow B \\ \bot \\\hline \end{array}\\ \lnot B \\ ~~\begin{array}{|l}\hline \lnot A \text{ assumption}\\\vdots\\\hline \end{array}\\\hline \end{array} $$

And then...?

Answer 1

1) $\lnot (A \to B)$ --- premise

2) $\lnot (A \land \lnot B)$ --- assumed [a]

3) $A$ --- assumed [b]

4) $\lnot B$ --- assumed [c]

5) $A \land \lnot B$ --- from 3) and 4) by $\land$-intro

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

7) $B$ --- from 4) and 6) by Double Negation-elim, discharging [c]

8) $A \to B$ --- from 3) and 7) by $\to$-intro, discharging [b]

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

10) $A \land \lnot B$ --- from 2) and 9) by Double Negation-elim, discharging [a].

Answer 2

If you assume $\neg A$ you should be able to prove that $A\Rightarrow B$. This can be done by deduction theorem, because if you assume $A$ you can prove $B$ by contradiction (and by deduction theorem you get $\neg A\vdash A\Rightarrow B$). Now with the assumption $\neg(A\Rightarrow B)$ you have a contradiction and can conclude that the assumption $\neg A$ was false or that $A$ is proven.

Answer 3

$ \lnot (A \Rightarrow B) \vDash A \land \lnot B $

Remember that we can write $(A \Rightarrow B)$ as $\lnot A \lor B$.

So we have $\lnot(\lnot A \lor B)$, and distributing the $\lnot$, we get $A \land \lnot B$, as wanted.

Answer 4

Your proof is so far so good!

So, to continue from:

$$\neg A \text{ Assumption}$$

$$\text{new box}$$

$$A \text{ Assumption}$$

$$\bot \text{ (from A and not A)}$$

$$B \text{ (from contradiction you can infer anything)}$$

$$\text{end box}$$

$$A \rightarrow B$$

$$\bot$$

$$\text{end box}$$

$$\neg \neg A$$

$$A$$

$$A \land \neg B$$

Answer 5

What you have to do is show that $\lnot (\lnot(A\to B)\to(A\land\lnot B))$ is a tautology. But the tableau of its negation is closed:

.

(Each path contains a contradiction.) Hence the result.