I am usually quite good with these but i just can't wrap my head around this once for some reason. I have to make a Fitch-style proof for the expression:
$(s \rightarrow p) \lor (t \rightarrow q) \vdash(s \rightarrow q) \lor (t \rightarrow p)$
It is easy to see that this is correct because the only time the left hand side is false is when
$(s \land \lnot p) \land (t \land \lnot q)$
Which also holds true for the right hand side since it's just switching around p and q. But how do i go about making a Fitch-style proof?
Best Answer
Whoever set the exercise wasn't being very kind; but tackling this is in fact quite a useful reality check in getting you to think through proof-strategy.
You have a disjunctive premiss, of the form $A \lor B$, and target conclusion $C$. It's a pound to a penny that you are going to have to use disjunction elimination. So the shape of the argument is surely going to be
$\quad A \lor B\\ \quad\quad\mid\quad A\\ \quad\quad\mid\quad \vdots\\ \quad\quad\mid\quad C\\ \quad\quad--\\ \quad\quad\mid\quad B\\ \quad\quad\mid\quad \vdots\\ \quad\quad\mid\quad C\\ \quad C$
So that reduces the problem, to finding two proofs, from $A$ to $C$ and $B$ to $C$. We'll look at the first, the other being similar.
So you now want to fill in the dots
$\quad s \to p\\ \quad \vdots\\ \quad (s \to q) \lor (t \to p)$
Nasty to do from first principles. But it perhaps looks a bit more manageable if you carve things into two stages like this
$\quad s \to p\\ \quad \vdots\\ \quad \neg s \lor p\\ \quad \vdots\\ \quad (s \to q) \lor (t \to p)$
(I didn't pull that out of a hat: think why that is the obvious path to take!) And you are going to need another disjunction elimination for the second part which should pretty obviously go
$\quad s \to p\\ \quad \vdots\\ \quad \neg s \lor p\\ \quad\quad \mid \neg s\\ \quad\quad \mid \vdots\\ \quad\quad \mid (s \to q)\\ \quad\quad \mid (s \to q) \lor (t \to p)\\ \quad\quad --\\ \quad\quad \mid p\\ \quad\quad \mid \vdots\\ \quad\quad \mid (t \to p)\\ \quad\quad \mid (s \to q) \lor (t \to p)\\ \quad (s \to q) \lor (t \to p)$
So we have at least reduced the problem to that of filling in the three gaps. But each of those should be a standard familiar task which you can already do in a Fitch proof. So I'll leave those further details filling in the $A$-to-$C$ proof to you; and the $B$-to-$C$ proof works similarly!