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 que coincidem nos seus primeiro e terceiro 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 a relação R sobre o conjunto \displaystyle A = \{\text{sequências de bits }x\mid |x|\ge3\}ê
por
(x,y)\in R \quad\Longleftrightarrow\quad x_{1}=y_{1}\\ \text{e}\\ x_{3}=y_{3}.
Queremos mostrar que R é uma relação de equivalência, ou seja, verificar reflexividade, simetria e transitividade.

Passo 2

(Reflexividade)
Tomemos uma sequência arbitrária x\in A. Claro que
x_{1}=x_{1} \quad\text{e}\quad x_{3}=x_{3},
logo (x,x)\in R. Assim, R é reflexiva.

Passo 3

(Simetria)
Suponha (x,y)\in R. Então
x_{1}=y_{1} \quad\text{e}\quad x_{3}=y_{3}.
Mas essas igualdades implicam também
y_{1}=x_{1} \quad\text{e}\quad y_{3}=x_{3},
portanto (y,x)\in R. Assim, R é simétrica.

Passo 4

(Transitividade)
Suponha (x,y)\in R e (y,z)\in R. Então
x_{1}=y_{1},\quad x_{3}=y_{3} \quad\text{e}\quad y_{1}=z_{1},\quad y_{3}=z_{3}.
Pela transitividade da igualdade em \{0,1\} segue
x_{1}=z_{1} \quad\text{e}\quad x_{3}=z_{3},
isto é, (x,z)\in R. Logo, 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