# Prove using natural deduction $((P \land Q) \rightarrow R) \vdash (P \rightarrow R) \lor (Q\rightarrow R)$

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.

• Proving $P\to R$ won't work, because $P$ might be true and $Q$ and $R$ false; your assumption is true, but the intermediate step $P \to R$ is false. ... I would change $(P\to R)\vee (Q\to R)$ to $\neg(P\to R)\to (Q\to R)$; then you can assume $\neg(P\to R)$ as well. (I'm not 100% what you mean by "natural deduction", so this method might not be legit.) – Christopher Carl Heckman Feb 8 '16 at 6:22

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

$\def\fitch#1#2{\quad\begin{array}{|l} #1\\[0ex]\hline #2\end{array}}$

Hints: $\neg P \to(P\to R)$, $\neg Q \to(Q\to R)$ and $R\to(P\to R)$ are tautologies.

$$\fitch{(P\land Q)\to R}{\fitch{\lnot((P\to R)\lor(Q\to R))}{\fitch{\neg P}{~~\vdots\\(P\to R)\lor(Q\to R)\\\bot}\\\neg\neg P\\P\\~~\vdots\\Q\\P\land Q\\R\\~~\vdots\\(P\to R)\vee(Q\to R)\\\bot}\\\lnot\lnot((P\to R)\lor(Q\to R))\\(P\to R)\lor(Q\to R)}$$

The OP ran into problems trying to use the Law of the Excluded Middle to prove this. Here is a proof that uses the Law of the Excluded Middle (LEM): 