Are these two logical statements equivalent?

Question

The question is:

Translate the following into logical notation:

Nobody is despised who can manage a crocodile.

Given that:

• $D(x)$ = "$x$ is despised"
• $M(x)$ = "$x$ can manage a crocodile"

It states the answer as being $\forall x (M(x) \rightarrow \neg D(x))$. But would it also be acceptable to say:

$\neg \exists x (D(x) \land M(x))$

Answer 1

Yes. They are equivalent.

$\forall x (M(x) \rightarrow \neg D(x)) \\ \quad \Leftrightarrow \neg\exists x \neg(M(x) \rightarrow \neg D(x)) \\ \quad \Leftrightarrow \neg\exists x (M(x) \land \neg\neg D(x))\\ \quad \Leftrightarrow \neg\exists x (M(x) \land D(x))\\ \quad \Leftrightarrow \neg\exists x (D(x) \land M(x))$

The first equivalence comes from the familiar relation between the two quantifiers; the other equivalences should all look compelling given what you know about about e.g. the equivalence of $\neg(A \to B)$ and $(A \land \neg B)$.

(Careful: what I've just said is supposed to be motivational, give you a sense of why the equivalences hold. A proof in e.g. a natural deduction system will be more complicated since you can't apply connective rules directly to the innards of a wff inside the scope of a quantifier!)

Answer 2

Note that $$P \to Q \equiv \neg P \lor Q \tag 1$$ Also, note that $$\neg \exists x \, P (x) \equiv \forall x \neg P (x) $$

Thus, your books expression can be expressed as: $$\forall x (\neg D(x) \lor \neg M (x)) = \forall x (M (x) \to \neg D (x)) $$ the same as your expression.

Answer 3

Nobody is despised who can manage a crocodile

Given that:

D(x) = "x is despised"

M(x) = "x can manage a crocodile"

It states the answer as being $\forall x (M(x) \rightarrow \neg D(x))$

But would it also be acceptable to say $\neg \exists x (D(x) \land M(x))$

I would say that it would be a more direct translation, since it maintains the structure of the sentence being translated.   Vis: "There does not exist somebody who is despised and can manage a crocodile."

They are, however, both equivalent in first order predicate calculus, and some lecturers will prefer you to avoid leaving expressions with negated quantifiers as a matter of style.   So $\forall x~(M(x)\to\neg D(x))$ ie "Anybody who can manage a crocodile is not despised," is also viable.

Though so is the contraposition: $\forall x~(D(x)\to\neg M(x))$ ie "Anybody who is despised can not manage a crocodile."

Well, anyway, what ever final form is preferred by your lecturer, it never hurts to show your working in an exam or assignment.   (Indeed it is preferred that you do so.)

Answer 4

One nice way to see the two statements are equivalent is by using Venn Diagrams.

We can represent the sentence $\forall x (M(x) \rightarrow \neg D(x))$ in a Venn diagram as follows:

Explanation: When in a Venn diagram an area is shaded, that means that there do not exist any objects there. So, by shading the area that is both inside the '$M$' circle and inside the '$D$' circle, we are forcing that anything that is inside the '$M$' has to be outside the '$D$', and hence anything that is an '$M$' cannot be a '$D$' ... which is exactly what we want.

Now, compare this to the Venn Diagram for $\exists x (D(x) \land M(x))$:

This time, we put an 'X' in the intersection, indicating that there is at least one object there, capturing $\exists x (D(x) \land M(x))$

Now, if you compare the two Venn Diagrams, you'll notice that they are saying the exact opposite: one is saying that there is not a thing in the intersection, while the other is saying that is is a thing in the intersection. Thus, one is the negation of the other. And thus:

$\forall x (M(x) \rightarrow \neg D(x)) \Leftrightarrow \neg \exists x (D(x) \land M(x))$