# natural deduction proof

Need help with the steps for natural deduction:

P1. $(A \rightarrow B) \rightarrow (C \rightarrow A)$

P2. $A \wedge (C \leftrightarrow B)$

P3. $(A \lor C) \to (A \to B)$

$\therefore B \vee A$

1. $\neg(B \lor ~I) \to (\neg L \text{ & } J)$
2. $\neg L \to (M \text{ & } B)$
3. $\neg (B \lor \neg I)$ $\therefore M \lor E$
4. $\neg L \text{ & } J$ $1,3$, $MP$
5. $\neg L$ $4,$ Simp
6. $M \text{ & } B$ $2,5, MP$
7. $M$ $6$, Simp
8. $M \lor E$ $7$, Add
• What are your deduction rules? – Git Gud Oct 7 '14 at 8:44
• Prove the following argument to be valid using the method of Natural Deduction. similar to the way the other problem underneath is worked out. – user179905 Oct 7 '14 at 8:45
• You didn't answer my question. Some of your deduction rules seem to be MP, Simp and Add, but these rules can vary. In order to get an appropriate answer, you must specify your rules. – Git Gud Oct 7 '14 at 8:47
• Rules are MP ( Modus Ponens), Simp (Simplication), Add (Addition), HS , Conj(Conjuction), DS (Disjuncitve syllogism), MT, CD (Constructive Dilema), Comm, Dist, Assoc, DM (DeMorgan's rule). did that answer your question. – user179905 Oct 7 '14 at 8:56
• Well, technically you did answer the question, but I don't know what these names refer to, but that's just me. In any case, judging by the example you provided, this is a two step proof using first Simp and then Add. – Git Gud Oct 7 '14 at 8:58

With Natural Deduction :

i) $A \land (C \leftrightarrow B)$ --- premise 2.

ii) $A$ --- from i) by $\land$-elimination (or Simplification)

iii) $A \lor B$ --- from ii) by $\lor$-introduction (or Addition)

Thus, from i) and iii) :

$A \land (C \leftrightarrow B) \vdash A \lor B$

(I've used the "turnstile" : $\vdash$ to denote the relation of derivability; thus $\Gamma \vdash \psi$ means that there is a derivation of the formula $\psi$ from the set of formulae $\Gamma$.)

The above derivation needs only premise 2; thus the same derivation holds with the three premises 1-3 :

$(A \rightarrow B) \rightarrow (C \rightarrow A), A \land (C \leftrightarrow B), (A \lor C) \rightarrow (A \rightarrow B) \vdash A \lor B$

• I dont understand it with the symbols you used. – user179905 Oct 7 '14 at 9:06
• Why the down vote? – Git Gud Oct 8 '14 at 15:02

Goal: to prove $B\lor A$ from premises $(1-3)$.

1. $(A \rightarrow B) \rightarrow (C \rightarrow A)$

2. $A \land (C \leftrightarrow B)$

3. $(A \lor C) \rightarrow (A \rightarrow B)$

We actually need only premise $(2)$.

1. $A \land (C\leftrightarrow B)\quad$ (given premise)

2. $A\quad\quad$ (from (2): $\land$-elimination, aka simplification)

3. $A \lor B \quad$ (from (3): $\lor$-Introduction, aka addition)

4. $B\lor A\quad$ (By commutativity of $\lor$)

Hence, from the given premises (in particular, given premise $(2)$), we have derived $B\lor A$, as desired.

Note that you just need one from your three premises, namely, the premise two:

$A \wedge (C \leftrightarrow B)$

From this we can use the $\wedge E$ and "detach" $A$ from it:

$\frac{A \wedge (C \leftrightarrow B)}{A}(\wedge E)$

Then we simple we the disjunction introduction rule in order to get $A \vee B$:

$\frac{\frac{A \wedge (C \leftrightarrow B)}{A}(\wedge E)}{A \vee B}(\vee I)$

This shows that $(A \rightarrow B) \rightarrow (C \rightarrow A),A \wedge (C \leftrightarrow B), A \wedge (C \leftrightarrow B) \vdash A \vee B$ as required.

In the derivation above we procceded by natural deduction. In this deduction system as you can see that the premises $(A \rightarrow B) \rightarrow (C \rightarrow A)$ and $A \wedge (C \leftrightarrow B)$ here are superfluous, but the fact our proof did not require their use does not imply they cannot be used as hypothesis: superfluous information can always be added.