Results 1 to 4 of 4

Math Help - Relation of eight bit strings

  1. #1
    Newbie
    Joined
    Jun 2012
    From
    -
    Posts
    11

    Relation of eight bit strings

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2008
    Posts
    1,034
    Thanks
    49

    Re: Relation of eight bit strings

    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Relation of eight bit strings

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,683
    Thanks
    615

    Re: Relation of eight bit strings

    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}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How many eight-bit strings contain exactly three 0's
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 4th 2010, 08:06 AM
  2. Bit strings
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 10th 2009, 11:07 AM
  3. How many bit strings of length 10....
    Posted in the Statistics Forum
    Replies: 1
    Last Post: February 22nd 2009, 05:52 PM
  4. recurrence relation bit strings
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 28th 2009, 12:49 AM
  5. strings
    Posted in the Statistics Forum
    Replies: 10
    Last Post: January 17th 2009, 12:35 PM

Search Tags


/mathhelpforum @mathhelpforum