lista4

Prévia do material em texto

Universidade Federal de Campina Grande
Centro de Engenharia Elétri
a e Informáti
a
Departamento de Sistemas e Computação
Lista de Exer
í
ios 4
Relações, Funções, Cardinalidade e Noções de
Complexidade de Algoritmos
1. Liste os pares ordenados na relação R de A =
{0, 1, 2, 3, 4} e B = {0, 1, 2, 3}, em que (a, b) ∈ R se e
somente se:
a) a = b
b) a+ b = 4
) a > b
d) a | b
e) mdc(a, b) = 1
f) mmc(a, b) = 2
2. Para 
ada uma das relações sobre o 
onjunto
{1, 2, 3, 4} veri�que se ela é re�exiva, simétri
a, an-
tisimétri
a, ou transitiva.
a) {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}
b) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
) {(2, 2), (4, 2)}
d) {(1, 2), (2, 3), (3, 4)}
e) {(1, 1), (2, 2), (3, 3), (4, 4)}
f) {(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)}
3. Determine se a relação R no 
onjunto de todas as
páginas Web é re�exiva, simétri
a, antisimétri
a,
e/ou transitiva, em que (a, b) ∈ R se e somente se:
a) Toda pessoa que visitou a página Web a também
visitou a página Web b.
b) Não há links em 
omum em ambas as páginas
Web a e b.
) Há pelo menos um link em 
omum na página
Web a e na página Web b.
d) Existe uma página Web que in
lui links para am-
bas as páginas Web a e b.
4. Considerando as seguintes relações, realize as oper-
ações indi
adas:
i) R1 = {(a, b) ∈ R
2 | a > b}, a relação "maior
que".
ii) R2 = {(a, b) ∈ R
2 | a ≥ b}, a relação "maior que
ou igual a".
iii) R3 = {(a, b) ∈ R
2 | a < b}, a relação "menor
que".
iv) R4 = {(a, b) ∈ R
2 | a ≤ b}, a relação "menor
que ou igual a".
v) R5 = {(a, b) ∈ R
2 | a = b}, a relação "igual a".
vi) R6 = {( b) ∈ R
2 | a 6= b}, a relação "diferente".
a) R2 ∪R4
b) R3 ∪R6
) R3 ∩R6
d) R4 ∩R6
e) R3 −R6
f) R6 −R3
g) R2 ⊕R6
h) R3 ⊕R5
5. Liste as triplas na relação {(a, b, c) | a, b, c são inteiros
om 0 < a < b < c < 5}.
6. As 3-tuplas na relação ternária representam os
seguintes atributos de um ban
o de dados de estu-
dantes: número identi�
ador do estudante, nome,
número de telefone. Qual ou quais desses atributos
poderia ser uma 
have primária? Por quê?
7. Represente 
ada uma dessas relações em {1, 2, 3} 
om
uma matriz (
om os elementos desse 
onjunto listados
em ordem 
res
ente).
a) {(1, 1), (1, 2), (1, 3)}
b) {(1, 2), (2, 1), (2, 2), (3, 3)}
) {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}
d) {(1, 3), (3, 1)}
8. Liste todos os pares nas relações em {1, 2, 3} 
orre-
spondendo às matrizes abaixo, nas quais as linhas e
olunas 
orrespondem aos inteiros listados em ordem
res
ente:
a) [
1 0 1
0 1 0
1 0 1
]
b) [
0 1 0
0 1 0
0 1 0
]
) [
1 1 1
1 0 1
1 1 1
]
9. Sejam R1 e R2 as relações no 
onjunto A represen-
tadas pelas matrizes:
MR1 =
[
0 1 0
1 1 1
1 0 0
]
e
MR2 =
[
0 1 0
0 1 1
1 1 1
]
Quais são as matrizes que representam:
a) R1 ∪R2
b) R1 ∩R2
) R1 ⊕R2
10. Seja R a relação sobre o 
onjunto 0, 1, 2, 3 
ontendo
os pares ordenados (0, 1), (1, 1), (1, 2), (2, 0), (2, 2)
e (3, 0). En
ontre:
a) O fe
ho re�exivo de R;
b) O fe
ho simétri
o de R.
1
a
b c
d
(a)
a
b
c
d
(b)
a
b
c
d
(
)
Figura 1: Figuras para o exer
í
io 11.
11. Para os grafos dirigidos abaixo, desenhe o grafo do
fe
ho re�exivo das relações mostradas em 
ada item.
12. Quais dessas relações sobre 0, 1, 2, 3 são relações
de equivalên
ia? Determine as propriedades de uma
relação de equivalên
ia que as outras não têm.
a) (0, 0), (1, 1), (2, 2), (3, 3)
b) (0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)
) (0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3)
d) (0, 0), (1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2),
(3, 3)
e) (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0)
13. Para as �guras abaixo, indique se a relação represen-
tada pelo grafo dirigido mostra uma relação de equiv-
alên
ia:
a
c d
b
(a)
a
d
b
c
(b)
a
b
d
c
(
)
Figura 2: Figuras para o exer
í
io 13.
14. Quais destas relações sobre 0, 1, 2, 3 são de ordem
par
ial? Determine as propriedades de uma relação
de ordem par
ial que as outras relações não possuem.
a) (0, 0), (1,1), (2, 2), (3, 3)
b) (0, 0), (1, 1), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)
) (0, 0), (1, 1), (1, 2), (2, 2), (3, 3)
d) (0, 0), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)
e) (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0),
(2, 2), (3, 3)
2
15. Determine se as relações representadas pelas matrizes
abaixo são de ordem par
ial:
a) [
1 0 1
1 1 0
0 0 1
]
b) [
1 0 0
0 1 0
1 0 1
]
) 

1 0 1 0
0 1 1 0
0 0 1 1
1 1 0 1


16. Nas �guras abaixo, determine se a relação represen-
tada no grafo dirigido mostra uma relação de ordem
par
ial.
a
b c
d
(a)
a
b
c
d
(b)
a
b c
d
(
)
Figura 3: Figuras para o exer
í
io 16.
17. Determine qual é o dual dos seguintes 
onjuntos par-
ialmente ordenados (POSET).
1. ({0, 1, 2},≤)
2. (Z,≥)
3. (P (Z),⊇)
4. (Z+, |)
18. Desenhe o digrama de Hasse para a relação "maior
que ou igual a"sobre o 
onjunto {0, 1, 2, 3, 4, 5}.
19. Desenhe o diagrama de Hasse para divisibilidade so-
bre o 
onjunto:
1. 1, 2, 3, 4, 5, 6, 7, 8
2. 1, 2, 3, 5, 7, 11, 13
3. 1, 2, 3, 6, 12, 24, 36, 48
4. 1, 2, 4, 8, 16, 32, 48
20. Determine os seguintes valores:
1. ⌊1.1⌋
2. ⌈1.1⌉
3. ⌊−0.1⌋
4. ⌈−0.1⌉
5. ⌈2.99⌉
6. ⌈−2.99⌉
21. Determine se 
ada uma das funções abaixo é "um-a-
um":
1. f(n) = n− 1
2. f(n) = n2 + 1
3. f(n) = n3
4. f(n) = ⌈n/2⌉
22. Determine se a função f : Z × Z → Z é sobrejetora
se:
1. f(m,n) = 2m− n
2. f(m,n) = m2 − n2
3. f(m,n) = m+ n+ 1
4. f(m,n) = |m| − |n|
23. Determine se 
ada uma das funções abaixo é bijetora
de R em R.
1. f(x) = 2x+ 1
2. f(x) = x2 + 1
3. f(x) = x3
4. f(x) = (x2 + 1)/(x2 + 2)
24. Determine f ◦ g e g ◦ f para f(x) = x2 + 1 e
g(x) = x+ 2, de R em R.
25. Seja f uma função de R em R de�nida por f(x) = x2.
Determine f−1({x|x > 4}).
26. Determine a inversa da função f(x) = x3 + 1.
27. Para 
ada lista de inteiros abaixo, determine uma fór-
mula simples ou regra para gerar os termos de uma
sequên
ia de inteiros que 
omeça 
om a lista dada.
Assumindo que sua fórmula ou regra está 
orreta, de-
termine os próximos três termos da sequên
ia.
1. 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, ...
2. 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, ...
3
3. 1, 0, 2, 0, 4, 0, 8, 0, 16, 0, ...
28. Determine se 
ada um dos 
onjuntos abaixo é �nito,
in�nito 
ontável ou in
ontável. Para aqueles que são
in�nitos 
ontáveis, exiba uma 
orrespondên
ia um-a-
um entre eles e o 
onjunto dos inteiros positivos.
1. Os inteiros negativos.
2. Os inteiros pares.
3. Os inteiros menores que 100.
4. Os números reais entre 0 e
1
2
.
5. Os inteiros múltiplos de 7.
29. Suponha que o Grande Hotel de Hilbert está 
omple-
tamente o
upado, mas o hotel fe
ha todos os quartos
de número par para manutenção. Mostre que todos
os hóspedes podem permane
er no hotel.
30. Dê um exemplo de dois 
onjuntos não 
ontáveis A e
B tais que A∩B é: a) Finito, b) in�nito 
ontável, 
)
in
ontável.
31. Para as funções a seguir, a) determine valores C e
k para determinar o rela
ionamento big − O tal que
|f(x)| ≤ C|g(x)| sempre que x > k, b) determine se a
função é Ω(x), 
) determine se a função é Θ(x)
1. f(x) = 10
2. f(x) = 3x+ 7
3. f(x) = x2 + x+ 1
4. f(x) = 5 log x
5. f(x) = ⌊x⌋
32. Determine se 
ada uma das funções abaixo é O(x2):
1. f(x) = 17x+ 11
2. f(x) = x2 + 100
3. f(x) = x log x
4. f(x) = x
4
2
5. f(x) = 2x6. f(x) = ⌊x⌋.⌈x⌉
4