I'm stuck on an undergraduate CS exercise: I am to translate "Everybody knows somebody who knows Alice" into predicate logic.

I'm having trouble bending my head around it (being a complete beginner), but this is what I'm thinking:

$x,y \in $ "the set of all people"
$A(y) = y$ knows Alice

$\forall x \exists !y A(y)$

However, this feels too cumbersome (if it's even valid), and I'm sure there must be a better, simpler way of doing it. Can anybody offer any suggestions?

  • 3
    $\begingroup$ You need a binary predicate symbol $K(x,y)$, to be read "$x$ knows $y$." $\endgroup$ – André Nicolas Nov 17 '13 at 21:13

You need a binary predicate (two-place), let's say, $K(x, y)\,$ to denote "$\;x\,$ knows $\,y$", and then we can simply use the constant $\,a\,$ to denote Alice.

You used the uniqueness quantifier $\exists!$, which is not appropriate here.

What we want is to say "For all $x$, there is some $y$ such that $x$ knows $y$, and $y$ knows Alice."

$$\forall x \,\exists y\,\Big(K(x, y) \land K(y, a)\Big)$$

  • 1
    $\begingroup$ I didn't realise I could do it that way! Thanks a lot! Out of interest, why is the uniqueness identifier inappropriate? Is it because "somebody" could mean more than one person? $\endgroup$ – Jacob Nov 17 '13 at 21:18
  • $\begingroup$ You're welcome, Jacob! $\endgroup$ – Namaste Nov 17 '13 at 21:24
  • 1
    $\begingroup$ @Jacob : Yes, somebody means "any number greater or equal than 1". $\endgroup$ – Fezvez Nov 17 '13 at 22:44
  • $\begingroup$ @Jacob Yes, "exists someone" means "there is at least one person". If the problem made explicit that there is one and only one person that x knows, or stated "Everyone knows exactly one person that knows Alice"...then we would need the uniqueness quantifier. $\endgroup$ – Namaste Nov 17 '13 at 22:48
  • $\begingroup$ @amWhy: Right up your alley! +1 $\endgroup$ – Amzoti Nov 18 '13 at 0:09

You need a two-place predicate $K(x,y)$ that means ‘$x$ knows $y$’. You want

$$\forall x\,\exists y\Big(K(x,y)\land\text{something}\Big)\;,$$

where I’ve left $\text{something}$ for you to fill in. So far it just says that each person $x$ knows someone ($y$). You’ll need a constant, $\text{Alice}$, as well as the predicate $K$.

  • $\begingroup$ Thanks! I've accepted @amWhy's answer because it's more complete, but I do appreciate you leaving something to work out. $\endgroup$ – Jacob Nov 17 '13 at 21:24
  • $\begingroup$ @Jacob: You’re welcome. $\endgroup$ – Brian M. Scott Nov 17 '13 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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