GATE CS 2021 Set 1 Q7 — Propositional and First Order Logic

We can simplify the common sub-expression $\neg p \wedge (p \vee q)$ using the distributive law of propositional logic:

Now, let's analyze the two formulae:

1. Formula $S_1$: $(\neg p \wedge (p \vee q)) \rightarrow q$
   Substituting the simplified expression, we get: $$(\neg p \wedge q) \rightarrow q$$ Since any implication of the form $A \wedge B \rightarrow B$ is always true, $S_1$ is a tautology.
2. Formula $S_2$: $q \rightarrow (\neg p \wedge (p \vee q))$
   Substituting the simplified expression, we get: $$q \rightarrow (\neg p \wedge q)$$ If we assign $p = \text{True}$ and $q = \text{True}$, the formula evaluates to: $$\text{True} \rightarrow (\text{False} \wedge \text{True}) \equiv \text{True} \rightarrow \text{False} \equiv \text{False}$$ Since it is false for at least one truth assignment, $S_2$ is not a tautology.

Hence, $S_1$ is a tautology but $S_2$ is not a tautology.