The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes


Everyone has exactly one best friend

Which of the following first order logic statements correctly represents above English statement? $BF(x,y)$  means $x$ and $y$ are best friends

  • $S1 : \forall x \exists y \forall z (BF(x,y) \wedge \sim BF(x,z) \rightarrow (y \neq z))$
  • $S2 : \forall x \exists y (BF(x,y)\rightarrow \forall z [(y \neq z)] \rightarrow \sim BF(x,z))$
  1. Only $S1$
  2. Only $S2$
  3. Both $S1$ and $S2$
  4. None of the two
asked in Mathematical Logic by Boss (15.3k points)
edited by | 137 views

@Soumya29 PLease guide with this 



2nd : False

if x does not have any best friend (y), then statement is becoming false and overall giving TRue., same reason with 1st option


@Learner_jai answered. Check it,

1 Answer

+4 votes
Answer- Option $D$
$\text{Everyone has exactly one best friend}$

We can express it as -

$\forall x \exists y(BF(x,y) \wedge \forall z(BF(x,z) \rightarrow (y = z)))$

$\text{OR equivalently we can write it as - }$

$\forall x \exists y(BF(x,y) \wedge \forall z( (y \neq z)\rightarrow \sim BF(x,z)))$

$S1 - $ It is same as -$\forall x \exists y \forall z ((BF(x,y) \wedge \sim BF(x,z) )\rightarrow (y \neq z))​​​​​​ $
It is false because if some person has no best friend then LHS will be false so overall statement becomes true.

$S2-$ is false. Same reasoning as above.
answered by Boss (15.3k points)

@Soumya29 @akash.dinkar12 @register_user_19


Here in this equation which has highest precedence is it    $\wedge$  or  $\rightarrow$. Lets say there is no bracket defined then which one should be considered.

As given in book the precedence of operators is this

~ , $ \wedge , \vee , \Rightarrow , \Leftrightarrow$



I removed brackets here - $\forall x \exists y(BF(x,y) \wedge \forall z \ BF(x,y) \rightarrow (y=z))$
Now, $ \forall$ is applicable only on $BF(x,z).$
 And  will take this 2 -$ BF(x,y) \wedge \forall z \ BF(x,y)$


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
48,515 questions
52,763 answers
68,234 users