Which of the following predicate logic formulae/formula is/are CORRECT…

GATE · 2025 · CS · Set 1 · Computer Science & IT

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:

• $𝑚𝑜𝑡ℎ𝑒𝑟(𝑦, 𝑥): 𝑦$ is the mother of $x$

• $𝑛𝑜𝑡𝑒𝑞(𝑥, 𝑦): 𝑥$ and $y$ are not equal

A.
$∀𝑥∃𝑦∃𝑧(𝑚𝑜𝑡ℎ𝑒𝑟(𝑦, 𝑥) ∧ ¬𝑚𝑜𝑡ℎ𝑒𝑟(𝑧, 𝑥))$
B.
$∀𝑥∃𝑦[𝑚𝑜𝑡ℎ𝑒𝑟(𝑦, 𝑥) ∧ ∀𝑧(𝑛𝑜𝑡𝑒𝑞(𝑧, 𝑦) → ¬𝑚𝑜𝑡ℎ𝑒𝑟(𝑧, 𝑥))]$
C.
$∀𝑥∀𝑦[𝑚𝑜𝑡ℎ𝑒𝑟(𝑦, 𝑥) → ∃𝑧(𝑚𝑜𝑡ℎ𝑒𝑟(𝑧, 𝑥) ∧ ¬𝑛𝑜𝑡𝑒𝑞(𝑧, 𝑦))]$
D.
$∀𝑥∃𝑦[𝑚𝑜𝑡ℎ𝑒𝑟(𝑦, 𝑥) ∧ ¬∃𝑧(𝑛𝑜𝑡𝑒𝑞(𝑧, 𝑦) ∧ 𝑚𝑜𝑡ℎ𝑒𝑟(𝑧, 𝑥))]$

Attempted by 117 students.

Sign up free to check your answer

Explore the full course: Gate Guidance By Sanchit Sir