Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  amWhy Nov 24 '12 at 14:04

3 Answers 3

up vote 3 down vote accepted

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))$.

I hope that, along with Henning's answer, shows why your original answer was mistaken!

share|improve this answer
    
+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.) –  amWhy 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! –  tgoossens 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").

share|improve this answer

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

share|improve this answer
    
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 –  tgoossens 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. –  tgoossens Nov 24 '12 at 13:18
2  
The other answer explains your mistake well –  Amr Nov 24 '12 at 13:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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