Which of the following is a Tautology? Which of the following logic is a Tautology ?


*

*$S1: (P → (Q ∨ R)) ∧ (P → (Q ∨ ¬R)) → P → Q$

*$S2: (P → Q) ∧ ((Q ∧ R) → S) → (P ∧ R) → S$



How to solve without using Truth table ?
 A: First, let me add some disambiguating parentheses where I suspect they have to go (correct me if I am wrong):
$S1: ((P \rightarrow (Q \lor R)) \land (P \rightarrow (Q \lor \neg R))) \rightarrow (P \rightarrow Q)$
$S2: ((P \rightarrow Q) \land ((Q \land R) \rightarrow S)) \rightarrow ((P \land R) \rightarrow S)$
The first one is fairly easy shown to be a tautology:
$((P \rightarrow (Q \lor R)) \land (P \rightarrow (Q \lor \neg R))) \rightarrow (P \rightarrow Q) \Leftrightarrow$ (Distribution $\rightarrow$ over $\land$)
$(P \rightarrow ((Q \lor R) \land (Q \lor \neg R))) \rightarrow (P \rightarrow Q) \Leftrightarrow$ (Adjacency)
$(P \rightarrow Q) \rightarrow (P \rightarrow Q) \Leftrightarrow$
$\top$
The second one is a bit harder:
$((P \rightarrow Q) \land ((Q \land R) \rightarrow S)) \rightarrow ((P \land R) \rightarrow S) \Leftrightarrow$ (Implication)
$\neg ((P \rightarrow Q) \land ((Q \land R) \rightarrow S)) \lor (\neg (P \land R) \lor S) \Leftrightarrow$ (DeMorgan)
$\neg (P \rightarrow Q) \lor \neg (Q \land R) \rightarrow S) \lor (\neg P \lor \neg R \lor S) \Leftrightarrow$ (Implication)
$(P \land \neg Q) \lor (Q \land R \land \neg S) \lor \neg P \lor \neg R \lor S \Leftrightarrow$ (DeMorgan)
$(P \land \neg Q) \lor (Q \land \neg(\neg R \lor S)) \lor \neg P \lor \neg R \lor S \Leftrightarrow$ (Reduction)
$\neg Q \lor Q \lor \neg P \lor \neg R \lor S \Leftrightarrow$
$\top \lor \neg P \lor \neg R \lor S \Leftrightarrow$
$\top$
A: Hints:
$S1$: This will be a tautology if, given $P \to (Q \lor R)$, $P \to (Q \lor \lnot R)$ and $P$, you can conclude $Q$. Now under any assignment, one of $R$ and $\lnot R$ is false, so one of $P \to (Q \lor R)$ and $P \to (Q \lor \lnot R)$ is equivalent to $P \to Q$. As you are given $P$, you have $Q$.
$S2$: Reason similarly using the fact that if $P \to Q$, then $P \land R \to Q \land R$.
