GATE CS 1990 Q3-x — Propositional and First Order Logic

To determine which formula is valid (a tautology), we analyze each option:

1. $(P \Rightarrow Q) \wedge (Q \Rightarrow R) \Rightarrow (P \Rightarrow R)$
   This is the classic Hypothetical Syllogism rule of inference. If $P$ implies $Q$ and $Q$ implies $R$, then $P$ must imply $R$. This is a well-known tautology and is always valid.
2. $(P \Rightarrow Q) \Rightarrow (\neg P \Rightarrow \neg Q)$
   This represents the fallacy of denying the antecedent. For $P = \text{False}$ and $Q = \text{True}$:
   • Antecedent: $P \Rightarrow Q \equiv \text{False} \Rightarrow \text{True} \equiv \text{True}$.
   • Consequent: $\neg P \Rightarrow \neg Q \equiv \text{True} \Rightarrow \text{False} \equiv \text{False}$.
   Thus, $\text{True} \Rightarrow \text{False}$ is $\text{False}$. This is invalid.
3. $(P \wedge (\neg P \vee \neg Q)) \Rightarrow Q$
   Simplifying the antecedent using the distributive law: $$P \wedge (\neg P \vee \neg Q) \equiv (P \wedge \neg P) \vee (P \wedge \neg Q) \equiv \text{False} \vee (P \wedge \neg Q) \equiv P \wedge \neg Q$$ The formula becomes $(P \wedge \neg Q) \Rightarrow Q$. For $P = \text{True}$ and $Q = \text{False}$, the antecedent is $\text{True}$ but the consequent is $\text{False}$. This is invalid.
4. $((P \Rightarrow R) \vee (Q \Rightarrow R)) \Rightarrow ((P \vee Q) \Rightarrow R)$
   Let $P = \text{True}$, $Q = \text{False}$, and $R = \text{False}$:
   • Antecedent: $(P \Rightarrow R) \vee (Q \Rightarrow R) \equiv (\text{True} \Rightarrow \text{False}) \vee (\text{False} \Rightarrow \text{False}) \equiv \text{False} \vee \text{True} \equiv \text{True}$.
   • Consequent: $(P \vee Q) \Rightarrow R \equiv (\text{True} \vee \text{False}) \Rightarrow \text{False} \equiv \text{True} \Rightarrow \text{False} \equiv \text{False}$.
   Thus, $\text{True} \Rightarrow \text{False}$ is $\text{False}$. This is invalid.