GATE CS 2026 Set 2 Q1 — Propositional and First Order Logic

To translate the given English statement into first-order logic, let us break it down into smaller components:

1. "There is a person..."
   This indicates an existential quantifier. Let this special person be represented by the variable $y$. Thus, we start with: $$\exists y$$
2. "...who does not know anyone else..."
   For any other person $x$ (where $x \neq y$), $y$ does not know $x$. This is represented as: $$\forall x (x \neq y \rightarrow \neg M(y, x))$$
3. "...but that person is known by everyone else."
   For any other person $x$ (where $x \neq y$), $x$ knows $y$. This is represented as: $$\forall x (x \neq y \rightarrow M(x, y))$$

Combining these two conditions for all other persons $x$, we get:

$$\forall x \left( (x \neq y) \rightarrow (M(x, y) \wedge \neg M(y, x)) \right)$$

Prefixing this with the existential quantifier for $y$ yields the complete expression:

$$(\exists y)(\forall x)\left((x \neq y) \rightarrow(M(x, y) \wedge \neg M(y, x))\right)$$

This matches Option A.