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.

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?

share|improve this question
3  
You need a binary predicate symbol $K(x,y)$, to be read "$x$ knows $y$." –  André Nicolas Nov 17 '13 at 21:13
add comment

2 Answers

up vote 12 down vote accepted

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

share|improve this answer
1  
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? –  Jacob Walker Nov 17 '13 at 21:18
    
You're welcome, Jacob! –  amWhy Nov 17 '13 at 21:24
1  
@Jacob : Yes, somebody means "any number greater or equal than 1". –  Fezvez Nov 17 '13 at 22:44
    
@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. –  amWhy Nov 17 '13 at 22:48
    
@amWhy: Right up your alley! +1 –  Amzoti Nov 18 '13 at 0:09
show 1 more comment

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

share|improve this answer
    
Thanks! I've accepted @amWhy's answer because it's more complete, but I do appreciate you leaving something to work out. –  Jacob Walker Nov 17 '13 at 21:24
    
@Jacob: You’re welcome. –  Brian M. Scott Nov 17 '13 at 21:28
add comment

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.