Computer Sciences > GATE 2025 SET-1 > Predicate Logic
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
A
∀x∃y∃z (mother(y,x) ∧ ¬mother(z,x))
B
∀x∃y [mother(y,x) ∧ ∀z (note q(z,y) → ¬mother(z,x))]
C
∀x∀y [mother(y,x) → ∃z (mother(z,x) ∧ ¬note q(z,y))]
D
∀x∃y [mother(y,x) ∧ ¬∃z (note q(z,y) ∧ mother(z,x))]

Correct : b

This question is about expressing "exactly one" in predicate logic — which is one of the most commonly tested concepts in GATE discrete mathematics. "Exactly one" means two things at once: at least one exists, and no second one exists. Both parts must appear in the formula for it to be correct.
Let''s go through each option carefully.
Option A — ∀x∃y∃z(mother(y,x) ∧ ¬mother(z,x))
This says: for every x, there exists some y who is a mother of x, and there exists some z who is NOT a mother of x. The problem here is that z could be anyone — even x itself or some random person. This formula doesn''t say anything about y being the only mother. It completely fails to capture uniqueness, making Option A incorrect.
Option B — ∀x∃y[mother(y,x) ∧ ∀z(noteq(z,y) → ¬mother(z,x))]
This is the correct one. It reads: for every person x, there exists a y who is the mother of x, and for every z that is different from y, z is NOT the mother of x. The first part guarantees existence, and the second part guarantees uniqueness — no one other than y can be the mother of x. This is a textbook representation of "exactly one" and is correct.
Option C — ∀x∀y[mother(y,x) → ∃z(mother(z,x) ∧ ¬noteq(z,y))]
Let''s unpack this carefully. ¬noteq(z,y) means z and y are equal. So the formula says: for every x and y, if y is the mother of x, then there exists a z who is also the mother of x and z equals y. This is essentially just saying "if y is a mother of x, then y is a mother of x" — a tautology that says nothing about uniqueness or even existence. This is incorrect.
Option D — ∀x∃y[mother(y,x) ∧ ¬∃z(noteq(z,y) ∧ mother(z,x))]
This says: for every x, there exists a y who is the mother of x, and there is no z different from y who is also the mother of x. This is logically equivalent to Option B — the only difference is that uniqueness is expressed using ¬∃ instead of ∀...→¬. Since ¬∃z P(z) is the same as ∀z ¬P(z), both formulas say the same thing. So Option D is also a correct representation.
The official GATE key marks Option B as the answer, though Option D is equally valid logically. In GATE MSQ questions, both would be accepted. The key insight to remember - whenever you see "exactly one" in a logic question, immediately think: existence + uniqueness, and make sure both are present in the formula you pick.

Similar Questions

A palindrome is a word that reads the same forwards and backwards. In a game of words, a player has the following two plates painted with letters. From...
#1 MCQ
Which number does not belong in the series below? 2, 5, 10, 17, 26, 37, 50, 64
#4 MCQ
Choose the word that is opposite in meaning to the word “coherent”.
#5 MCQ

Related Topics

predicate logic GATE 2025 GATE CS 2025 Set-1 Q48 exactly one mother predicate logic first order logic GATE universal existential quantifier mother predicate noteq predicate uniqueness in predicate logic discrete mathematics GATE GATE computer science 2025

Unique Visitor Count

Total Unique Visitors

Loading......