GATE 2025 CS1 Q.48: solution and answer

GATE 2025 · CS1Q.48 · 2 marks · MSQ

Which of the following predicate logic formulae/formula is/are CORRECT representation(s) of the statement: "Everyone has exactly one mother"?

The meanings of the predicates used are:
- $m o t h er (y, x)$ : $y$ is the mother of $x$
- $n o t e q (x, y)$ : $x$ and $y$ are not equal

(A)
$\forall x \exists y \exists z (m o t h er (y, x) \land \neg m o t h er (z, x))$
(B)
$\forall x \exists y [m o t h er (y, x) \land \forall z (n o t e q (z, y) \to \neg m o t h er (z, x))]$
(C)
$\forall x \forall y [m o t h er (y, x) \to \exists z (m o t h er (z, x) \land \neg n o t e q (z, y))]$
(D)
$\forall x \exists y [m o t h er (y, x) \land \neg\exists z (n o t e q (z, y) \land m o t h er (z, x))]$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The correct options are B and D.

Official answer: B, DSource: Official answer key, GATE 2025 CS1 (IIT Roorkee)

"Exactly one mother" for every $x$ means two things: existence (some $y$ is a mother of $x$ ) and uniqueness (nobody other than $y$ is a mother of $x$ ). Target form: $\forall x \exists y [m o t h er (y, x) \land \forall z (n o t e q (z, y) \to \neg m o t h er (z, x))]$ .
(A) $\forall x \exists y \exists z (m o t h er (y, x) \land \neg m o t h er (z, x))$ says only that $x$ has some mother $y$ and that some $z$ is not a mother of $x$ . The second part is true in any world with at least two people, even if $x$ has ten mothers (take $y$ as one mother and $z$ as a non-mother). Uniqueness is not captured, so (A) is incorrect.
(B) $\forall x \exists y [m o t h er (y, x) \land \forall z (n o t e q (z, y) \to \neg m o t h er (z, x))]$ is exactly the target form: $y$ is a mother of $x$ , and every $z$ different from $y$ is not a mother of $x$ . Correct.
(C) $\forall x \forall y [m o t h er (y, x) \to \exists z (m o t h er (z, x) \land \neg n o t e q (z, y))]$ . Here $\neg n o t e q (z, y)$ means $z = y$ , so the consequent is $\exists z (m o t h er (z, x) \land z = y)$ , which is $m o t h er (y, x)$ . The formula reduces to $\forall x \forall y [m o t h er (y, x) \to m o t h er (y, x)]$ , a tautology. A person with no mother satisfies it vacuously, and so does a person with two mothers. It does not express "exactly one", so (C) is incorrect.
(D) $\forall x \exists y [m o t h er (y, x) \land \neg\exists z (n o t e q (z, y) \land m o t h er (z, x))]$ . Use $\neg\exists z P \equiv \forall z \neg P$ , then $\neg (a \land b) \equiv (a \to \neg b)$ . This gives $\forall z (n o t e q (z, y) \to \neg m o t h er (z, x))$ , which is the same as the inner part of (B). So (D) is equivalent to (B). Correct.
Hence the correct options are B and D.

KEY IDEA

"Exactly one" means existence plus uniqueness: some $y$ is the mother, and every $z$ different from $y$ is not. Writing uniqueness as $\forall z (z \neq = y \to \neg P (z))$ or as $\neg\exists z (z \neq = y \land P (z))$ gives equivalent formulas.

WATCH OUT FOR

Choosing (A) because it looks like "one mother and others are not mothers". Its $\neg m o t h er (z, x)$ only says some $z$ is not a mother, which does not limit the number of mothers. Another slip is reading $\neg n o t e q (z, y)$ in (C) as a real restriction, when it just means $z = y$ and makes the formula a tautology.

From the GATE 2025 CS1 paper. Every question of this paper · Download the full paper · All 7 Mathematical logic questions, with notes

GATE 2025 CS1 Q.48: solution and answer

Answer and solution

More Mathematical logic questions