$(s \to p) \lor (t \to q) \vdash (s \to q) \lor (t \to p)$
This has been giving me a terrible headache. I have no idea how to go about proving this. I'm not asking for a complete solution, I just need some pointers to prove this with natural deduction...
On
We want to prove the right hand side assuming the left hand side.
Suppose $(s\to q)$ is false (with a given interpretation of the letters).
That happens only when $s$ is true and $q$ is false.
From the conditions, if $(s\to p)$ holds, then $p$ is also true, therefore so is $(t\to p)$,
while if $(t\to q)$ holds, then $t$ must be false as $q$ is false, hence again $(t\to p)$ is true.
By the way, both sides can be written as $$(\lnot s)\lor p\lor (\lnot t)\lor q\ =\ (\lnot s)\lor q\lor (\lnot t)\lor p\,.$$
Since your premise is a disjunction you need to use the rule of elimination of the disjunction. First you have to assume (s → p) and then try to derivate (s → q) ∨ (t → p), and second you have to assume (t → q) and try to derivate (s → q) ∨ (t → p), wiht this tow derivations you can conlude (s → q) ∨ (t → p) by elimination of the disjunction from your premise.
I have to point out that the derivation i made is 40 steps long and it's a clasical derivation. I dont know if there's a intuitionist derivation, and my first assumption was actually ¬((s → q) ∨ (t → p)).
the proof looks like this:
4-18) derivations until you get (s → q) ∨ (t → p)
21-35) derivations until you get (s → q) ∨ (t → p)
After that you can eliminate the disjunction and finish the derivations with the rules you ned to aplly. I don't know if there's an easier derivation. If you want I can edit the answer and write the full derivation.