O conjunto A possui n elementos.
a) Determine o número de relações que podem ser construídas em A;
b) Idem, relações reflexivas;
c) Idem, relações simétricas;
d) Idem, relações anti-simétricas;
e) Idem, relações reflexivas e simétricas;
f) Idem, relações reflexivas e anti-simétrica;
g) Idem, relações simétricas e anti-simétricas;
h) Idem, relações reflexivas, simétricas e anti-simétricas.

Passo 1

O enunciado pede para contar tipos de relações em um conjunto A com n elementos.
Conteúdo: teoria de relações como subconjuntos de Atimes A.
Precisaremos do fato de que lvert Atimes Arvert = n^2 e de políticas de escolha de pares sujeitos às propriedades (reflexiva, simétrica, antissimétrica).

Passo 2

Para qualquer relação em A não há restrição: é um subconjunto de Atimes A de tamanho n^2.
Logo, o número de relações possíveis é o número de subconjuntos de Atimes A, isto é,
2^n^2

Passo 3

Para ser reflexiva, a relação deve conter todos os n pares (a,a). Os demais n^2-n pares podem ou não entrar livremente.
Assim, o total de relações reflexivas é
2^,n^2 - n

Passo 4

Para ser simétrica, sempre que (x,y) for escolhido ( xneq y), o par (y,x) também deve estar.
  • tfracn(n-1)2 “pares não diagonais” x,y com xneq y, cada um gerando a opção “incluir ambos ou nenhum” ( 2 escolhas).
  • n pares diagonais (a,a), cada um pode entrar ou não ( 2 escolhas independentes).
    Logo, o total de relações simétricas é
2^n(n-1)2times 2^n ;=; 2^n(n+1)2

Passo 5

Para ser antissimétrica, não podemos ter simultaneamente (x,y) e (y,x) quando xneq y.
  • Em cada um dos tfracn(n-1)2 pares não diagonais x,y temos 3 escolhas: “nenhum”, “só (x,y)” ou “só (y,x)”.
  • Em cada um dos n pares diagonais (a,a) podemos escolher incluí-lo ou não ( 2 escolhas).
    Portanto, o total de relações antissimétricas é
3^n(n-1)2times 2^n

Passo 6

Para ser reflexiva e simétrica, devemos:
  • Incluir todos os n pares diagonais (reflexiva).
  • Nas tfracn(n-1)2 classes de pares não diagonais, manter a simetria: para cada classe “incluir ambos ou nenhum” ( 2 escolhas).
    Logo, o total é
2^n(n-1)2

Passo 7

Para ser reflexiva e antissimétrica, devemos incluir todos os n loops e, nos tfracn(n-1)2 pares não diagonais, respeitar a antissimetria ( 3 escolhas cada).
Assim, o total é
3^n(n-1)2

Passo 8

Para ser simétrica e antissimétrica, não podemos ter nenhum par distinto xneq y (pois a simetria forçaria os dois (x,y) e (y,x), violando a antissimetria). Logo todos os pares não diagonais ficam de fora.
Resta apenas decidir, para cada um dos n pares diagonais, se entra ou não.
O total é
2^n

Passo 9

Para ser reflexiva, simétrica e antissimétrica simultaneamente, precisamos incluir todos os n loops (reflexiva) e não poder ter pares distintos (simétric a+antissimétrica). Não há nenhuma escolha livre: é a relação que contém exatamente todos os (a,a).
Logo, só há
1
relação desse tipo.

Resposta

a) 2^n^2
b) 2^,n^2 - n
c) 2^n(n+1)2
d) 3^n(n-1)2times 2^n
e) 2^n(n-1)2
f) 3^n(n-1)2
g) 2^n
h) 1

Exercícios de Livros Relacionados