Natural Deduction $(\phi \wedge \psi) \to \chi \vdash (\phi \to \chi) \vee (\psi \to \chi)$

Question

I have to proof the following using natural deduction: $(\phi \wedge \psi) \to \chi \vdash (\phi \to \chi )\vee (\psi \to \chi)$. I want to try to do this without using morgan's laws or anything like that - just the rules for introducing/eliminating the symbols. Can anyone help to get me started?

Answer 1

Improved proof, thanks to comments received.

The proof uses Double Negation rule: thus, it is not intuitionistically valid.

1. $(\phi \wedge \psi) \to \chi$ --- premise

2. $\lnot [(\phi \to \chi )\vee (\psi \to \chi)]$ --- assumption [a]

3. $\phi$ --- asumption [b]

4. $\psi$ --- assumption [c]

5. $(\phi \wedge \psi)$ --- from 3) and 4) by $\land$intro

6. $\chi$ --- using 5) and 1) by $\to$-elim

7. $(\psi \to \chi)$ --- from 4) and 6), discharging [c]

8. $\bot$ --- from 7) using $\lor$-intro and 2)

9. $\chi$ --- from 8) using EFQ

10. $(\phi \to \chi)$ --- from 3) and 9), discharging [b]

Now we have again a contradiction with 2) and we conclude by DN with:

$(\phi \to \chi )\vee (\psi \to \chi)$ --- discharging [a].

Answer 2

As mentioned in the comments, the formula is true (in fact, the converse also holds). This you have already seen in your truth table. However, you ask to prove it without De Morgan's laws, and that is simply impossible. The reason is that it is not a tautology in intuitionistic logic. Put differently: you will need some instance of double negation elimination (or proof by contradiction).

I wrote an answer about this for a more specific case here. They ask about $\neg(P \wedge Q) \to (\neg P \vee \neg Q)$. So setting $\phi = P$, $\psi = Q$ and $\chi = \bot$ we see that that really is a special case of what you are asking about.