Vtyjkyuk

how do I prove the following using Natural Deduction ?

$((P land Q) rightarrow R) vdash (P rightarrow R) lor (Qrightarrow R)$

My current approach:

So instead of proving $(P rightarrow R) lor (Qrightarrow 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 Law of Excluded middle, but it does not seemed 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)\
quadquad |quad neg ((P to R) lor (Q to R))\
quadquad |quadquad|quad (P to R)\
quadquad |quadquad|quad ((P to R) lor (Q to R))\
quadquad |quadquad|quad bot\
quadquad |quad neg(P to R)\
quadquad |quad vdots\
quadquad |quad P\
quadquad |quad neg R\
quadquad |quadquad|quad (Q to R)\
quadquad |quadquad|quad ((P to R) lor (Q to R))\
quadquad |quadquad|quad bot\
quadquad |quad neg(Q to R)\
quadquad |quad vdots\
quadquad |quad Q\
quadquad |quad neg R\
quadquad |quad (P land Q)\
quadquad |quad R\
quadquad |quad bot\
negneg((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$).

$deffitch#1#2quadbeginarrayl #1\[0ex]hline #2endarray$

Hints: $neg P to(Pto R)$, $neg Q to(Qto R)$ and $Rto(Pto R)$ are tautologies.

$$fitch(Pland Q)to Rfitchlnot((Pto R)lor(Qto R))fitchneg P~~vdots\(Pto R)lor(Qto R)\bot\negneg P\P\~~vdots\Q\Pland Q\R\~~vdots\(Pto R)vee(Qto R)\bot\lnotlnot((Pto R)lor(Qto R))\(Pto R)lor(Qto R)$$