GATE CS 2025 Set 1 | Question 48

MSQ · 2 marks

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:

  • \(mother(y, x)\): \(y\) is the mother of \(x\)
  • \(noteq(x, y)\): \(x\) and \(y\) are not equal
  1. Option A: \(\forall x \exists y \exists z \big(mother(y, x) \land \lnot mother(z, x)\big)\)
  2. Option B: \(\forall x \exists y \big[mother(y, x) \land \forall z \big(noteq(z, y) \to \lnot mother(z, x)\big)\big]\) (correct)
  3. Option C: \(\forall x \forall y [mother(y, x) \to \exists z (mother(z, x) \land \lnot noteq(z, y))]\)
  4. Option D: \(\forall x \exists y \big[mother(y, x) \land \lnot \exists z \big(noteq(z, y) \land mother(z, x)\big)\big]\) (correct)

Answer

(B), (D)

Explanation

“Exactly one mother” means: \(x\) has at least one mother \(y\), and nobody other than \(y\) is a mother of \(x\).

  • (A) False: it only says \(x\) has some mother \(y\) and some non-mother \(z\); a second mother is not ruled out.
  • (B) True: \(y\) is a mother of \(x\), and every \(z\) different from \(y\) is not a mother of \(x\).
  • (C) False: it says that if \(y\) is a mother of \(x\), then some \(z\) equal to \(y\) is a mother of \(x\). That is always true (take \(z = y\)), so it neither forces a mother to exist nor limits how many there are.
  • (D) True: \(\lnot \exists z\, (noteq(z, y) \land mother(z, x))\) is equivalent to \(\forall z\, (noteq(z, y) \to \lnot mother(z, x))\), so (D) says the same as (B).

Answer: B, D