Lista10 Operacoes Relacoes

Prévia do material em texto

Lista 10 de Matemática Discreta I
Operações com Relações
1. Represente cada uma das relações em {1, 2, 3, 4} no formato de uma matriz.
(a) R = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}.
(b) R = {(1, 1), (1, 4), (2, 2), (3, 3), (4, 1)}.
(c) R = {(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)}.
(d) R = {(2, 4), (3, 1), (3, 2), (3, 4)}.
2. Como podemos usar a representação matricial de uma relação para mostrar que a
relação é irreflexiva?
3. Como podemos usar a representação matricial de uma relação para mostrar que a
relação é assimétrica?
4. Verifique se as relações dadas abaixo na forma matricial são reflexivas, irreflexivas,
simétricas, assimétricas, anti-simétricas e/ou transitiva.
[a]
1 0 10 1 01 0 1
 , [b]
0 1 00 1 00 1 0
 , [c]
1 1 11 0 11 1 1
 , [d]

1 1 0 1
1 0 1 0
0 1 1 1
1 0 1 1
 , [e]

1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
 ,
5. Considere a representação matricial da relação R dada no conjunto {1, 2, , . . . , 100}.
Quantas entradas não nulas existem na décima linha da matriz?
(a) R = {(a, b) : a < b}.
(b) R = {(a, b) : a = b + 1}.
(c) R = {(a, b) : ab = 1}.
(d) R = {(a, b) : a , b}.
(e) R = {(a, b) : a = 1}.
6. Seja R a relação representada pela matriz
0 1 11 1 01 0 1
 . Ache R−1, R e R2
1
2
7. SejamR1 eR2 relações no conjunto A representadas pelas matrizesMR1 =
0 1 01 1 11 0 0
 .
e MR2 =
0 1 00 1 11 1 1
 .. Ache as matrizes que representam:
(a) R1 ∪ R2.
(b) R1 ∩ R2.
(c) R1 ◦ R2.
(d) R2 ◦ R1.
8. Seja a relação R representada pela matriz MR =
0 1 00 0 11 1 0
 .. Ache as matrizes que
representam R2, R3 e R4.
9. Seja R uma relação no conjunto A com n elementos. Se existem k entradas não
nulas na matriz que representa a relação, MR, quantas entradas não nulas existem
em MR−1? e na MR?
10. SejaRa relação no conjunto {0, 1, 2, 3} contendo os pares (0, 1), (1, 1), (1, 2), (2, 0), (2, 2)
e (3, 0). Ache o fecho reflexivo e o fecho simétrico da relação.
11. Seja R = {(a, b) ∈ Z ×Z : a , b}. Qual o fecho reflexivo de R?
12. Seja R{(a, b) ∈ Z ×Z : a divide b}. Qual o fecho simétrico de R?
13. SejaA = {1, 2, 3} e seja a relação R em A contendo os pares (1, 1), (1, 2), (1, 3), (3, 1), (2, 3).
Ache os fechos reflexivo, simétrico e transitivo de R.
14. Seja A = {0, 1, 2, 4, 6}. Verifique se as relações binárias em A são reflexivas, simétri-
cas, anti-simétricas e/ou transitivas. A seguir, ache os fechos reflexivo, simétrico e
transitivo.
(a) R = {(0, 0), (1, 1), (2, 2), (4, 4), (6, 6), (0, 1), (1, 2), (2, 4), (4, 6)}.
(b) R = {(0, 1), (1, 0), (2, 4), (4, 2), (4, 6), (6, 4)}.
(c) R = {(0, 0), (1, 1), (2, 2), (4, 4), (6, 6), (4, 6), (6, 4)}.