Question about equivalence relation/bitstring

691 Views Asked by At

enter image description here

Actually i have no idea about this question.i know the definition of equivalence relations 1-) reflective 2-) symmetric 3-) transitive but not more :(

1

There are 1 best solutions below

1
On

HINT

OK, so you know the definition of an equivalence relation ... That it needs to be reflexive, symmetric, and transitive .. so just appl those definitions to this specific relation $R$:

Reflexive: Any bit string $x$ has the same number of $1$'s as $x$ itself.

Symmetric: If bit string $x$ has the same number of $1$'s as bit string $y$, then $y$ has the same number of $1$'s as $x$

Transitive: If bit string $x$ has the same number of $1$'s as bit string $y$, and bit string $y$ has the same number of $1$'s as $z$, then bit string $x$ has the same number of $1$'s as bit string $z$

Second question: Two bit strings $x$ and $y$ are in each other's equivalence class if and only if $xRy$, i.e. if and only if they have he same number of $1$'s.