Seja E um conjunto finito com n elementos.

Quantas são as relações binárias sobre E?

Quantas dessas relações são reflexivas:

Sugestão: use o fato de que uma relação R sobre E é reflexiva se, e somente se, R = Δ E ⋃ R ' , em que Δ E = x , x x ∈ E e R’ é um subconjunto de E × E - Δ E .

Quantas dessas relações são simétricas?

Sugestão: use o fato de que uma relação R sobre E = { a 1 ,   a 2 ,   a 3 , … ,   a n } é simétrica se, e somente se, R = S ⋃ S - 1 , em que S é um subconjunto de E × E constituido por pares da forma ( a i , a j ) , com i ≥ j .

Passo 1

Fala minha galera, esses exercícios complementares são pedrada forte, bora com muita calma que vai dar tudo certo!

E × E possui n 2 relações binárias, então por definição, o número de relações binária em E = 2 n 2 .

Passo 2

Vamos usar a sugestão, temos que uma relação só é reflexiva quando seus pares são iguais, isto é, se temos um Δ E = x , x x ∈ E . Para que tenhamos uma relação reflexiva R, R deve ser Δ E ⋃ R ' , com R’ sendo as relações binárias de E menos nosso delta que carrega as reflexivas. Dessa forma temos 2 n 2 - n relações reflexivas, pois existem n números no conjunto E.

Passo 3

Para encontrarmos o número para relação simétrica, devemos notar que o número de relações simétricas é par, temos 2 escolhas de par e os elementos definidos com a relação simétrica são os que sobraram do n 2 - n , então temos:

2 n + n 2 - n 2 = n 2 + n 2

Dessa forma, temos que o número de relações reflexivas são 2 n 2 + n 2

Resposta

2 n 2   relações binárias, 2 n 2 - n reflexivas e 2 n 2 + n 2 relações simétricas.