Predicates and Quantifiers in discrete math

291 Views Asked by At

Let P(x,y) be "x is waiting for y", where the universe of discourse is the set of all people in the world. Use quantifiers to express the following statement. (i)There is no one who is waiting for everybody. (ii) Everybody is waiting for somebody.

May i know how to solve this kind of question?

1

There are 1 best solutions below

6
On BEST ANSWER

I would approach it as follows:

(i) "There is no one who is waiting for everybody." Meaning: There does not exist a person (i.e., $\nexists x$) who is waiting for everybody (i.e., $\forall y$). Thus, for (i), we get the following: $\nexists x \forall y P(x,y)$. However, you may want to report the answer without any negated quantifiers; in such a case, you may observe the following: $$ \neg(\nexists x \forall y P(x,y)) = (\neg \nexists x)(\exists y)\neg P(x,y) = \exists x \exists y \neg P(x,y), $$ where $\neg P(x,y)$ is taken to mean "$x$ is not waiting for $y$."

(ii) "Everybody is waiting for somebody." Meaning: There exists someone (i.e., $\exists y$) who is being waited for by everyone (i.e., $\forall x$). Thus, the reported answer for (ii) would be $\exists y \forall x P(x,y)$. Note that the order of quantifiers is important here.

This is how I would answer it anyway.