114 views
“Everyone has exactly one best friend”

Which of the following first order logic statements correctly represents above English statement?

$\text{BF(x,y)} = \text{x and y are best friends}$

$S1 : \forall x \exists y \forall z (BF(x,y) \wedge \neg BF(x,z) \implies (y \neq z))$

$S2: \forall x \exists y (BF(x,y) \implies \forall z [(y \neq z)] \implies \neg BF(x,z))$
| 114 views
0
i did not understood….implication is changed to OR right i.e. $\vee$ ?

in question A→ B→ C is given so how did you changed it to A $\wedge$ B → C ?
+1
given S2 is false because if for any x there isn’t any best friend then also S2 becomes true because $F \implies \text{anything}$ is true
0 Both are not true

+1
@Shaik

Some cases S2 can take AND value too.

right??

like, (x and y not BF) or (y and z are not same) , then x and z are not BF.

Here , if u take (x and y not BF)=True

(y and z are not same)=True

Then it can be also true x has no BF.

right??
0
i got it mam after mk comment !

+1 vote

$\text{BF(x,y)} = \text{x and y are best friends}$

$S1 : \forall x \exists y \forall z (BF(x,y) \wedge \neg BF(x,z) \implies (y \neq z))$

This statement says

for all  $x$ there exist a $y$ and for all $z$

if $(x$ and $y$ are best friends and if $x$ and $z$ are not best friends $)$ then this means that $y$ and $z$ are not same people.

which is trivially true.(how can $y$ be both best friend and NOT best friend of $x$ at same time)

So this statement is not equivalent to “Everyone has exactly one best friend”

$S2: \forall x \exists y (BF(x,y) \implies \forall z [(y \neq z)] \implies \neg BF(x,z))$

We can rewrite this as

$S2: \forall x \exists y (BF(x,y) \wedge \forall z [(y \neq z)] \implies \neg BF(x,z))$ (since implication has right asociatiivity)

This statement says

for all  $x$ there exist a $y$ such that

if $x$ and $y$ are best friends

AND

among all $z$ whichever $z$ we select is not equal to $y$ i.e. $y$ and $z$ are different people

then $x$ and $z$ can’t be best friends.

This statement is all not equivalent to “Everyone has exactly one best friend” because  if for any $x$ there isn’t any best friend then also $S2$ becomes true because $F⟹anything \equiv True \vee anything \equiv True$

Hence both $S1$ and $S2$ are not correct.

by (4.1k points)
edited by
0
in s1, let z is also BF of x…. Then ?
0
then z =y coz BF of x is y.
0
take y and z are two different persons….

don't forgot there is implies condition… in p->q, p fails.. No matter of what q is.
0

@shaik ...can you tell me what the statements s1 and s2 denotes ?

and where am i wrong in my explanation in the answer.

if BF(x,z) is also true then z=y.

taking contapositive of S1

$(y=z) \implies \sim BF(x,y) \vee BF(x,z) \equiv y=z \implies True$  i.e. y and z will be same person.

0

in the universe, there are many people.

let Satbir have two best friends i.e., MK and Sresta

For Statement 1 : let x = Satbir, y=MK and z = Sresta.

Then as per precedence AND logic evaluated first ! it leads to False

if  antecedent false, then no need to worry for  consequent.

Then x is satisfied your preposition.

0

Then as per precedence AND logic evaluated first ! it leads to False.

Ok and also $(y \neq z)$ is becoming true.

so statement S1 : becomes like  false → True = true or true = true.

I have written this only in my answer. I am not saying that $S1 =$ everyone has exactly one best friend.

Please give a counter example for $S2$

+1

after reading your answer, i thought, you conclude s1 is true…. infact you doesn’t conclude neither true nor false, you just read the statement, that’s it.

coming to s2 :-    implication have right associaitivity !

p->q->r ≡ p->(q->r) ≡ (p∧q) → r

from the comment of MK

given S2 is false because if for any x there isn’t any best friend then also S2 becomes true because F⟹ anything