# Natural deduction: Derive $(\phi\lor\psi)\lor\sigma\to\phi\lor(\psi\lor\sigma)$

Exercise: Derive $(\phi\lor\psi)\lor\sigma\to\phi\lor(\psi\lor\sigma)$

It's pretty hard for me to understand what I'm supposed to do. It was kinda easy to solve the first few exercises from my text-book since I just had to mimic how they solved the examples in the book. But now it isn't that easy for me any longer. I really want to understand why I am applying all these rules and their real meaning.

They have introduced some "introduction rules" and some "Elimination rules". Here is my attempt to explain how I think about the rules:

Introduction rules:

AND RULE

So begin with, which I think is, the easiest case to understand: a formulae of the form $$\phi\land\psi$$

So let's suppose $\phi$ and $\psi$ both are true (statements?) all by themselves. Then we can be sure that $\phi\land\psi$ also is true.

IMPLICATION RULE

Suppose we have a formulae $\phi$ and from this formula we derive another formula $\psi$. Then we can be sure that if $\phi$ is true then so is $\psi$. So we can introduce $\to$. That is $\phi\to\psi$.

OR RULE

If we know that $\phi_i$ is true for some $1\leq i\leq n$. Then we can be sure that $\phi_1\lor\phi_2\lor...\lor\phi_n$ also is true.

Elimination rules:

AND RULE

Let's suppose $\phi\land\psi$ is true. Then I can be sure that $\phi$ is true and that $\psi$ is true.

IMPLICATION RULE

If we know that "if $\phi$ is true then $\psi$ is true" and that "$\phi$ is true" then we can "use" the elimination rule and just conclude that "$\psi$ is true".

OR RULE

Suppose we know that $\phi_1\lor\phi_2\lor...\lor\phi_n$ is true and we have managed to derive $\sigma$ from $\phi_1$, $\sigma$ from $\phi_2$ and so on. Then we know for sure that sigma must be true. So this is like saying, since we have managed to derive $\sigma$ from every $\phi_i$ then we can substitute $\sigma$ instead of every $\phi_i$ and we get $\sigma\lor\sigma\lor...\lor\sigma$ which is the same as $\sigma$?

So this was my attempts to explain how I think about the introduction rules and elimination rules in natural deduction. Can you think about it like this: the elimination rules is to simplify expressions and introduction rules is to... complicate them? Also can you think about the introduction rule for "$\lor$" like proof by cases if you imagine a mathematical theory/theorem?

To solve the exercises my book tells me to construct "proof-trees". They are also telling me it is easiest to start from bottom and work my way up to the top. But it is best read from top to bottom.

Let's head back to the exercise at the top of this post. I'm not even really sure what I am supposed to derive. Am i supposed to derive $\phi\lor(\psi\lor\sigma)$ from $(\phi\lor\psi)\lor\sigma$. If this is the case I would like to put two parantheses around $(\phi\lor\psi)\lor\sigma$ and two around $\phi\lor(\psi\lor\sigma)$, and so it would look like this $((\phi\lor\psi)\lor\sigma)\to(\phi\lor(\psi\lor\sigma))$. Anyway if i would like to construct a "proof-tree" and begin at the end(?) of the proof, I would first use the introduction rule for implication which leaves me with $$\phi\lor(\psi\lor\sigma)$$

And then use the introduction rule for $\lor$? Which leaves me with $$\phi\text{ ........ }\psi\lor\sigma$$ and then use the "or"-elimination rule on the left-side and use another "or" introduction rule on the right side for $\psi\lor\sigma$ and so on. Is this how i should do it. Or am I totally wrong?

This was all for now. Hope someone can help me out here. I am new to this subject and it freaks me out right now. I think it took me about 3 and a half hour to finish this post since I've started to understand some concepts much better while I was typing. So i have changed some paragraphs a lot of times. :) For 3 hours ago I never even saw the difference between the introduction rules and elimination rules.

Thank you.

Hint

You have to produce a proof-tree showing :

$(ϕ∨ψ)∨σ \vdash ϕ∨(ψ∨σ)$;

a final application of the $\to$-introduction rule will convert the above proof-tree into a derivation of:

$(ϕ∨ψ)∨σ → ϕ∨(ψ∨σ)$.

For the first step, you hav to use $\lor$-elimination; this amount to two sub-proofs showing respectively :

(i) $(ϕ∨ψ) \vdash ϕ∨(ψ∨σ)$

and :

(ii) $σ \vdash ϕ∨(ψ∨σ)$

and then conclude with the application of the $\lor$-elimination rule :

$$\frac{(ϕ∨ψ) \vdash ϕ∨(ψ∨σ) \quad \quad σ \vdash ϕ∨(ψ∨σ) \quad \quad (ϕ∨ψ)∨σ}{ϕ∨(ψ∨σ)}.$$

Consider case (ii) :

1) $σ$ --- premise

2) $(ψ∨σ)$ --- from 1) by $∨$-introduction

3) $ϕ∨(ψ∨σ)$ --- from 2) by $∨$-introduction

$σ \vdash ϕ∨(ψ∨σ)$ --- from 1)-3).

Case (i) is similar, but here you need $\lor$-elimination again.

• Thank you so much for your help and such a great response. I sat for an hour just staring at your text and was thinking "okay, I still don't understand anything...", but I think things starts to clear up now. So in the first case, I have to use an elimination rule $\lor$ a second time? :) – user231999 Sep 6 '15 at 15:08
• @Joel - exactly ! – Mauro ALLEGRANZA Sep 6 '15 at 17:04