GATE CS 2005 Q40 — Propositional and First Order Logic

To determine which of the options is a tautology, let us simplify the propositional formulas $X$ and $Y$ using standard logical equivalences.

Given:

Step 1: Simplify $X$

Using the implication equivalence $A \to B \equiv \neg A \lor B$ and De Morgan's laws:

Step 2: Simplify $Y$

Using the implication equivalence:

Step 3: Analyze the relationship between $X$ and $Y$

Let us evaluate the implication $X \to Y$:

• If $R$ is true, both $X$ and $Y$ are true.
• If $R$ is false, then:
  • $X$ simplifies to $\neg P \land \neg Q$
  • $Y$ simplifies to $\neg P \lor \neg Q$
  Since the conjunction $(\neg P \land \neg Q)$ logically implies the disjunction $(\neg P \lor \neg Q)$, whenever $X$ is true, $Y$ must also be true.

Thus, $X \to Y$ is always true, making it a tautology.

Step 4: Eliminate other options

• Option A ($X \equiv Y$): False. If $P$ is true, $Q$ is false, and $R$ is false, then $X$ is false but $Y$ is true.
• Option C ($Y \to X$): False. Using the same counterexample ($P = \text{True}, Q = \text{False}, R = \text{False}$), we get $Y \to X \equiv \text{True} \to \text{False} \equiv \text{False}$.
• Option D ($\neg Y \to X$): False. If $P = \text{True}, Q = \text{True}, R = \text{False}$, then $X = \text{False}$ and $Y = \text{False}$. This gives $\neg Y \to X \equiv \text{True} \to \text{False} \equiv \text{False}$.