I'm supposed to prove the validity of the following
$(p\to q)\lor (r\to s) \vdash (p\to s)\lor(r\to q)$
I'm very new to natural deduction, so I still haven't got a "feel" about it. I can prove small sequents, but it usually involves random guessing on my part. Like in this case, I see that the left side has an "or". So I assumed each of the operand true individually and then tried to prove the RHS from both sides. But I have no idea how to follow up. I'd be grateful if you could tell me your thought process behind the solution.
Also, why is Fitch logic so complicated? Can't we use boolean algebra to prove things? All we have to do is prove ((LHS1)and(LHS2)and(LHS3)...)->(R.H.S)=1 using the laws of boolean algebra. Seems much simpler to me. Is there a way to convert such a boolean proof to Fitch proof?
Fitch-style notation is a particular approach to a more general method of proof, called natural deduction. One appealing feature of natural deduction is that it mirrors the structure of deductive argumentation. For example, an argument for a statement of the form "if $p$ then $q$" may begin with an assumption of the truth of $p$, followed by inferences from $p$ together with various supporting assumptions, to an assertion of $q$; this justifies the assertion of $p\to q$ on the basis of the supporting assumptions alone. Fitch-style notation illuminates the patterns of hypothetical argument by requiring conclusions reached "under" an assumption to be written under it literally, as in:
$\begin{array}{|l} p \\ \cdots \\ \cdots \\ q \end{array} \\ p\to q$
A second, perhaps more philosophically appealing feature of natural deduction is that its rules of proof make as clear as possible that "nothing can be inferred from a statement which was not required for its proof". For example, a statement $p\to q$ yields a proof of $q$ given a proof of $p$; but this is precisely what is needed to prove $p\to q$ in the first place.
Of course, a choice of rules which are comparably few and simple entails a tradeoff: a bit more work in their application. Specifically, you can expect some simple-looking valid sequents to require in natural deduction a complicated or indirect argument. (Often, the validity of such sequents may seem slightly counterintuitive, as in for example $(p\to q)\lor(q\to p)$.)
The example you mention looks contrived to demonstrate just how hairy natural deduction arguments can get; if it was assigned by an instructor you should probably give them the evil eye.
Anyway, a sketch for the case you mention. The goal is to prove something on the basis of a disjunction. Since, in proving a disjunction, it suffices to prove any of its disjuncts, therefore in deducing some conclusion from a disjunction it is necessary to show that it follows from any of its disjuncts as well.
The task now breaks into two. First assume the left disjunct of your hypothesis, namely $p\to q$; you want to deduce from this $(p\to s)\lor (r\to q)$. To that end it would, of course, suffice to deduce a disjunct, one of $p\to s$ and $r\to q$. However, check of the truth-tables shows that won't be possible since your deduction system is sound. So you must instead proceed indirectly. Assume the opposite $\neg ((p\to s)\lor(r\to q))$ of your goal and aim for contradiction. To this end, you should devise arguments for the patterns $\neg(A\lor B)\vdash \neg A$, $\neg(A\to B)\vdash A$, and $\neg(A\to B)\vdash \neg B$. Together these patterns will help you to prove the desired
$p\to q,\neg ((p\to s)\lor(r\to q))\vdash \bot$,
from which you obtain a proof of
$p\to q\vdash((p\to s)\lor(r\to q))$.
A proof of
$r\to s\vdash((p\to s)\lor(r\to q))$
will be completely parallel.
You can now complete the proof by disjunction elimination.