Question

Hello, I need help with the following Discrete problem. Please show your work, thank you!

11. Let R be the relation defined on the set of eight-bit strings by Si R 52 provided that sy and sz have the same number of zeros. (a) Show that is an equivalence relation. (b) How many equivalence classes are there? (c) List one member of each equivalence class.

Answer 1

From the information given above, The relation R defined on sets which has same number of zeros.

(a)

To prove R is an equivalence relation we need to show

• R is Reflexive
• R is Symmetric
• R is Transitive.

Reflexive: $s_{1}\mathbb{R}s_{1}$

$\mathbb{R}$ is reflexive because s₁ has same number of zero as s1 i.e, s₁ has same number of zeros as itself which is trivial and true.

Therefore, R is reflexive.

Symmetric:    
siRsz then s2Rs1

Given that in Relation R s₁ and s₂ has equal number of zeros.

So, If s₁ has equal number of zero's as s₂, then s₂ will also have equal number of zeros's as s₁.

Therefore, Relation $\mathbb{R}$ is symmetric.

Transitive:

if siRs, and S Rs3 then siRs3

If s1 and s2 has same number of zeros and s2 and s3 has same number of zeros then s1 and s3 will have same number of zeros which is true.

Therefore, $\mathbb{R}$ is Transitive.

Therefore, The given Relation $\mathbb{R}$ is equivalence relation.

(b)

The number of zeros in a equivalence class can be 0, 1, 2, 3, 4 , 5, 6, 7, 8

equivalence class with no zeros, one zeros and so on till equivalence class with eight zeros.

So, there are 9 equivalence classes possible for given relation R.

Therefore, there are 9 equivalence classes possible for given relation R.

(c)

Equivalence Class	Member
No zeros	11111111
1 zero	11111110
2 zeros	11111100
3 zeros	11111000
4 zeros	11110000
5 zeros	11100000
6 zeros	11000000
7 zeros	10000000
8 zeros	00000000