2
$\begingroup$

The question is from Exercise 13 of part 1.4 in Rosen's "Discrete Mathematics and Its Applications" (5th edition): "let $M(x,y)$ be "$x$ has sent y an e-mail message", where the universe of discourse consists of all students in your class".

The sentence to be translated to predicate language is: "g) there is a student in your class who has sent everyone else in your class an e-mail message"

My solution is:

$$\exists x \ \forall y \ \ (M(x,y)\implies x \neq y) $$

The solution in the instructor's manual of Rosen's book has the statements of the implication in reverse:

$$\exists x \ \ \forall y \ \ (x \neq y \implies M(x,y))$$

Which one is correct? To me it seems that the solutions manual is incorrect. The solution from the manual is true if the antecedent is F and the consequent T, which would mean that if the student is himself/herself, then he/she has sent himself/herself an e-mail message, so it seems to be wrong in my mind because the original idea was to exclude sending messages to oneself. The first solution allows x to send y an e-mail message only if it is not sent to oneself and if the e-mail is not sent, then it doesn't matter to whom it is sent.

$\endgroup$
2
$\begingroup$

An other approach by the writing the negation of your statement and the book's statement :

  • The negation of $\exists x \ \forall y \ \ (M(x,y)\implies x \neq y) $ is : For all $x$ there exist $y$ such that $x$ sent $y$ an email and ($x$ and $y$ is the same person).

In other word :

For all $x$, $x$ sent an email to himself.

  • The negation of $\exists x \ \ \forall y \ \ (x \neq y \implies M(x,y))$ is :

For all $x$ there exist $y$ such that $x$ is different from $y$ and $x$ didn't send an email to $y$

In other word :

For all $x$ there exist $y$ different from $x$ such that $x$ didn't send an email to $y$.

You can see that this second statement is the exact negation of the one wanted.

Note that for the statement of the negation I used the fact that $(P \Longrightarrow Q)$ is the same as $\lnot P \vee Q$

$\endgroup$
  • $\begingroup$ Ok, so the negation of $\exists x \ \forall y \ \ (M(x,y)\implies x \neq y) $ is $\forall x \ \exists y \ \ (M(x,y) \land x = y \ ) $ and the negation of $\exists x \ \ \forall y \ \ (x \neq y \implies M(x,y))$ is $\forall x\ \exists y \ \ (x \neq y \land \neg M(x,y))$. Now it is much clearer for me $\endgroup$ – MPO Aug 3 '15 at 10:43
  • $\begingroup$ That's right. I am happy to hear that. I want to point out to pay attention to the quantifiers if they rule $P$ only or the whole implication as they do in this case. $\endgroup$ – Aymane Fihadi Aug 3 '15 at 11:13
2
$\begingroup$

Statement $1$ is $\exists x\forall y (M(x,y) \implies x\ne y)$

This can be interpreted as:

There exists a student such that for all students, if student $x$ has sent student $y$ an email, student $x$ is not student $y$.

This doesn't implies that the student has sent everyone but themselves an email, or even any student an email, just that they haven't sent an email to themselves.

Statement $2$ is $\exists x\forall y (x\ne y \implies M(x,y))$

This is correct. It can be interpreted as:

There exists a student $x$ such that for all students, if student $x$ is not student $y$, then they have sent student $y$ an email.

And statement $2$ also means that student $x$ has not sent an email to themselves.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.