10

How to convert an English sentence that contains "Exactly two" or "Atleast two" into predicate calculus sentence?

For example: There are two people with income less than 4K/year.

quid
  • 42,135
Alexander Suraphel
  • 653
  • 2
  • 5
  • 9

2 Answers2

18

"There are at least two objects satisfying P" can be expressed in first-order logic as $$\exists x \exists y (x \neq y \wedge P(x) \wedge P(y))$$

"There are exactly two objects satisfying P" can be dealt with by first rephrasing to "There are at least two objects satisfying P, but there are not at least three objects satisfying P" and using the above idea, or alternatively as $$\exists x \exists y ((x \neq y \wedge P(x) \wedge P(y)) \wedge \forall z (P(z) \rightarrow (z=x \vee z=y)))$$

Chris Eagle
  • 33,306
  • It was a question on a quiz and that's how I answered it. Thanks a lot! Can I trouble you with one more sentence? "Everyone who Mary loves loves someone who is happy." – Alexander Suraphel May 01 '12 at 13:35
  • 2
    @André, Your statement looks like a transcription of "Everyone who loves Mary loves someone who is happy," rather than what is asked. A sad truth about the world is that the "love" predicate is not symmetric. – user83827 May 01 '12 at 14:28
  • @ccc: Thanks, I misread the English, would have expected "whom Mary loves" if $L(m,x)$ was intended. But it is true that in colloquial spoken English, the who in "who Mary loves" means whom. – André Nicolas May 01 '12 at 14:38
  • 1
    @André: It's more than just colloquial spoken English: whom is disappearing from the written language as well, even in fairly formal registers. Many of those who retain it at all do so only after prepositions (to whom I gave it, but Who did you give it to). Holdouts like me who retain the full distinction are a vanishing breed. – Brian M. Scott May 01 '12 at 16:07
  • 1
    @Brian M. Scott: Someone to whom English is not the first language (it is in my case no higher than fourth) may pay insufficient attention to word order, and rely too much on grammatical distinctions. – André Nicolas May 01 '12 at 16:21
  • @André: I'm impressed: I'd guessed second, and an early second at that. – Brian M. Scott May 01 '12 at 16:23
  • @Brian M. Scott: Fairly early fourth. Prior schooling in only two others. – André Nicolas May 01 '12 at 16:37
5

Let's say your predicate is $P(x)$. Then here is "Exactly one $x$ satisfies $P$":

$$ \exists x. P(x)\\ \wedge (\forall y. P(y)\implies y=x)$$

That is, $P(x)$ holds, and if it holds for any $y$, then $y=x$.

Now let's do "Exactly two $x$ satisfy $P$":

$$ \exists x.\exists x'. P(x) \wedge P(x')\\ \wedge x\not= x' \\ \wedge(\forall y.P(y)\implies (y=x\vee y=x'))$$

That is, $x$ and $x'$ both satisfy $P$, they are different, and if $y$ satisfies $P$ then it must either be $x$ or $x'$.

Other formulations are possible.

MJD
  • 65,394
  • 39
  • 298
  • 580