Change things inside parentheses - Natural deduction

195 Views Asked by At

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

2

There are 2 best solutions below

0
On

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.

0
On

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?