5.7 One with proof by cases. $P\vee(Q\wedge R)\vdash P\vee Q$

It will be needed the most complex derivation rule: the disjunction elimination. $P\vee(Q\wedge R)\vdash P\vee Q$ solved:

$$\begin{fitch} \par P \vee (Q \wedge R) \\ \par \fh P & H \\ ... ...I$\vee$\ 5 \\ \par P \vee Q & E$\vee$\ 1,3,6 \par \end{fitch}$$

You already know the rules, so I just explain the way of thinking of a human who doesn't know natural deduction but can think a little:

We need to know that $P\vee Q$ is always true. The expression from the left, $P\vee(Q\wedge R)$, can be made true because of two causes:

• if it's true because $P$ is true, then $P\vee Q$ is true.
• if it's true because $Q\wedge R$ is true, then both $Q$ and $R$ are true, so $P\vee Q$ is true because of $Q$.

So, anyway, $P\vee Q$ is true.

Well, now we just need to translate all this to logical language, following the same order in which we thought that, and proceeding slowly.

We start proving one path, then the other, and finally we apply the disjunction elimination. To justify it we must write the line where the disjunction is in, and the two lines from inside each subdemonstration where we saw that both supposing one thing or supposing the other leads to the same result.

Notice that, even if we discovered that $P\Rightarrow P\vee Q$ and that $Q\wedge R\Rightarrow P\vee Q$, it isn't necessary to use implication introduction to keep this written down.

The hardest thing in proof by cases is to decide which will be the expression to prove in both cases. It must be exactly the same in both cases!