GATE2025_CS1_Q48

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

Note: This is a Multiple Select Question (MSQ). One or more options may be correct.

✅ Final Answer:

The correct options are (B) and (D).

🔹 Short Answer:

The statement "Everyone has exactly one mother" breaks down into two conditions for every person `x`: (1) Existence of a mother, and (2) Uniqueness of that mother. Both options (B) and (D) correctly capture these two conditions. They both assert that "for all x, there exists a y who is the mother of x," and then add a uniqueness clause. Option (B) states uniqueness as "any person z different from y cannot be the mother," while option (D) states it as "there does not exist any person z different from y who is also the mother." These two clauses are logically equivalent.

🔸 Long Answer:

To translate "Everyone has exactly one mother," we need to express two ideas for every individual `x`:

1. Existence: There is at least one mother. (`∃y mother(y,x)`)
2. Uniqueness: There is at most one mother. (`∀z(mother(z,x) → z=y)`)

Combining these gives the standard logical form: ∀x ∃y (mother(y,x) ∧ ∀z(mother(z,x) → z=y)). Let's analyze each option against this structure.

Analysis of Options

A. ∀x∃y∃z(mother(y, x) ∧ ¬mother(z, x))

This translates to: "For every person x, there exists a person y and a person z such that y is the mother of x and z is not the mother of x." This only ensures that the set of "mothers of x" is not the set of all people. It does not prevent x from having multiple mothers. Therefore, it is incorrect.

B. ∀x∃y[mother(y, x) ∧ ∀z(noteq(z, y) → ¬mother(z,x))]

• ∀x∃y[mother(y, x) ... ]: This part handles existence ("Everyone has a mother").
• ... ∧ ∀z(noteq(z, y) → ¬mother(z,x))]: This part handles uniqueness. It says, "for any individual z, if z is not y, then z is not the mother of x." This is a perfect way to state that only y can be the mother. This clause is the contrapositive of, and thus logically equivalent to, our standard uniqueness clause ∀z(mother(z,x) → z=y).

Since this option correctly captures both existence and uniqueness, it is CORRECT.

C. ∀x∀y[mother(y, x) → ∃z(mother(z, x) ∧ ¬noteq(z,y))]

The predicate ¬noteq(z,y) is equivalent to z=y. Substituting this in, the consequent becomes ∃z(mother(z, x) ∧ z=y), which simplifies to just mother(y,x). The entire formula is thus ∀x∀y[mother(y, x) → mother(y, x)]. This is a tautology (a statement that is always true, like P→P) and does not convey the specific meaning of the English sentence. Therefore, it is incorrect.

D. ∀x∃y[mother(y, x) ∧ ¬∃z(noteq(z, y) ∧ mother(z,x))]

• ∀x∃y[mother(y, x) ... ]: This part, again, handles existence.
• ... ∧ ¬∃z(noteq(z, y) ∧ mother(z,x))]: This is an alternative way to express uniqueness. It says, "...and it is not the case that there exists an individual z such that z is different from y AND z is the mother of x." In simpler terms: "There isn't another person who is also the mother."

This is logically equivalent to the uniqueness clause in option (B). Using the quantifier negation rule (¬∃P ⇔ ∀¬P), we can see: ¬∃z(noteq(z, y) ∧ mother(z,x)) is equivalent to ∀z(¬(noteq(z, y) ∧ mother(z,x))), which is ∀z(z=y ∨ ¬mother(z,x)), which simplifies to ∀z(mother(z,x) → z=y). This confirms it correctly states uniqueness. Therefore, this option is also CORRECT.

Bibliography:
- Rosen, K. H. (2018). Discrete Mathematics and Its Applications. McGraw-Hill Education. (Chapter 1: The Foundations: Logic and Proofs).
- Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning.

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.