Question

What are the equivalence classes of these bit strings forthe equivalence relation in Exercise 11?a)010b)1011c)11111d)01010101

Answer 1

Answer:

1. [010]_{R}  = { s ∈ A | the first three bits of s are 010}
2. [1011]_{R}  = { s ∈ A | the first three bits of s are 101}
3. [11111]_{R}  = { s ∈ A | the first three bits of s are 111}
4. [01010101]_{R}  = { s ∈ A | the first three bits of s are 010}

Explanation:

We say ∼ is an equivalence relation on a set A if it satisfies the following three properties:

a) reflexive: for all a∈A, a∼a.

b) symmetry: for all a,b∈A, if a∼b then b∼a.

c) transitivity: for all a,b,c∈A, if a∼b and b∼c then a∼c.

Given

A = Set of all bit strings that have a length of at least 3

R ={(x,y) first three bit of x and y are same

a) the equivalence classes of 010 will contain all bit strings that have as the first three digits 010

[010]_{R}  = { s ∈ A | the first three bits of s are 010}

b) the equivalence classes of 1011 will contain all bit strings that have as the first three digits 101

[1011]_{R}  = { s ∈ A | the first three bits of s are 101}

c) the equivalence classes of 11111 will contain all bit strings that have as the first three digits 111

[11111]_{R}  = { s ∈ A | the first three bits of s are 111}

d) the equivalence classes of 01010101 will contain all bit strings that have as the first three digits 010

[01010101]_{R}  = { s ∈ A | the first three bits of s are 010}

Answer 2

Answer:

d) 01010101

Explanation: