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(x, y): x is the mother of y - noteq(x, y): x and y are not equal A. forall y exists x [mother(x,y) ^ forall z (mother(z,y) -> z=x)] B. forall y exists x [mother(x,y) ^ forall z (noteq(z,x) -> ~mother(z,y))] C. forall y exists x [mother(x,y) ^ forall z (mother(z,y) -> noteq(z,x))] D. forall y [exists x mother(x,y) ^ forall x forall z ((mother(x,y) ^ mother(z,y)) -> x=z)]
GATE 2025 · Discrete Mathematics · First Order Logic · medium
Answer: Options B and D are correct representations. Answer: B, D.
- Analyse option A: A: forall y exists x [mother(x,y) ^ forall z (mother(z,y) -> z=x)]. The inner formula says any z who is a mother of y must equal x. This is the standard unique-existence pattern using = directly. Option A is CORRECT.
- Analyse option B: B: forall y exists x [mother(x,y) ^ forall z (noteq(z,x) -> ~mother(z,y))]. noteq(z,x) means z!=x; so forall z (z!=x -> ~mother(z,y)) means no entity different from x is a mother of y. This is exactly the unique-existence pattern written with noteq instead of =. Option B is CORRECT.
- Analyse option C: C: forall y exists x [mother(x,y) ^ forall z (mother(z,y) -> noteq(z,x))]. The inner implication mother(z,y) -> noteq(z,x) means any mother z of y is different from x. But x itself is also a mother of y, and noteq(x,x) is false, causing a contradiction. This formula is unsatisfiable (or incorrectly forces x != x). Option C is INCORRECT.
- Analyse option D: D: forall y [exists x mother(x,y) ^ forall x forall z ((mother(x,y) ^ mother(z,y)) -> x=z)]. The first conjunct asserts existence; the second asserts that any two mothers of y are identical, i.e., uniqueness. Together they correctly say 'exactly one mother'. Option D is CORRECT.