Mostre que a relação R, que consiste em todos os pares (x, y) tal que x e y são seqüências de bits de comprimento maior que ou igual a 3, que coincidem em seus primeiros três bits, é uma relação de equivalência no conjunto de todas as seqüências de bits de comprimento maior que ou igual a 3.

Passo 1

O enunciado define o conjunto
A = \{\text{todas as sequências de bits de comprimento }n\ge3\}ê
e a relação R\subseteq A\times A dada por
(x,y)\in R \quad\Longleftrightarrow\quad \text{os três primeiros bits de \(x\) são iguais aos três primeiros bits de \(y\).}êãê
O conteúdo é teoria de relações de equivalência e vamos usar as definições de reflexividade, simetria e transitividade.

Passo 2

(Propriedade reflexiva)
Seja x\in A. Escrevendo x=x_1x_2x_3\ldots x_n com n\ge3, claramente x_1=x_1, x_2=x_2 e x_3=x_3. Logo os três primeiros bits de x coincidem com os de x, isto é, (x,x)\in R. Portanto R é reflexiva.

Passo 3

(Propriedade simétrica)
Suponha (x,y)\in R. Então pelas regras de R temos
x_1 = y_1,\quad x_2 = y_2,\quad x_3 = y_3.
Mas igualdade é simétrica, logo
y_1 = x_1,\quad y_2 = x_2,\quad y_3 = x_3,
o que implica (y,x)\in R. Assim R é simétrica.

Passo 4

(Propriedade transitiva)
Suponha (x,y)\in R e (y,z)\in R. Então
x_i = y_i \quad\text{e}\quad y_i = z_i \quad\text{para }i=1,2,3.
Pelo caráter transitivo da igualdade segue
x_i = z_i \quad\text{para }i=1,2,3,
portanto (x,z)\in R. Assim R é transitiva.

Resposta

Como R é reflexiva, simétrica e transitiva, concluímos que R é uma relação de equivalência em A.

Exercícios de Livros Relacionados