Exercícios de Matemática Discreta

Prévia do material em texto

MAT 01375 – Matema´tica Discreta B 2017/2
Lista de Exerc´ıcios 5
1. Verifique se as relac¸o˜es definidas abaixo sa˜o relac¸o˜es de ordem parcial.
Justifique suas respostas.
(i) 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

 .
(ii) 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

 .
(iii) A relac¸a˜o em {1, 2, 3} representada pela matriz


1 1 1
0 1 0
1 0 1

 .
2. Fac¸a o grafo, diagrama de Hasse, das relac¸o˜es do exerc´ıcio anterior.
3. Verifique se as relac¸o˜es dadas abaixo sa˜o relac¸o˜es de ordem parcial.
Justifique suas respostas.
(i) 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)].
(ii) Seja B = P({1, 2, 3}). Para dois conjuntos C,D ∈ P({1, 2, 3}), definimos C RD
se C = ∅ ou se C,D 6= ∅ e max{α : α ∈ C} ≤ max{α : α ∈ D}.
4. Dentre os pares de elementos dados abaixo, quais sa˜o compara´veis no conjunto
parcialmente ordenado (N, | ) com | a relac¸a˜o de divisibilidade? Justifique sua
resposta.
(i) 5 e 15 (ii) 6 e 9 (iii) 8 e 16 (iv) 7 e 17 (v) 10 e 15.
5. Determine dois elementos na˜o compara´veis nos conjuntos parcialmente ordenados
dados abaixo:
(i) (P({0, 1, 2}),⊆)
(ii) ({1, 2, 4, 6, 8}, | ).
6. Seja R ⊆ Z× Z a relac¸a˜o definida por:
(a, b) ∈ R←→ (∃ t ∈ N∗) b = at.
(i) Mostre que R e´ uma relac¸a˜o de ordem parcial em Z.
(ii) (Z, R) e´ um conjunto totalmente ordenado?
7. Seja S uma relac¸a˜o em R× R = R2 definida por:
((a, b), (c, d)) ∈ S ←→ a ≤ c ou b ≤ d.
(i) S e´ funcional? S e´ sobrejetora?
(ii) S e´ uma relac¸a˜o de ordem parcial ?
8. Mostre que, se (A1,�1) e (A2,�2) sa˜o POSETs, enta˜o (A1 × A2,�prod) e´ um POSET,
em que a relac¸a˜o “�prod ” e´ definida por:
(a, b) �prod (c, d)⇐⇒ a �1 c ∧ b �2 d
Caso A1 e A2 sejam totalmente ordenados, o conjunto A1 × A2 sera´ tambe´m total-
mente ordenado? Justifique sua resposta.
9. Determine todos os elementos (a, b) ∈ N× N, para os quais temos:
(i) (a, b) �prod (1, 8) ; com �1=�2=≤
(ii) (a, b) �prod (1, 8) ; com �1=≤ e �2 a relac¸a˜o de divisibilidade.
10. Seja (A,R) um POSET. Mostre que
(
A,R−1
)
e´ um POSET.
11. Seja P o conjunto das proposic¸o˜es. Mostre que “ =⇒ ” define uma relac¸a˜o de ordem
parcial em P , ou seja, mostre que a relac¸a˜o R definida por:
(∀ p , q ∈ P) (p, q) ∈ R se e somente se p =⇒ q
e´ uma relac¸a˜o de ordem parcial. Use que duas proposic¸o˜es p e q sa˜o “iguais” se elas
sa˜o logicamente equivalentes, ou seja, p⇐⇒ q.
12. Considere f : N −→ Z, definida por f(2n) = n e f(2n− 1) = −n, para todo
n ∈ N.
(i) Mostre que f e´ uma bijec¸a˜o
(ii) Dados z1, z2 ∈ Z, definimos �Z por
z1 �Z z2 ⇐⇒ f
−1(z1) �Z f
−1(z2) .
Verifique, justificando suas respostas, se:
(a)
(
Z, �Z
)
e´ um POSET (conjunto parcialmente ordenado).
(b)
(
Z, �Z
)
e´ TO (conjunto totalmente ordenado).
(c)
(
Z, �Z
)
e´ BO (conjunto bem ordenado).