Quantifiable logic. Difference between $\forall y, \forall z(F(y,z) \implies Q(y)) $ and $\forall y, \exists z (F(y,z)\implies Q(y))$.

Question

I'm reading "how to prove it" and am struggling on the following question:

"Analyse the logical form: If anyone in the dorm has the measles, then everyone who has a friend in the dorm will have to be quarantined".

I came up with the following:

$\exists x(D(x) \land M(x))\implies \forall y ,\forall z ((F(y,z) \land D(z)) \implies Q(y))$

Where $D(x) = $ x is in the dorm, $M(x)=$ x has the measles, $F(y,z)=$ y is a friend of z, $Q(x)=$ x has to quarantine.

I looked up the answer online, and my answer is correct, except instead of $\forall z$ it is $\exists z$. I can't seem to work this out. Surely for all combinations of people y and z, if they are friends (ie: $F(y,z)$) then my statement/solution is correct.

Can somebody explain to me why we would use $\exists z$ instead of $\forall z$ in this case?

Answer 1

I'm guessing that you overlooked a difference in parentheses.

Your answer is

$$\forall y \forall z ((F(y,z) \land D(z)) \implies Q(y)),$$

and I'm guessing the answer in the book is

$$\forall y (\exists z (F(y,z) \land D(z)) \implies Q(y)).$$

Both of these sentences are equivalent, so both of them are correct. I like the second sentence better, since the phrase "who has a friend" sounds like existential quantification inside of the antecedent of an implication. But the first one is correct too.

On the other hand, the sentence

$$\forall y \exists z ((F(y,z) \land D(z)) \implies Q(y))$$

is completely different. This sentence says that for every person $y$, there is another person ($z$) who

• is not a friend of $y$, or
• does not live in the dorm, or
• will have to be quarantined.

If the answer key really does have the third sentence here, then that's probably a printing error.

---

By the way, here's how to show that the first two sentences are equivalent. We start with the sentence

$$\forall y \forall z ((F(y,z) \land D(z)) \implies Q(y)).$$

First, we rewrite the implication as disjunction:

$$\forall y \forall z (\neg (F(y,z) \land D(z)) \lor Q(y)).$$

Disjunction factors out of universal quantification:

$$\forall y (\forall z \ \neg (F(y,z) \land D(z)) \lor Q(y)).$$

De Morgan's law for quantifiers:

$$\forall y (\neg \exists z (F(y,z) \land D(z)) \lor Q(y)).$$

Finally, rewrite the disjunction as implication again:

$$\forall y (\exists z (F(y,z) \land D(z)) \implies Q(y)).$$