GateAI
Propositional and First-Order Logic

GATE CSE 2026 Set 2 · Q11

MCQ1 markEasy

Time

For two different persons xx and yy, the predicate M(x,y)M(x, y) denotes that xx knows yy. 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?

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: A) (∃ y)(∀ x) ((x ≠ y) → (M(x, y) eg M(y, x)))

Propositional and First-Order Logic

Let the specific person mentioned in the statement be represented by the variable yy.

  1. "There is a person...": This translates to an existential quantifier ∃y\exists y.

  2. "...who does not know anyone else": For any other person xx (where x≠yx \neq y), person yy does not know xx, which is represented as $

eg M(y, x)$.

  1. "...but that person is known by everyone else": For any other person xx (where x≠yx \neq y), person xx knows yy, which is represented as M(x,y)M(x, y).

Combining both conditions for every person xx distinct from yy: ∀x((x≠y)→(M(x,y)∧egM(y,x)))\forall x \big((x \neq y) \rightarrow (M(x, y) \wedge eg M(y, x))\big)

Adding the outer existential quantifier over yy, we get: (∃y)(∀x)((x≠y)→(M(x,y)∧egM(y,x)))(\exists y)(\forall x)\big((x \neq y) \rightarrow (M(x, y) \wedge eg M(y, x))\big)

Hence, option A correctly represents the given statement.

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Propositional and First-Order Logic previous year question is Q11 of the GATE CSE 2026 Set 2 paper. Find more GATE CSE PYQs on Propositional and First-Order Logic in Engineering Mathematics, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Propositional and First-Order Logic PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Propositional and First-Order Logic in GATE CSE

Propositional and First-Order Logic has 18 GATE CSE PYQs across 16 papers from 2011 to 2026. 6 of them are 1-mark MCQs like this one, and it is the only one in GATE CSE 2026 Set 2.

How GATE tests Propositional and First-Order Logic

More from GATE CSE 2026 Set 2

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2026 Set 2 · Q11 · MCQ

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?

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.