L4D162 MAT01375 UFRGS DISCRETA B

Prévia do material em texto

MAT 01375 – Matema´tica Discreta B 2016/2
Lista de Exerc´ıcios 4
1. Seja A = {a, b, c}. Determine a representac¸a˜o matricial das seguintes relac¸o˜es em
A× A.
a) S1 = {(a, a), (a, b), (a, c)}
b) S2 = {(a, b), (b, a), (b, b), (c, c)}
c) S3 = {(a, a), (a, b), (a, c), (b, b), (b, c), (c, c)}
d) S4 = {(a, c), (c, a)}
Quais das relac¸o˜es acima sa˜o reflexivas, irreflexivas, sime´tricas, antissime´trica e/ou
transitivas?
2. Classifique as relac¸o˜es abaixo, dadas por sua representac¸a˜o matricial, quanto a re-
flexividade, simetria e transitividade. Justifique sua resposta.
T =


1 1 1
0 1 1
1 1 1

 , M =


1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1

 , e N =


1 1 1 0
1 1 1 0
1 1 1 0
0 0 0 1

 .
3. Seja A = {a, e, i, o, u}. Apresente um exemplo de uma relac¸a˜o em A que e´:
a) injetora e reflexiva
b) sobrejetora e sime´trica
c) anti-sime´trica e transitiva
d) injetora e na˜o total
e) funcional e sobrejetora
f) reflexiva e anti-sime´trica
g) na˜o sime´trica e na˜o anti-sime´trica
h) transitiva e sime´trica e na˜o reflexiva
4. Seja A um conjunto e R ⊆ A× A. Prove ou deˆ um contra-exemplo:
a) Se R e´ sime´trica e transitiva, enta˜o R e´ reflexiva.
b) Se R e´ reflexiva, enta˜o R e´ total.
c) Se R e´ reflexiva, enta˜o R e´ sobrejetora.
d) Se R e´ funcional, enta˜o R na˜o e´ transitiva.
e) Se R e´ sime´trica, enta˜o a relac¸a˜o R−1 coincide com R.
5. Fac¸a o grafo das relac¸o˜es S1, S2, S3, S4, T,M,N , dos exerc´ıcios 1 e 2 acima.
6. Verifique quais das relac¸o˜es S1, S2, S3, T,M,N sa˜o de equivaleˆncia e quais sa˜o de
ordem. Justifique sua resposta.
7. Seja R a relac¸a˜o de equivaleˆncia dada pela congrueˆncias mo´dulo n, ou seja, dizemos
que (a, b) ∈ R ⇐⇒ a e b teˆm o mesmo resto na divisa˜o por n. Em cada caso abaixo,
descreva a classe de equivaleˆncia [ 4 ]n, com
a) n = 3.
b) n = 5.
c) n = 6.
8. Seja R a relac¸a˜o em N× N definida por:
(
(a, b), (c, d)
)
∈ R⇐⇒ a+ d = b+ c.
a) Mostre que R e´ uma relac¸a˜o de equivaleˆncia.
b) Determine as classes de equivaleˆncia de [(1, 1)]R, [(2, 1)]R e [(3, 2)]R.
9. Seja S uma relac¸a˜o em R× R = R2 definida por:
(
(a, b), (c, d)
)
∈ S ⇐⇒ a = c.
a) S e´ funcional? S e´ sobrejetora?
b) Mostre que S e´ uma relac¸a˜o de equivaleˆncia em R2.
c) Descreva [(2, 3)]S
10. Seja S uma relac¸a˜o em R× R = R2 definida por:
(
(a, b), (c, d)
)
∈ S ⇐⇒ a+ 2b = c+ 2d.
a) Mostre que S e´ uma relac¸a˜o de equivaleˆncia.
b) Determine as classes de equivaleˆncia de [(1, 1)]S e [(2, 3)]S.
c) S e´ total? S e´ injetora? Justifique.
11. Seja R uma relac¸a˜o sobre Z dada por
xRy ⇐⇒ 4 | (x+ 3y).
a) Mostre que a relac¸a˜o R e´ uma relac¸a˜o de equivaleˆncia;
b) Descreva a classe de equivaleˆncia [0]R.
c) Descreva a classe de equivaleˆncia [3]R.
12. Verifique se as relac¸o˜es definidas abaixo sa˜o relac¸o˜es de ordem parcial.
Justifique suas respostas.
(a) A relac¸a˜o em {a, b, c, d} representada pela matriz


1 1 1 1
0 1 0 1
0 0 1 0
0 0 0 1

 .
(b) A relac¸a˜o em {a, b, c, d} representada pela matriz


1 1 1 0
0 1 0 1
0 0 1 0
0 0 0 1

 .
(c) A relac¸a˜o em {1, 2, 3} representada pela matriz


1 1 1
0 1 0
1 0 1

 .
13. Fac¸a o grafo das relac¸o˜es do exerc´ıcio anterior.
14. Verifique se as relac¸o˜es dadas abaixo sa˜o relac¸o˜es de ordem parcial.
Justifique suas respostas.
(a) Seja S(R) o conjunto de todas as func¸o˜es f : [0, 1] → [0, 1]. A relac¸a˜o R ⊆
S(R)× S(R) e´ definida por fRg ⇐⇒ (∀x ∈ [0, 1])[f(x) ≤ g(x)].
(b) Seja B = P({1, 2, 3}). Para dois conjuntos C,D ∈ P({1, 2, 3}), definimos a
relac¸a˜o R por: C RD se C = ∅ ou se C,D 6= ∅ e max{i : i ∈ C} ≤ max{i : i ∈
D}.
15. Quais dos pares de elementos dados abaixo sa˜o compara´veis no conjunto parcial-
mente ordenado (N∗, | ) com | a relac¸a˜o de divisibilidade? Justifique.
(a) 5 e 15 (b) 6 e 9 (c) 8 e 16 (d) 7 e 17 (e) 10 e 15.
16. Determine dois elementos na˜o compara´veis nos conjuntos parcialmente ordenados
abaixo.
(a) (P({0, 1, 2}),⊆)
(b) ({1, 2, 4, 6, 8}, | ).
17. Seja R ⊆ Z× Z a relac¸a˜o definida por:
(a, b) ∈ R⇐⇒ (∃ t ∈ N∗) b = at.
(a) Mostre que R e´ uma relac¸a˜o de ordem parcial em Z.
(b) (Z, R) e´ um conjunto totalmente ordenado?
18. Seja S uma relac¸a˜o em R× R = R2 definida por:
((a, b), (c, d)) ∈ S ⇐⇒ a ≤ c ou b ≤ d.
(a) S e´ funcional? S e´ sobrejetora?
(b) S e´ uma relac¸a˜o de ordem parcial ?
19. Seja (A,R) um POSET. Mostre que
(
A,R−1
)
e´ um POSET.