The GATE Grind

GATE 2026 CS (CS2) – Question 11

Engineering Mathematics · Discrete Mathematics: Propositional and First Order Logic · 1 mark · Multiple choice

For two different persons $x$ and $y$, the predicate $M(x,y)$ denotes that $x$ knows $y$. Consider the following statement: There is a person who does not know anyone else, but that person is known by everyone else. Which one of the following expressions represents the above statement?

  1. $(\exists y)(\forall x)\,((x \ne y) \to (M(x,y) \land \neg M(y,x)))$
  2. $(\forall y)(\exists x)\,((x \ne y) \to (M(x,y) \land \neg M(y,x)))$
  3. $(\exists y)(\exists x)\,((x \ne y) \to (M(x,y) \land \neg M(y,x)))$
  4. $(\forall y)(\forall x)\,((x \ne y) \to (M(x,y) \land \neg M(y,x)))$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $(\exists y)(\forall x)\,((x \ne y) \to (M(x,y) \land \neg M(y,x)))$

Explanation

We need a statement saying there exists a person $y$ such that every other person $x$ knows $y$, but $y$ does not know $x$. This is written as $(\exists y)(\forall x)((x \ne y) \to (M(x,y) \land \neg M(y,x)))$. Therefore, option (A) is correct.