1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Christopher Carl Heckman Feb 8 '16 at 6:22
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

$\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)}$$

$\endgroup$
0
$\begingroup$

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):

enter image description here

The proof checker and associated text for more information are linked below.


Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

P. D. Magnus, Tim Button with additions by J. Robert Loftis remixed and revised by Aaron Thomas-Bolduc, Richard Zach, forallx Calgary Remix: An Introduction to Formal Logic, Winter 2018. http://forallx.openlogicproject.org/

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.