Natural Deduction

Question

Given the following premises:

P AND Q 1.
P IMPLIES R 2.
Q IMPLIES R 3.

I need to demonstrate that this entails:

Q AND R

The way I tackled the problem was:

Q 4. AND ELIMINATION on Line 1
R 5. IMPLICATION ELIMINATION on Lines 3, 4
Q AND R 6. AND INTRODUCTION on Lines 4, 5

However, the textbook solution derives:

P OR Q

and then uses both statements 2 and 3 to imply R. However, isn't having Q alone sufficient to imply R and complete the proof?

PS: Apologies for the poor formatting, I'm not sure how I can do better.

Answer 1

Proof :

$$\begin{align} (1) & P \land Q && [\text{assumed}] \\ (2) & P && [\land \text{-elim(1)}] \\ (3) & Q && [\land \text{-elim(1)}] \\ (4) & P \rightarrow R && [\text{assumed}] \\ (5) & R && [\rightarrow \text{-elim}(2,4)] \\ (6) & Q \land R && [\land\text{-intro}(3,5)] \\ \end{align}$$

Thus we have proved :

$P \land Q, P \rightarrow R \vdash Q \land R$.

The third premise : $Q \rightarrow R$ seems unnecessary to me.

But you are right; we may replace step (4) with $Q \rightarrow R$ and then derive $R$ from (3) and (4) by $\rightarrow$-elim; then conclude as before.

In this case, we have :

$P \land Q, Q \rightarrow R \vdash Q \land R$

and is $P \rightarrow R$ which is redundant.

The "detour" through $P \lor Q$ seems unnecessary; in this case we have to derive $P \vdash R$ and $Q \vdash R$ (as in the two versions of the proof above) and then we use $\lor$-elim : to conclude $P \lor Q \vdash R$.

Thus, we have :

$P \land Q, P \rightarrow R, Q \rightarrow R \vdash Q \land R$

and we have used all the premises.