Computer Sciences > GATE 2026 SET-2 > Discrete Mathematics
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?
A
(∃y)(∀x)((x ≠ y) → (M(x, y) ∧ ¬M(y, x)))
B
(∀y)(∃x)((x ≠ y) → (M(x, y) ∧ ¬M(y, x)))
C
(∃y)(∃x)((x ≠ y) → (M(x, y) ∧ ¬M(y, x)))
D
(∀y)(∀x)((x ≠ y) → (M(x, y) ∧ ¬M(y, x)))

Correct : a

The English statement has two parts about the same special person y — they do not know anyone else, but everyone else knows them.
The first word "there is" tells us we need an existential quantifier for y, so we start with ∃y. The phrases "anyone else" and "everyone else" both refer to all persons x different from y, so we need ∀x with the condition x ≠ y. Using implication (x ≠ y) → ... is the standard way to restrict the universal quantifier to only those x that are different from y.
Inside the implication we need two things to hold simultaneously for every such x — M(x, y) meaning x knows y (everyone else knows that person), and ¬M(y, x) meaning y does not know x (that person does not know anyone else). Both conditions are joined with ∧.
So the full expression is (∃y)(∀x)((x ≠ y) → (M(x, y) ∧ ¬M(y, x))), which is option A.
Why the others are wrong:
Option B uses ∀y∃x which says "for every person y, there exists some x" — this changes the meaning completely and does not fix one special person.
Option C uses ∃y∃x which says there exist some y and some x — this only claims two specific people have this relationship, not that it holds for all others.
Option D uses ∀y∀x which universalises over everyone — this would mean every person simultaneously does not know anyone and is known by everyone, which is far too strong and not what is stated.
Correct answer: A ✓

Similar Questions

The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln-1 + Ln-2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
#953 MCQ
Geetha has a conjecture about integers, which is of the form ∀x(P(x)⇒∃yQ(x,y)), where P is a statement about integers, and Q is a statement about pairs of integ...
#962 MSQ
Let U = {1, 2,...,n}, where n is a large positive integer greater than 1000. Let k be a positive integer less than n. Let A, B be subsets of U with |A| = |B| =...
#983 MCQ

Related Topics

predicate logic GATE 2026 GATE CS 2026 Set-2 Q11 existential universal quantifier GATE M(x y) knows predicate logic discrete mathematics GATE 2026 first order logic statement GATE quantifier expression person knows GATE

Unique Visitor Count

Total Unique Visitors

Loading......