# Change things inside parentheses - Natural deduction

$$\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
$$\bot$$
$$\neg B$$
$$A\to \neg B$$
$$\bot$$
$$\neg A\to \bot$$
$$A$$

• Hint: $A\to\neg B$ is same with $\neg A \lor \neg B$. Sep 26, 2021 at 1:11
• Thank you! But I know that, my only problem is to prove it using natural Deduction. More precisely prove that B is True. @zkutch Sep 26, 2021 at 1:22
• Your premise is all left hand side, not only $A$. Sep 26, 2021 at 1:37
• 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). Sep 26, 2021 at 15:57

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?
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, \landI}\\ \{2, 3\} &5. &B &\text{4, \landE}\\ \{2\} &6. &A\to B & \text{(3), 5, CP}\\ \{1, 2\} &7. &(A\to B)\land\lnot(A\to B) &\text{1, 6, \landI}\\ \{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.