GATE CS 2015 Set 2 Q55 — Propositional and First Order Logic

To determine which well-formed formula is a tautology, we can analyze the options:

• Option C: The material implication equivalence states that for any propositions $A$ and $B$, $A \rightarrow B \equiv \neg A \lor B$. Applying this equivalence to the predicate terms: $$P(x,y) \rightarrow R(x, y) \equiv \neg P(x, y) \lor R(x, y)$$ Since the inner formulas are logically equivalent, applying the same quantifiers $\forall x \, \exists y$ to both sides preserves this equivalence: $$\forall x \, \exists y \, \left( P(x,y) \, \rightarrow \, R(x, y) \right) \equiv \forall x \, \exists y \left(\neg P(x, y) \, \lor R(x, y) \right)$$ Since both sides of the bi-conditional ($\leftrightarrow$) are logically equivalent, the entire formula is always true (a tautology).
• Option D: The formula $\forall x \, \forall y \, P(x,y)$ asserts that the predicate $P$ holds for all pairs in the domain. Swapping the variable names does not change this meaning, so $\forall x \, \forall y \, P(x,y) \equiv \forall x \, \forall y \, P(y,x)$. Thus, Option D is also a tautology (both C and D were accepted as correct in the official GATE key).
• Option A: $\forall x \, \exists y \, R(x,y) \rightarrow \exists y \, \forall x \, R(x,y)$ is not generally valid (e.g., "every person has a mother" does not imply "there is a single person who is the mother of everyone").
• Option B: The scope of the existential quantifier $\exists y$ in the antecedent is restricted to $R(x,y)$, leaving $y$ in $S(x,y)$ free, which does not logically imply the consequent.