# misinterpreting logic expression

Represent in first order logic

"Every person who dislikes all vegetarians is smart"

## My solution

$\forall x,y$ $person(x) \land vegetarian(y) \land dislike(x,y) \rightarrow smart(x)$

People say to me that this is not correct. I don't understand why?

Where is my misconception?

• Note that, one problem among many here (and as the answers all reveal): you need to be careful to use parentheses to enclose expressions. E.g., you need to use parentheses to make explicit the scope of a quantifier, to make explicit what is implying what, etc. Nov 24 '12 at 14:04

This sort of translation can be done easily if you take it in stages. Consider

(a) Every person who dislikes all vegetarians is smart

(b) $$\forall x$$( person-who-dislikes-all-vegetarians $$(x) \to smart(x))$$

(c) $$\forall x([person(x) \land \forall y\{(vegetarian(y) \to dislike(x, y)\}] \to smart(x))$$

The move from (a) to (b) needs no explanation, and the move from (b) to (c) just involves noting that person-who-dislikes-all-vegetarians $$(x)$$ says that $$x$$ is a person and for any vegetarian $$y$$, $$x$$ dislikes $$y$$. OK?

Now, that's fine and you can stop there. But suppose you wanted to bring the quantifers all to the front. Then (c) is equivalent to

(d) $$\forall x(\forall y[person(x) \land \{(vegetarian(y) \to dislike(x, y)\}] \to smart(x))$$

(Do you see why?) But now (d) is $$\forall x$$ followed by something of the form $$(\forall yFxy \to Gx)$$.

But now the crucial observation. $$(\forall yFxy \to Gx)$$ is equivalent to $$(\neg\forall yFxy \lor Gx)$$, which is equivalent to $$(\exists y\neg Fxy \lor Gx)$$ which is equivalent to $$\exists y(\neg Fxy \lor Gx)$$ which is equivalent to $$\exists y(Fxy \to Gx)$$. In short, dragging a quantifier out from the antecedent of a conditional flips it into the dual quantifier. That means (d) is equivalent to

(e) $$\forall x\exists y([person(x) \land \{(vegetarian(y) \to dislike(x, y)\}] \to smart(x))$$.

• +1Nicely explained!, especially the explicit "logic" behind how "dragging a quantifier out from an antecedent of a conditional flips it into the dual quantifier." (And nicely disambiguated, e.g., using parentheses to enclose the antecedent.) Nov 24 '12 at 14:00
• Your answer and that of henning was really really useful. I would both upvote you if I could. Thanks a lot! Nov 24 '12 at 20:15

Your solution claims that whenever there is someone who dislikes some vegetarian, the one doing the disliking is smart.

For example, suppose that indeed, everyone who dislikes all vegetarians is smart. Suppose further John is kinda stupid, and likes everybody except for Brian, who is a vegetarian. That is not a conflict, because John doesn't dislike all vegetarians: Henry is a vegetarian, and John likes him just fine. However your first-order formula is false in this situation.

It is false because the only thing that is needed to make a $\forall$ formula false is a single counterexample. And $x=\text{John}, y=\text{Brian}$ is a counterexample -- the body of the quantifier then becomes: $$\text{person(John)}\land\text{vegetarian(Brian)}\land\text{dislike(John,Brian)}\to\text{smart(John)}$$ and here all the conjuncts to the left of the $\to$ are true, but the conclusion on the right is not.

I suspect you started out fine with something like $$\forall x\big[\text{person}(x)\land\text{dislikes-all-vegetarians}(x)\to\text{smart}(x)\big]$$ but then you when wrong translating "dislikes-all-vegetarians". By itself it is $$\text{dislikes-all-vegetarians}(x) \equiv \forall y[\text{vegetarian}(y)\to \text{dislike}(x,y)]$$ and we can insert it into the first formula to get $$\forall x\big[\text{person}(x)\land\forall y[\text{vegetarian}(y)\to \text{dislike}(x,y)]\to\text{smart}(x)\big]$$ Note that here you cannot move the $\forall y$ out such that it is neighbor to the $\forall x$, because it is important for the meaning that $\forall y$ is subordinate to the $\rightarrow$ rather than the opposite.

We can insist on getting a logically equivalent formula where all quantifiers are out at the front (a "prenex formula"), but then the $\forall y$ becomes $\exists y$, which makes the result rather unrecognizable as a rendering of the original English sentence: $$\forall x \exists y \big[ \text{person}(x) \land [\text{vegetarian}(y) \to \text{dislike}(x,y)] \to \text{smart}(x)]\big]$$ or $$\forall x \exists y \big[ \text{person}(x) \to \text{smart}(x) \lor [\text{vegetarian}(y) \land \neg\text{dislike}(x,y)]\big]$$ (more or less "every person is smart unless (possibly) if there is a vegetarian he doesn't dislike").

$\forall x[ person(x) \rightarrow [\forall y[veg(y) \rightarrow dislike(x,y)]\rightarrow smart(x)]]$

• I am not sure if the statement you wrote is equivalent to mine. I will check
– Amr
Nov 24 '12 at 13:07
• Your statement is correct i think. And I can see why. But i cannot "intuitively" see why my solution is not correct Nov 24 '12 at 13:14
• Is this your statement $\forall x,y$[ $person(x) \land vegetarian(y) \land dislike(x,y) \rightarrow smart(x)]$?
– Amr
Nov 24 '12 at 13:16
• That is correct. Nov 24 '12 at 13:18