GATE CS 2025 Set 1 Q38 — Propositional and First Order Logic

To represent the statement "Everyone has exactly one mother", we need to express two conditions for every person $x$:

1. Existence: There exists some $y$ who is the mother of $x$. $$\forall x \exists y (\operatorname{mother}(y, x))$$
2. Uniqueness: There is no other person $z$ (where $z \neq y$) who is also the mother of $x$. $$\forall z (z \neq y \rightarrow \neg \operatorname{mother}(z, x)) \quad \text{or} \quad \neg \exists z (z \neq y \wedge \operatorname{mother}(z, x))$$

Let us analyze each option based on these conditions:

• Option A: $\forall x \exists y \exists z(\operatorname{mother}(y, x) \wedge \neg \operatorname{mother}(z, x))$
  This states that for everyone $x$, there is some mother $y$, and there exists some person $z$ who is not the mother of $x$. This does not guarantee uniqueness, as $x$ could still have multiple mothers other than $z$.
  (Incorrect)
• Option B: $\forall x \exists y[\operatorname{mother}(y, x) \wedge \forall z( \operatorname{noteq} (z, y) \rightarrow \neg \operatorname{mother} (z, x))]$
  This states that for every $x$, there exists a $y$ who is the mother of $x$, and for any $z$, if $z \neq y$, then $z$ is not the mother of $x$. This perfectly captures both existence and uniqueness.
  (Correct)
• Option C: $\forall x \forall y[\operatorname{mother}(y, x) \rightarrow \exists z( \operatorname{mother} (z, x) \wedge \neg \operatorname{noteq}(z, y))]$
  Since $\neg \operatorname{noteq}(z, y)$ means $z = y$, this simplifies to: "If $y$ is the mother of $x$, then there exists some $z = y$ who is the mother of $x$". This is a tautology for anyone who has a mother and does not assert that everyone must have a mother, nor does it enforce uniqueness.
  (Incorrect)
• Option D: $\forall x \exists y[\operatorname{mother}(y, x) \wedge \neg \exists z( \operatorname{noteq}(z, y) \wedge \operatorname{mother} (z, x))]$
  This states that for every $x$, there exists a $y$ who is the mother of $x$, and there does not exist any $z$ such that $z \neq y$ and $z$ is the mother of $x$.
  Using the logical equivalence $\neg \exists z (P(z)) \equiv \forall z (\neg P(z))$, we have: $$\neg \exists z (\operatorname{noteq}(z, y) \wedge \operatorname{mother}(z, x)) \equiv \forall z (\operatorname{noteq}(z, y) \rightarrow \neg \operatorname{mother}(z, x))$$ This is logically equivalent to Option B.
  (Correct)