GATE 2026 CS2 Q.11: solution and answer

Official answer: ASource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

1. The statement names one particular person who is known by everyone else and who knows no one else. So the outer quantifier is $\exists$ on that person. Call the person $y$: $(\exists y)$.

2. "Everyone else" means every person $x$ with $x\ne y$. A universal claim about such persons is written $(\forall x)((x\ne y)\to \dots )$, because the guard $x\ne y$ restricts the claim to the others.

3. "Known by everyone else": each such $x$ knows $y$. Since $M(a,b)$ means $a$ knows $b$, this is $M(x,y)$.

4. "Does not know anyone else": $y$ does not know any such $x$. This is $\neg M(y,x)$.

5. Both conditions must hold for every $x\ne y$, so join them with $\wedge$ under the same guard: $$(\exists y)(\forall x)((x\ne y)\to (M(x,y)\wedge \neg M(y,x)))$$ This is option A.

6. Option D, $(\forall y)(\forall x)$, claims the condition for every ordered pair of distinct persons. Take two different people $a$ and $b$. Using $(x,y)=(a,b)$ gives $M(a,b)\wedge \neg M(b,a)$. Using $(x,y)=(b,a)$ gives $M(b,a)\wedge \neg M(a,b)$. These contradict each other, so D is false whenever there are at least two people. It does not express the statement.

7. Options B, $(\forall y)(\exists x)$, and C, $(\exists y)(\exists x)$, use an existential $x$ with an implication. Choosing $x=y$ makes the premise $x\ne y$ false, so the implication is true. Hence $(\exists x)(\dots )$ is true for every $y$. B is therefore true of every $y$, and C is true as soon as some $y$ exists. Neither says anything about the persons other than $y$, so neither expresses the statement.

8. Only A puts $\forall$ on $x$ under the guard $x\ne y$, so only A forces every other person to know $y$ and $y$ to know none of them. The answer is A.