I am trying to learn proof by contradiction. How would i go about proving that
((A => B) and (C => D)) => ((A => D) or (C => B))
is a tautology, using proof by contradiction? Particularly what would be the steps for producing a contradiction? thanks.
Negate your statement, by putting a $\neg$ in front of it (with everything between brackets) and show that it is always false.
Your initial proposition is: $((A\to B)\land(C\to D))\to((A\to D)\lor(C\to B))$. Consider now its negation, and work step by step until you single out sentence letters: $$\neg\bigg(\Big((A\to B)\land(C\to D)\Big)\to\Big((A\to D)\lor(C\to B)\Big)\bigg)$$ $$\Longleftrightarrow\Big((A\to B)\land(C\to D)\Big)\land\neg\Big((A\to D)\lor(C\to B)\Big)$$ $$\Longleftrightarrow\Big((\neg A\lor B)\land(\neg C\lor D)\Big)\land\Big(\neg(A\to D)\land\neg(C\to B)\Big)$$ $$\Longleftrightarrow\Big(\neg(A\land\neg B)\land\neg(C\land\neg D)\Big)\land\Big((A\land\neg D)\land(C\land\neg B)\Big)$$ $$\Longleftrightarrow\neg(A\land\neg B)\land\neg(C\land\neg D)\land(A\land\neg B)\land(C\land\neg D)$$
And the last line is obviously a logical falsehood (contradiction). Therefore, the original proposition must be a tautology.
EDIT - To follow up on
Git Gudandcrash's comments: notice that my first step, negating the original proposition, is exactly equivalent to saying "let the premise be true and the conclusion false" (see line 2). What we're trying to show is that this is a contradiction: that there is precisely no possible assignment of truth-values to the sentence letters that make the premise true and the conclusion false (in which case the original implication is a tautology). Ascrashmentioned, in the last step, I used the fact that the second major bracket contains only conjunctions: these have the property of being associative, i.e. you can rearrange them as you please and, in particular, in such a way that they become explicitly contradictory with the first major bracket.