1
$\begingroup$

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

$\endgroup$
4
  • 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

3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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