The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote

Que. Consider domain is the set of all people in the world.

$F(x,y) =x \text{ is the friend of y}.$ 

Represent each of the following sentences using first-order logic statements
$1.$ Every person has $at most \ 2$ friends.
$2.$ Every person has $exactly \ 2$ friends.
$3.$ Every person has $at least \ 2$ friends. 

My attempt –
$1. \forall x \exists y_1\exists y_2(F(x,y_1) \wedge F(x,y_2) \wedge \forall z(F(x,z) \implies ((z= y_1) \vee (z= y_2))))$
$2. \forall x \exists y_1\exists y_2(F(x,y_1) \wedge F(x,y_2) \wedge (y_1 \neq y_2) \wedge  \forall z(F(x,z) \implies ((z= y_1) \vee (z= y_2))))$
$3. \forall x \exists y_1\exists y_2(F(x,y_1) \wedge F(x,y_2) \wedge (y_1 \neq y_2))$

Please verify. 


asked in Mathematical Logic by Boss (15.5k points) | 85 views
Every person has $atmost$ 2 friends. - means he can have either 0, 1 or 2 friends. According to me it should be

$\forall x \exists y_1\exists y_2(F(x,y_1) \wedge F(x,y_2) \wedge \forall z(F(x,z) \implies (((z \neq y_1) \wedge (z \neq y_2))\vee (z= y_1) \vee (z= y_2)))))$

Let me know if i am making any mistake in this.

@!KARAN, I don't think so it will work. Try when x has 3 friends. 
There is a flaw in my formula too. It's not covering "0" case, 



For Statement 1, If you use "for all" symbol then it should work.

 $\forall x \forall y_1 \forall y_2(F(x,y_1) \wedge F(x,y_2) \wedge \forall z(F(x,z) \implies ((z= y_1) \vee (z= y_2))))$

or simply write- 

 $\forall x \forall y_1 \forall y_2 \forall z (F(x,y_1) \wedge F(x,y_2) \wedge F(x,z) \implies ((z= y_1) \vee (z= y_2)))$


Yes, it covers all the cases now. Thank you so much @Sachin   :)

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,430 questions
53,618 answers
70,892 users