Awesome q2a theme
0 votes
77 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))  $
in Mathematical Logic by (302 points) | 77 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 Answer

+1 vote
Best answer

$\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 (3.7k 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

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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Dec 2019
  1. Pratyush Priyam Kuan

    158 Points

  2. Vimal Patel

    118 Points

  3. avistein

    65 Points

  4. srestha

    54 Points

  5. Mk Utkarsh

    49 Points

  6. arya_stark

    46 Points

  7. goxul

    39 Points

  8. Sathuri Bharath

    34 Points

  9. vishal burnwal

    31 Points

  10. Shaik Masthan

    26 Points

Monthly Top User and those within 60% of his/her points will get a share of monthly revenue of GO subject to a minimum payout of Rs. 500. Current monthly budget for Top Users is Rs. 75.
2,315 questions
1,294 answers
6,592 comments
89,719 users