Relações em Matemática Discreta

Prévia do material em texto

Lista de Matemática Discreta
Relações
1. Assim como as funções, as relações podem ser compostas. Dadas as relações R ⊆ A × B e S ⊆ B × C
definimos
(S ◦ R) ⊂ A × C
pela regra (x, z) ∈ (S ◦ R) se, e somente se, existe y ∈ B tal que (x, y) ∈ R e (y, z) ∈ S. Em notação infixa
x (S ◦ R) z ⇔ ∃y(x R y ∧ y S z)
Não é difícil ver que a composição ordinária de funções é um caso especial de composição de relação.
Considere as seguintes relações sobre {0, 1, 2, 3, 4}
R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)}
S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)}
Determine S ◦ R, R ◦ S, S ◦ S e R ◦ R.
2. As relações também têm inversa
x R−1 y ⇔ y R x.
Ao contrário das funções, toda relação tem uma inversa.
Determine a relação inversa de R = {(1, 2), (1, 3), (2, 3)} sobre A = {1, 2, 3}.
Determine também R−1 ◦ R e R ◦ R−1.
3. Qual é inversa da relação < sobre N?
4. Seja Z o conjunto dos números inteiros. Para cada i ∈ {0, 1, 2} denote por Ri o subconjunto dos números
inteiros que deixam resto i quando divididos por 3. Prove que {R0, R1, R2} é uma partição de Z.
5. Seja q um número inteiro e positivo. Para cada i ∈ {0, 1, . . . , q − 1} denote por Ri o subconjunto dos
números inteiros que deixam resto i quando divididos por q. Prove que {R0, R1, . . . , Rq−1} é uma partição
de Z.
6. Dê um exemplo de uma relação no conjunto {1, 2, 3, 4} que seja
(a) reflexiva, simétrica e não transitiva;
(b) não reflexiva, simétrica e transitiva;
(c) reflexiva, antissimétrica e não transitiva.
7. Explique o que está errado na seguinte demonstração sobre uma relação binária R sobre A:
Teorema. Se R é uma relação simétrica e transitiva então R é uma relação reflexiva.
Demonstração. Seja x um elemento qualquer de A. Para todo y, se xR y então y R x, pois a
relação é simétrica. Se xR y e y R x, então xR x pela transitividade. Portanto, R é reflexiva.
8. Considere a relação Z ⊂ N ×N definida por
(a, b)Z(n, m) se, e só se a + m = b + n (1)
Prove que Z é uma relação de equivalência, isto é, uma relação reflexiva, simétrica e transitiva.
9. Defina classe de equivalência com respeito a uma relação de equivalência R em um conjunto não-vazio
A.
1
10. Seja m > 1 inteiro. Dois inteiros a e b são congruentes módulo m se m
∣∣∣∣b − a. Mostre que congruência
módulo m é uma relação de equivalência. Determine as classes de equivalência.
11. Defina em Z a relação a ∼ b se e só se b = a ou b = −a. Determine se a relação é de equivalência e, caso
seja, determine as classes de equivalência.
12. Mostre que a relação | nos inteiros não é de equivalência.
13. Sejam (A,E) e (B,�) duas ordens totais. Definimos em A × B a seguinte relação binária
(a, b) 2 (c, d) (2)
se a / c (i.e., a E c e a , c) ou a = c e b � b. Prove que (A × B,2) é uma ordem total. Essa ordem é
conhecida como lexicográfica.
14. Considere o conjunto N ×N com a ordem lexicográfica 4:
(x, y) 4 (a, b) se
x < a ou
x = a e y ≤ b
Ordene os seguintes elementos de acordo com a ordem lexicográfica:
(1, 2), (2, 1), (3, 1), (1, 1), (2, 2), (3, 3), (1, 4), (3, 5), (2, 4), (4, 4), (4, 1).
15. Determine os elementos maximais e minimais de ({2, 4, 5, 10, 12, 20, 25}, |).
16. Prove que se numa ordem parcial (A,�) há maior elemento então ele é único.
17. Numa ordem parcial (A,�) dizemos que C ⊆ A é uma cadeia se os elementos de C são comparáveis entre
si. Dizemos que C é uma anti-cadeia se os elementos de C são incomparáveis entre si. Determine as
cadeias e as anti-cadeias de (2{1,2,3},⊆).
18. Prove que numa ordem parcial finita e não vazia há elementos maximal e minimal.
19. O diagrama de Hasse de uma ordem parcial (A,�) é uma representação gráfica dessa ordem. Nela os
elementos do conjunto são ligados por arestas e a está ligado com b se a � b e não existe c tal que
a � c � b, ainda se a � b então b aparece (verticalmente) acima de a no diagrama. O seguinte diagrama
representa (2{1,2,3},⊆)
{1, 2, 3}
{2, 3} {1, 3} {1, 2}
{3} {2} {1}
∅
Desenhe o diagrama de Hasse de ({1, 2, 4, 5, 12, 20}, | )
2
20. Uma linearização (ou ordenação topológica) de uma ordem parcial (A,�) é uma sequência a1, a2, . . . , an
com todos os elemento de A que é compatível com �, isto é, se i < j então ai � aj , ou ai e aj são incompa-
ráveis. Uma linearização de (2{1,2,3},⊆) é
∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} (3)
Escreva outras duas linearizações possíveis para (2{1,2,3},⊆).
21. Seja S um conjunto de tarefas e � uma relação de ordem, de modo que s � t significa que s deve ser
realizada antes de t. Uma linearização corresponde a uma sequência de realização de tarefas que é
compatível com a ordem.
Encontre uma ordem de tarefas para um projeto de software cuja ordem é representada por
22. Considere N ×N com a boa-ordem do exercício 14. Defina a : N ×N→ N recursivamente
a(0, 0) = 0
a(m, n) =
a(m − 1, n) + 1 se n = 0 e m > 0
a(m, n − 1) + n se n > 0
Prove por indução em (m, n) que a(m, n) = m + n(n + 1)/2.
23. Defina em Z
− a ordem x 4 y se, e só se, |y| ≤ |x|. Defina f : Z− → Z
− recursivamentef (−1) = −1
f (n) = f (n + 1) + n para n < −1
Prove que f (x) = −|n|(|n| + 1)/2.
3