Relation of eight bit strings

**whyyie** · June 13th 2012, 11:25 PM

Let R be the relation defined on the set of eight-bits strings by s1RS2
provided that s1 and s2 have the same number of zeros.
(a) Show that r is an equivalent relation.
(b) How many equivalence classes are there?
(c) List one member of each equivalence class.

**tom@ballooncalculus** · June 14th 2012, 01:25 AM

**emakarov** · June 14th 2012, 03:30 AM

The following remark is probably not very suitable to the level of the question, but if there is some function f : X -> Y, then the relation x₁ R x₂ defined by f(x₁) = f(x₂) is an equivalence relation. It is important that f is a function, not a general relation.

**Soroban** · June 14th 2012, 07:33 AM

Hello, whyyie!

$\text{Let }\mathbb{R}\text{ be the relation defined on the set of eight-bits strings by: }\,s_1\mathbb{R}s_2$
$\text{provided that }s_1\text{ and }s_2\text{ have the same number of zeros.}$

$\text{(a) Show that }\mathbb{R}\text{ is an equivalence relation.}$

$\text{Reflexive: }\:s_1\mathbb{R}s_1$
. . $s_1\text{ has the same number of zeros as }s_1\text{ . . . Yes}$

$\text{Symmetric: }\:\text{If }s_1\mathbb{R}s_2\text{, then }s_2\mathbb{R}s_1$
. . $\text{If }s_1\text{ and }s_2\text{ have equal zeros, then }s_2\text{ and }s_1\text{ have equal zeros . . . Yes}$

$\text{Transitive: }\:\text{If }s_1\mathbb{R}s_2\text{ and }s_2\mathbb{R}s_3\text{, then }s_1\mathbb{R}s_3.$
. . $\text{If }s_1\text{ and }s_2\text{ have equal zeros and }s_2\text{ and }s_3\text{ have equal zeros,}$
. . $\text{then }r_1\text{ and }r_3\text{ have equal zeros . . . Yes}$

$\text{Therefore, }\mathbb{R}\text{ is an equivalence relation.}$

(b) How many equivalence classes are there?

Nine.

(c) List one member of each equivalence class.

$\begin{array}{cc} \text{no zeros} & 11111111 \\ \text{1 zero} & 01111111 \\ \text{2 zeros} & 00111111 \\ \vdots & \vdots \\ \text{7 zeros} & 00000001 \\ \text{8 zeros} & 00000000 \end{array}$

Thread: Relation of eight bit strings

LinkBack

Thread Tools

Display

Relation of eight bit strings

Re: Relation of eight bit strings

Re: Relation of eight bit strings

Re: Relation of eight bit strings

Similar Math Help Forum Discussions

How many eight-bit strings contain exactly three 0's

Bit strings

How many bit strings of length 10....

recurrence relation bit strings

strings

Search Tags