How do I build a proof in natural deduction?

233 Views Asked by At

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?

1

There are 1 best solutions below

0
On

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