O conjunto
possui
elementos.
a) Determine o número de relações que podem ser construídas em
;
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.
a) Determine o número de relações que podem ser construídas em
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
com
elementos.
Conteúdo: teoria de relações como subconjuntos de .
Precisaremos do fato de que e de políticas de escolha de pares sujeitos às propriedades (reflexiva, simétrica, antissimétrica).
Conteúdo: teoria de relações como subconjuntos de
Precisaremos do fato de que
Passo 2
Para qualquer relação em
não há restrição: é um subconjunto de
de tamanho
.
Logo, o número de relações possíveis é o número de subconjuntos de , isto é,
Logo, o número de relações possíveis é o número de subconjuntos de
Passo 3
Para ser reflexiva, a relação deve conter todos os
pares
. Os demais
pares podem ou não entrar livremente.
Assim, o total de relações reflexivas é
Assim, o total de relações reflexivas é
Passo 4
Para ser simétrica, sempre que
for escolhido (
), o par
também deve estar.
- Há
“pares não diagonais” com , cada um gerando a opção “incluir ambos ou nenhum” ( escolhas). - Há
pares diagonais , cada um pode entrar ou não ( escolhas independentes).
Logo, o total de relações simétricas é
Passo 5
Para ser antissimétrica, não podemos ter simultaneamente
e
quando
.
- Em cada um dos
pares não diagonais temos escolhas: “nenhum”, “só ” ou “só ”. - Em cada um dos
pares diagonais podemos escolher incluí-lo ou não ( escolhas).
Portanto, o total de relações antissimétricas é
Passo 6
Para ser reflexiva e simétrica, devemos:
- Incluir todos os
pares diagonais (reflexiva). - Nas
classes de pares não diagonais, manter a simetria: para cada classe “incluir ambos ou nenhum” ( escolhas).
Logo, o total é
Passo 7
Para ser reflexiva e antissimétrica, devemos incluir todos os
loops e, nos
pares não diagonais, respeitar a antissimetria (
escolhas cada).
Assim, o total é
Assim, o total é
Passo 8
Para ser simétrica e antissimétrica, não podemos ter nenhum par distinto
(pois a simetria forçaria os dois
e
, violando a antissimetria). Logo todos os pares não diagonais ficam de fora.
Resta apenas decidir, para cada um dos pares diagonais, se entra ou não.
O total é
Resta apenas decidir, para cada um dos
O total é
Passo 9
Para ser reflexiva, simétrica e antissimétrica simultaneamente, precisamos incluir todos os
loops (reflexiva) e não poder ter pares distintos (simétric
ntissimétrica). Não há nenhuma escolha livre: é a relação que contém exatamente todos os
.
Logo, só há
Logo, só há
relação desse tipo.
Resposta
a)
b)
c)
d)
e)
f)
g)
h)
b)
c)
d)
e)
f)
g)
h)