The GATE Grind

GATE 2025 CS (CS1) – Question 48

Engineering Mathematics · Discrete Mathematics: Propositional and First Order Logic · 2 marks · Multiple select

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. $\forall x \exists y \exists z (mother(y,x) \wedge \neg mother(z,x))$
  2. $\forall x \exists y [mother(y,x) \wedge \forall z (noteq(z,y) \rightarrow \neg mother(z,x))]$
  3. $\forall x \forall y [mother(y,x) \rightarrow \exists z (mother(z,x) \wedge \neg noteq(z,y))]$
  4. $\forall x \exists y [mother(y,x) \wedge \neg\exists z (noteq(z,y) \wedge mother(z,x))]$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\forall x \exists y [mother(y,x) \wedge \forall z (noteq(z,y) \rightarrow \neg mother(z,x))]$; (D) $\forall x \exists y [mother(y,x) \wedge \neg\exists z (noteq(z,y) \wedge mother(z,x))]$

Explanation

'Exactly one' means some y is the mother and every other z is not. (B) and (D) state this and are logically equivalent. (A) only says someone is not a mother, and (C) is trivially satisfied by z=y and does not force existence.