How do I prove the following using Natural Deduction?
$$((P \land Q) \rightarrow R) \vdash (P \rightarrow R) \lor (Q\rightarrow R)$$
My current approach:
So instead of proving $(P \rightarrow R) \lor (Q\rightarrow R)$, I figure I just need to prove $(P \rightarrow R)$ and use disjunction introduction.
The problem is my hypothesis requires $P$ and $Q$. How do I "create" this Q? I tried using the Law of the Excluded middle, but it does not seem to work.
Any help or insights is deeply appreciated.
This isn't quick using just the standard introduction and elimination rules. But the obvious brute-force way has the following shape using a Fitch-style lay out:
$((P \land Q) \to R)\\ \quad\quad |\quad \neg ((P \to R) \lor (Q \to R))\\ \quad\quad |\quad\quad|\quad (P \to R)\\ \quad\quad |\quad\quad|\quad ((P \to R) \lor (Q \to R))\\ \quad\quad |\quad\quad|\quad \bot\\ \quad\quad |\quad \neg(P \to R)\\ \quad\quad |\quad \vdots\\ \quad\quad |\quad P\\ \quad\quad |\quad \neg R\\ \quad\quad |\quad\quad|\quad (Q \to R)\\ \quad\quad |\quad\quad|\quad ((P \to R) \lor (Q \to R))\\ \quad\quad |\quad\quad|\quad \bot\\ \quad\quad |\quad \neg(Q \to R)\\ \quad\quad |\quad \vdots\\ \quad\quad |\quad Q\\ \quad\quad |\quad \neg R\\ \quad\quad |\quad (P \land Q)\\ \quad\quad |\quad R\\ \quad\quad |\quad \bot\\ \neg\neg((P \to R) \lor (Q \to R))\\ ((P \to R) \lor (Q \to R))$
We temporarily assume the negation of the conclusion and aim for a reductio (what else?). Check that you understand the rationale at each step -- though the moves after that initial assumption are pretty much then the only sensible things to do. The dots hold the places for two routine proofs you need to know how to do (from something of the form $\neg(A \to B)$ to both $A$ and $\neg B$).