# How do I build a proof in natural deduction?

I know all the rules but I don't know how make assumptions and build a proof in general.

Example : prove : $((A \rightarrow B) \wedge(C \rightarrow B))\rightarrow(A \wedge C)\rightarrow B$

I'm only able to do these 2 steps :

$\frac{(A \wedge B)}{B} \frac{(A ),( C)}{(A \wedge C)}$

I don't know how to build the $\rightarrow$'s using the $\rightarrow$ introduction rule.

Let's try it again :

$1. [(A \rightarrow B)\wedge(C \rightarrow B)]$

$2. (A \wedge C),B$

$3. B$ is it correct?

• Maybe you must add a couple of parenthesis to improve readibility. – Mauro ALLEGRANZA Feb 6 '18 at 14:29
• Start assuming the antecedent: $((A \to B) \land (C \to B))$. – Mauro ALLEGRANZA Feb 6 '18 at 14:30
• Then assume $(A \land C)$. – Mauro ALLEGRANZA Feb 6 '18 at 14:30
• $1). (A \rightarrow B)\wedge(C \rightarrow B) 2). (A \wedge C),B 3). B$ is it correct? – Bleeeaa Feb 6 '18 at 14:34
• No, it is not.... – Mauro ALLEGRANZA Feb 6 '18 at 14:39

We have to prove an implication, so we start by assuming the antecedent:

1. $((A \to B) \land (C \to B))$ (ass.)

We have to prove an implication from this so again we assume the antecedent:

1. $(A \land C)$ (ass)
2. $A \to B$ from 1. and elimination of $\land$.
3. $A$ from 2. and elimination of $\land$ again.
4. $B$ by modus ponens from 3 and 4.
5. $(A \land C) \to B$ from introduction $\to$ (cancel ass. 2)

Now your required statement follows from ass 1 (which will be eliminated) and again introduction of $\to$.