MAT01375 - MATEMÁTICA DISCRETA B Eduardo Brietzke Lista 6

Prévia do material em texto

MAT 01375 – Matemática Discreta B – 2019/2 – Lista 6
1. Considere a relação R = {(1, 3), (1, 4), (3, 2), (3, 3), (3, 4)} no conjunto A = {1, 2, 3, 4}.
a) Obtenha a matriz MR de R.
b) Encontre R−1. Determine a matriz MR−1 de R
−1.
c) Faça uma esboço do digrafo de R.
d) Determine R ◦R e a matriz que a representa.
e) Utilizando os itens anteriores, determine se R é transitiva.
f) Encontre R−1 ◦R e R ◦R−1.
2. Mostre que se R for uma relação de A em B e S uma relação de B em C, então
(S ◦R)−1 = R−1 ◦ S−1.
3. Considere em as seguintes relações em N : (x, y) ∈ R1 ←→ x ≥ y,
(x, y) ∈ R2 ←→ xy é um quadrado perfeito (x, y) ∈ R3 ←→ x+ y = 10
(x, y) ∈ R4 ←→ x+ 4y = 10.
Determine quais das relações acima são
a) reflexivas b) simétricas c) anti-simétricas d) transitivas.
4. Sejam R e S relações em um conjunto A. Suponha que A tenha no mı́nimo 3 elementos
decida se cada sentença é verdadeira ou falsa. Se a sentença for verdadeira, sustifique. Se
for falsa, apresente um contra-exemplo usando o conjunto A = {1, 2, 3}.
a) R e S simétricas −→ R ∩ S é simétrica.
b) R e S simétricas −→ R ∪ S é simétrica.
c) R e S reflexivas −→ R ∩ S é reflexiva.
d) R e S reflexivas −→ R ∪ S é reflexiva.
e) R e S transitivas −→ R ∪ S é transitiva.
f) R e S anti-simétricas −→ R ∪ S anti-simétrica.
g) R anti-simétrica −→ R−1 anti-simétrica.
h) R reflexiva −→ R ∩R−1 ̸= ∅.
h) R simétrica −→ R ∩R−1 ̸= ∅.
5. Sendo A = {1, 2, 3}, dê exemplo de relação R em A satisfazendo:
a) R é simétrica e anti-simétrica.
b) R não é simétrica nem anti-simétrica.
a) R é transitiva mas R ∪R−1 não é transitiva.
6. Sejam R e S relações em um conjunto A de quatro elementos representadas pelas matrizes
MR =

1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
 e MS =

0 1 0 1
1 0 1 0
1 0 1 0
0 1 0 1

Examinando as respectivas matrizes, determine
a) Quais das seguintes relações R, S, R◦S, S ◦R, R∩S, R∪S são reflexivas, simétricas
ou transitivas?
b) Quais das seguintes relações R, S, R ◦ S, S ◦ R, R ∩ S, R ∪ S são universais (igual
a A× A)?
2