0
$\begingroup$

How to show that $ \{ (\phi \wedge \psi) \rightarrow \theta \} \vdash \phi \rightarrow(\psi \rightarrow \theta)$?

I tried to do it using deduction theorem and got $\vdash((\phi \wedge \psi) \rightarrow \theta) \rightarrow (\phi \rightarrow(\psi \rightarrow \theta))$. After that rewrote it like $\vdash(\neg(\phi \rightarrow \neg \psi) \rightarrow \theta) \rightarrow (\phi \rightarrow(\psi \rightarrow \theta))$, but now I dont have no idea what to do next...

$\endgroup$
  • 3
    $\begingroup$ What proof system are you using? There are dozens of different proof systems! $\endgroup$ – Bram28 Nov 10 '18 at 20:48
  • $\begingroup$ Also, is that last $\phi$ supposed to be a $\theta$? ... and I would put parentheses around the conjunction to be clear ... $\endgroup$ – Bram28 Nov 10 '18 at 20:50
  • $\begingroup$ Also, note that you can only apply the Deduction Theorem on what you have already proven. You are trying to apply it to what needs to be proven ... $\endgroup$ – Bram28 Nov 10 '18 at 20:51
  • 2
    $\begingroup$ Can you prove $\{((\phi\land\psi)\to\theta),\phi,\psi\}\vdash\theta$ ? If so, then the deduction theorem becomes a good idea. $\endgroup$ – Andreas Blass Nov 11 '18 at 1:24
  • $\begingroup$ See Exportation (logic) for the proof of the equivalence. $\endgroup$ – Mauro ALLEGRANZA Nov 11 '18 at 10:35
1
$\begingroup$

Hint

We can use the following axiom system for propositional calculus, with modus ponens as the only rule of inference.

As usual, Ax.1 and Ax.2 are used to prove the Deduction Theorem.

1) $(ϕ∧ψ)→θ$ --- premise

2) $ϕ$ --- assumption [a]

3) $ψ$ --- assumption [b]

4) $\vdash ϕ \to (ψ \to (ϕ∧ψ))$ --- axiom

5) $(ϕ∧ψ)$ --- from 2) and 3) and 4) by modus ponens twice

6) $θ$ --- from 5) and 1) by modus ponens

7) $(ψ \to θ)$ --- from 3) and 6) by Deduction Th, discharging temporary assumption [b]

8) $ϕ \to (ψ \to θ)$ --- from 2) and 7) by Deduction Th, discharging temporary assumption [a].

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