Propositional logic: how to show if tautology using proof by contradiction

Question

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.

Answer 1

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.

Yes this is the correct reason. However, the way you expressed the earlier part of your question is not correct.

You want to prove:

  $((P \to Q) \land (R \to S) \land (\lnot Q \lor \lnot S)) \to (\lnot P \lor \lnot R)$

To do so you consider the situation in which its negation is true:

  $((P \to Q) \land (R \to S) \land (\lnot Q \lor \lnot S)) \land (P \land R)$.

Since in this situation you deduce that $Q$ is true and $S$ is true, and hence $(\lnot Q \lor \lnot S)$ is false, you have reached a contradiction, and therefore this situation does not occur.

The only remaining possibility is that the original sentence is (always) true.

Answer 2

I cannot comment yet. So I write an answer.

The left side must always be true. When you assume that $\neg p \vee\neg q$ is false you end up in a situation where left side is false.

If $p\wedge q$ is true, then $p$ and $q$ must be true. Now, the implications $p\rightarrow q$ and $r\rightarrow s$ can be eather true or false, but also $\neg q \vee \neg s$ can be true or false. Both lead into contradiction.