Negating Quantified Statements

Express each of these statements using quantifiers. Then form the negation of the statement so that no negation is to the left of a quantifier. Next, express the negation in simple English. (Do not simply use the phrase “It is not the case that.”)

b) There is a student in this class who has chatted with exactly one other student.

I was able to correctly translate the statement, the answer being $\displaystyle \exists x \exists y (Q(x,y) \wedge \forall z(Q(x,z) \rightarrow y = z))$, where Q(x,y) represents, "x has chatted with y."

When I alter the statement by negating it, it becomes $\displaystyle \forall x \forall y (Q(x,y) \rightarrow \exists z(Q(x,y) \vee y \ne z ))$ (this required a few propositional equivalences to get to this state.) The difference between my answer and the true answer is, that the disjunction is actually a conjunction.

What did I do wrong?

Re: Negating Quantified Statements

Quote:

Originally Posted by

**Bashyboy** Express each of these statements using quantifiers. Then form the negation of the statement so that no negation is to the left of a quantifier. Next, express the negation in simple English. (Do not simply use the phrase “It is not the case that.”)

b) There is a student in this class who has chatted with exactly one other student.

I was able to correctly translate the statement, the answer being $\displaystyle \exists x \exists y (Q(x,y) \wedge \forall z(Q(x,z) \rightarrow y = z))$, where Q(x,y) represents, "x has chatted with y."

When I alter the statement by negating it, it becomes $\displaystyle \forall x \forall y (Q(x,y) \rightarrow \exists z(Q(x,y) \vee y \ne z ))$ (this required a few propositional equivalences to get to this state.) The difference between my answer and the true answer is, that the disjunction is actually a conjunction.

It is very very basic: $\displaystyle \neg \left[ {A \wedge (B \to C)} \right] \equiv \neg A \vee \left( {B \wedge \neg C} \right)$

Re: Negating Quantified Statements

Oh, yes. You are very right: it is basic. Thank you very much for the clarification.