The meanings of the predicates used are:
mother(y, x): y is the mother of x
noteq(x, y): x and y are not equal
Correct : b
This question is about expressing "exactly one" in predicate logic — which is one of the most commonly tested concepts in GATE discrete mathematics. "Exactly one" means two things at once: at least one exists, and no second one exists. Both parts must appear in the formula for it to be correct.
Let''s go through each option carefully.
Option A — ∀x∃y∃z(mother(y,x) ∧ ¬mother(z,x))
This says: for every x, there exists some y who is a mother of x, and there exists some z who is NOT a mother of x. The problem here is that z could be anyone — even x itself or some random person. This formula doesn''t say anything about y being the only mother. It completely fails to capture uniqueness, making Option A incorrect.
Option B — ∀x∃y[mother(y,x) ∧ ∀z(noteq(z,y) → ¬mother(z,x))]
This is the correct one. It reads: for every person x, there exists a y who is the mother of x, and for every z that is different from y, z is NOT the mother of x. The first part guarantees existence, and the second part guarantees uniqueness — no one other than y can be the mother of x. This is a textbook representation of "exactly one" and is correct.
Option C — ∀x∀y[mother(y,x) → ∃z(mother(z,x) ∧ ¬noteq(z,y))]
Let''s unpack this carefully. ¬noteq(z,y) means z and y are equal. So the formula says: for every x and y, if y is the mother of x, then there exists a z who is also the mother of x and z equals y. This is essentially just saying "if y is a mother of x, then y is a mother of x" — a tautology that says nothing about uniqueness or even existence. This is incorrect.
Option D — ∀x∃y[mother(y,x) ∧ ¬∃z(noteq(z,y) ∧ mother(z,x))]
This says: for every x, there exists a y who is the mother of x, and there is no z different from y who is also the mother of x. This is logically equivalent to Option B — the only difference is that uniqueness is expressed using ¬∃ instead of ∀...→¬. Since ¬∃z P(z) is the same as ∀z ¬P(z), both formulas say the same thing. So Option D is also a correct representation.
The official GATE key marks Option B as the answer, though Option D is equally valid logically. In GATE MSQ questions, both would be accepted. The key insight to remember - whenever you see "exactly one" in a logic question, immediately think: existence + uniqueness, and make sure both are present in the formula you pick.
Similar Questions
Total Unique Visitors