GATE CS 1997 Q3.2 — Propositional and First Order Logic

A proposition is a tautology if it is true under all possible truth value assignments of its constituent variables.

Let us analyze each option by simplifying the logical expressions using standard equivalences (specifically, the implication rule: $A \rightarrow B \equiv \neg A \vee B$):

• Option A: $(p \vee q) \rightarrow p$
  $\equiv \neg(p \vee q) \vee p$
  $\equiv (\neg p \wedge \neg q) \vee p$
  $\equiv (\neg p \vee p) \wedge (\neg q \vee p)$
  $\equiv T \wedge (\neg q \vee p) \equiv p \vee \neg q$
  This is not a tautology (it is false when $p = \text{False}$ and $q = \text{True}$).
• Option B: $p \vee (q \rightarrow p)$
  $\equiv p \vee (\neg q \vee p)$
  $\equiv p \vee \neg q$
  This is not a tautology (it is false when $p = \text{False}$ and $q = \text{True}$).
• Option C: $p \vee (p \rightarrow q)$
  $\equiv p \vee (\neg p \vee q)$
  $\equiv (p \vee \neg p) \vee q$
  $\equiv T \vee q$
  $\equiv T$
  Since this expression simplifies to $\text{True}$ regardless of the truth values of $p$ and $q$, it is a tautology.
• Option D: $p \rightarrow (p \rightarrow q)$
  $\equiv \neg p \vee (\neg p \vee q)$
  $\equiv \neg p \vee q$
  This is not a tautology (it is false when $p = \text{True}$ and $q = \text{False}$).