I have been shown how to prove a propositional formula is a tautology by using contradiction. However, I'm not fully understanding the logic.
Could someone help me understand the logic behind the below steps.
$$((P \to Q) \land (R \to S) \land (\lnot Q \lor \lnot S)) \to (\lnot P \lor \lnot R) $$
We assume the right hand side of the implication is false. Which mean P = 1, and R = 1 $$((P \to Q) \land (R \to S) \land (\lnot Q \lor \lnot S)) \to (P \land R) $$
We now see if the left hand side is true or false. $$((1 \to Q) \land (1 \to S) \land (\lnot Q \lor \lnot S))$$
$$ = Q \land S \land (\lnot Q \lor \lnot S)$$
This can't be true since if $Q = 1, \lnot Q = 0,$ if $S = 1, \lnot S = 0$.
All of the above means that the main formula is a tautology. But why?
Wait, is it because, for the formula as whole to be false, the premise (Left side) has to be true and the consequence(right side) has to be false. However, making the consequence false leads to the premise also being false, in which case the implication formula is true.
So there is no state in which the formula is false. A.K.A tautology.