# Thread: Regarding Discrete Mathematics Questions (Relation Question)

1. 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.

2.

3. 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.

 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   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement