Notices
Results 1 to 2 of 2

Thread: Regarding Discrete Mathematics Questions (Relation Question)

  1. #1 Regarding Discrete Mathematics Questions (Relation Question) 
    Forum Freshman
    Join Date
    Oct 2012
    Posts
    18
    Relation R defined on the set of seven-bit strings by s1Rs2, provided that the first four bits of s1 and s2 coincide

    (i) Show that R is anequivalence relation.

    (iii) List one (1) member of each equivalence class.


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Freshman
    Join Date
    Jan 2013
    Posts
    34
    I answered this on another board but:
    To be an equivalence relation R must be
    1) Reflexive. For any x, we must have xRx.
    That's easy to prove. Comparing such a string to itself, all bits are the same so certainly the first four bits are.

    2) Symmetric. If xRy then yRx.
    Again, easy. If xRy then x has the same first four bits as y. . But "=" is symmetric (it is the "ideal" equivalence relation) so . That is yRx.

    4)Transitive. If xRy and yRz then xRz. If xRy then . If yRz then . Again "=" is transitive so . That is, xRz.

    Two bitstrings are "equivalent" if the first four bits are the same. There are different 4 bit strings. They are
    0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, and 1111.
    So there are 16 equivalence classes. We can list one member of each by appending any three bits we like to the end of those. I choose 000:
    0000000
    0001000
    0010000
    0011000
    0100000
    0101000
    0110000
    0111000
    1000000
    1001000
    1010000
    1011000
    1100000
    1101000
    1110000
    1111000

    are one member of each of the 16 equivalence classes.


    Reply With Quote  
     

Similar Threads

  1. Continuous is lesser than Discrete?...
    By Wise Man in forum Mathematics
    Replies: 8
    Last Post: April 23rd, 2013, 06:44 PM
  2. Replies: 5
    Last Post: September 13th, 2012, 04:14 AM
  3. Thermometer! Discrete or continuous?
    By davedave4619 in forum General Discussion
    Replies: 6
    Last Post: March 4th, 2007, 10:52 AM
  4. Discrete Fourier Transform as an interpolater
    By wonkothesane in forum Mathematics
    Replies: 1
    Last Post: March 4th, 2007, 05:16 AM
Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •