$\neg (A \to \neg B) \vdash (A \land B) $
I successfully prove A, but I'm having problems to proof B. I don't know if I'm allowed to do that in natural deduction:
$\neg (A \to \neg B)$
$\neg (\neg B)$ ( Since I've already proved A )
Then $B$. But I think that I'm not allowed to do that because of the parentheses, is that right?

My proof of A:
$\neg A $ hip
$A$ hip
$\neg B$
$A\to \neg B$
$\neg A\to \bot$

  • 1
    $\begingroup$ Hint: $A\to\neg B$ is same with $\neg A \lor \neg B$. $\endgroup$
    – zkutch
    Sep 26, 2021 at 1:11
  • $\begingroup$ Thank you! But I know that, my only problem is to prove it using natural Deduction. More precisely prove that B is True. @zkutch $\endgroup$
    – Vithor
    Sep 26, 2021 at 1:22
  • $\begingroup$ Your premise is all left hand side, not only $A$. $\endgroup$
    – zkutch
    Sep 26, 2021 at 1:37
  • $\begingroup$ You have (¬A→⊥), and inferred A. You can also infer (¬B→⊥) from what you have, and thus conclude B. Then, you'll have (A∧B). $\endgroup$ Sep 26, 2021 at 15:57

2 Answers 2


No, there is no rule that allows you to infer $\neg \neg B$ from $\neg(A \to \neg B)$ in one step. But you can derive it in several steps: Assume $\neg B$, then you can do an implication introduction to conclude $A \to \neg B$. (You don't need to have the assumption $A$ actually occur in the derivation in order for the rule to be applicable.) Can you figure out how to close the bridge to $\neg \neg B$ from here?


Without knowing what deduction system you're using or whether you're allowed to make use of derived rules, it's quite difficult to give you a proper answer.

In general, when you're asked to prove a conjunction you need to prove each conjunct separately and conjoin them. This tends to be done via reductio. In the following example I've proved $\lnot(A\to B)\vdash\lnot B$ (the proof of $\lnot(A\to B)\vdash A\land\lnot B$ is left as an exercise).

$\begin{array}{} \{1\} &1. &\lnot(A\to\ B) & \text{P}\\ \{2\} &2. &B &\text{A for RAA}\\ \{3\} &3. &A &\text{A for CP}\\ \{2, 3\} &4. &A\land B &\text{2, 3, $\land$I}\\ \{2, 3\} &5. &B &\text{4, $\land$E}\\ \{2\} &6. &A\to B & \text{(3), 5, CP}\\ \{1, 2\} &7. &(A\to B)\land\lnot(A\to B) &\text{1, 6, $\land$I}\\ \{1\} &8. &\lnot B &\text{(2), 7, RAA}\\ \end{array}$

Of course, if you're allowed to make use of derived rules like De Morgan's and $(A\to B)\dashv\vdash (\lnot A\lor B)$, then the proofs can be vastly simplified. I'll leave that to you to experiment with.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .