GATE CS 1992 Q02 — Propositional and First Order Logic

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

Let us analyze each option:

Option B: $a \wedge b \to b \vee c$

An implication of the form $P \to Q$ is false if and only if the antecedent $P$ is True and the consequent $Q$ is False.

• Let the antecedent $P = a \wedge b$. For $P$ to be True, both $a$ and $b$ must be True.
• If $b$ is True, then the consequent $Q = b \vee c$ must also be True (since $T \vee c \equiv T$).

Since it is impossible for the antecedent to be True while the consequent is False, the implication $a \wedge b \to b \vee c$ is always True. Thus, it is a tautology.

Eliminating other options:

• Option A: $a \vee b \to b \wedge c$
  If we assign $a = \text{True}$, $b = \text{False}$, and $c = \text{False}$: $$\text{True} \vee \text{False} \to \text{False} \wedge \text{False} \implies \text{True} \to \text{False} \equiv \text{False}$$ Hence, it is not a tautology.
• Option C: $a \vee b \to (b \to c)$
  If we assign $a = \text{True}$, $b = \text{True}$, and $c = \text{False}$: $$\text{True} \vee \text{True} \to (\text{True} \to \text{False}) \implies \text{True} \to \text{False} \equiv \text{False}$$ Hence, it is not a tautology.
• Option D: $a \to b \to (b \to c)$
  If we assign $a = \text{True}$, $b = \text{True}$, and $c = \text{False}$: Whether parsed as $(a \to b) \to (b \to c)$ or $a \to (b \to (b \to c))$, this expression evaluates to False. Hence, it is not a tautology.