Mostre que a relação
, que consiste em todos os pares
tal que
e
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
e a relação
dada por
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 . Escrevendo
com
, claramente
,
e
. Logo os três primeiros bits de
coincidem com os de
, isto é,
. Portanto
é reflexiva.
Seja
Passo 3
(Propriedade simétrica)
Suponha . Então pelas regras de
temos
Suponha
Mas igualdade é simétrica, logo
o que implica
. Assim
é simétrica.
Passo 4
(Propriedade transitiva)
Suponha e
. Então
Suponha
Pelo caráter transitivo da igualdade segue
portanto
. Assim
é transitiva.
Resposta
Como
é reflexiva, simétrica e transitiva, concluímos que
é uma relação de equivalência em
.