106 views

Assume the specifications

• $F(x,y) : x$ is the father of $y$
• $M(x,y) : x$ is the mother of $y.$

Which of the formulas in predicate logic below express the sentence 'Everybody has a mother'?

1. $\exists x \forall y M(x, y)$
2. $\exists y \forall x M(x, y)$
3. $\forall x \exists y M(x, y)$
4. $\forall y \exists x M(x, y)$

### Subscribe to GO Classes for GATE CSE 2022

Option D Explanation -
The formula $\forall y \exists x M(x, y)$

• literally says 'For all $y$ there is some $x$ such that $x$ is a mother of $y$'.
• We can express this sentence more elegantly as 'Everyone has a mother'

which is the sentence we meant to express.

Option A Explanation -
The formula $\exists x \forall y M(x, y)$

• literally says 'There is some $x$ such that for all $y, x$ is a mother of $y$'.
• We can express this sentence more elegantly as 'Somebody is everybody's mother'.

Not only does this sentence not say what we want, but it also ignores most properties of motherhood.

Option B Explanation -
The formula $\exists y \forall x M(x, y)$

• literally says 'There is some $y$ such that for all $x, x$ is a mother of $y'$.
• We can express this sentence more elegantly as 'Somebody has everyone as their mother'.

Not only does this sentence not say what we want, but it also ignores most properties of motherhood.

Option C Explanation -
The formula $\forall x \exists y M(x, y)$

• literally says 'For all $x$ there is some $y$ such that $x$ is a mother of $y$'.
• We can express this sentence more elegantly as 'Everyone is a mother'.

Not only does this sentence not say what we want, but it also ignores that not all people are mothers.

For Practice -
The formula $\forall x \forall y M(x, y)$

• literally says 'For all $x$ and all $y, x$ is a mother of $y$'.
• We can express this sentence more elegantly as 'Everybody is the mother of everybody else'.

Not only does this sentence not say what we want, but it also ignores all properties of motherhood.

1
164 views