Exercícios 03 - Matemática Discreta

Prévia do material em texto

Cursos de Tecnologia da Informação - TI 
 
Matemática Discreta 
 Campus Nova AméricaCampus Nova AméricaCampus Nova AméricaCampus Nova América Prof. Aureo Ruffier 
 
Página 1 de 4 
 
 
Exercícios de Relações 
 
 
1. Para cada uma das relações binárias ρ, a seguir, definidas em N, decida quais dos 
pares ordenados dados pertence a ρ. 
a) x ρ y ↔ x + y < 7; (1, 3), (3, 3), (4, 4) 
b) x ρ y ↔ x= y +2; (0, 2), (4, 2), (6, 3), (5, 3) 
c) x ρ y ↔ 2x + 3y = 10; (5, 0), (2, 2), (3, 1), (1, 3) 
d) x ρ y ↔ y é um quadrado perfeito; (1, 1), (4, 2), (3, 9), (25, 5) 
 
2. Para cada uma das relações binárias a seguir em R, desenhe uma figura para 
mostrar a região do plano que a descreve. 
a) x ρ y ↔ y ≤ 2 
b) x ρ y ↔ x = y – 1 
c) x ρ y ↔ x² + y² ≤ 25 
d) x ρ y ↔ x ≥ y 
 
3. Diga se cada uma das relações em N a seguir é um para um, um para muitos, 
muitos para um ou muitos para muitos. 
a) ρ = {(1, 2), (1, 4), (1, 6), (2, 3), (4, 3)} 
b) ρ = {(9, 7), (6, 5), (3, 6), (8, 5)} 
c) ρ = {(12, 5), (8, 4), (6, 3), (7, 12)} 
d) ρ = {(2, 7), (8, 4), (2, 5), (7, 6), (10, 1)} 
 
4. Sejam ρ e σ relações binárias em N definidas por x ρ y ↔ “x divide y”, x σ y ↔ 
5x ≤ y. Decida quais dos pares ordenados dados satisfazem as relações 
correspondentes: 
a) ρ U σ; (2, 6), (3, 17), (2, 1), (0, 0) 
b) ρ ∩ σ; (3, 6), (1, 2), (2, 12) 
c) ρ′; (1, 5), (2, 8), (3, 15) 
d) σ′; (1, 1), (2, 10), (4, 8) 
 
5. Teste se as relações binárias em S dadas a seguir são reflexivas, simétricas, anti-
simétricas ou transitivas. 
a) S = Q x ρ y ↔ │x│ ≤ │y│ 
b) S = N x ρ y ↔ x – y é um múltiplo inteiro de 3 
c) S = Z x ρ y ↔ x vezes y é par 
 
 
 
 
 
 
Cursos de Tecnologia da Informação - TI 
 
Matemática Discreta 
 Campus Nova AméricaCampus Nova AméricaCampus Nova AméricaCampus Nova América Prof. Aureo Ruffier 
 
Página 2 de 4 
 
 
6. Para cada uma das relações a seguir, descreva em palavras qual deveria ser seu 
fecho transitivo. 
a) S = conjunto de prédios em uma cidade, x ρ y ↔ x é um ano mais velho do que 
y. 
b) S = conjunto de todos os homens da Bulgária, x ρ y ↔ x é o pai de y. 
c) S = conjunto de todas as cidades nos Estados Unidos, x ρ y ↔ você pode 
dirigir de x para y em um dia. 
 
7. Desenhe o diagrama de Hasse para as seguintes ordens parciais: 
a) S = {a, b, c} ρ = {(a, a), (b, b), (c, c), (a, b), (b, c), (a, c)} 
b) S = {a, b, c, d} ρ = {(a, a), (b, b), (c, c), (d, d), (a, b), (a, c)} 
c) S = {Ø, {a}, {a, b}, {c}, {a, c}, {b}} A ρ B ↔ A ⊆ B 
 
8. Desenhe o diagrama de Hasse para cada um dos dois conjuntos parcialmente 
ordenados a seguir. 
a) S = {1, 2, 3, 5, 6, 10, 15, 30} x ρ y ↔ x divide y 
b) S = P({1, 2, 3}) A ρ B ↔ A ⊆ B 
O que você pode dizer sobre a estrutura desses dois diagramas? 
 
9. Para cada um dos diagramas de Hasse nas figuras abaixo, liste os pares ordenados 
que pertencem à relação de ordem correspondente. 
 
a) b) c) 
 
 
10. Para a relação de equivalência ρ = {(a, a), (b, b), (c, c), (a, c), (c, a)}, qual é o 
conjunto [a]? Esse conjunto tem outros nomes? 
 
11. Para a relação de equivalência ρ = {(1, 1), (2, 2), (1, 2), (2, 1), (1, 3), (3, 1), (3, 2), 
(2, 3), (3, 3), (4, 4), (5, 5), (4, 5), (5, 4)}, qual é o conjunto [3]? E o conjunto [4]? 
 
12. Seja S = N X N e seja ρ uma relação binária em S definida por (x, y) ρ (z, w) ↔ 
y = w. Mostre que ρ é uma relação de equivalência em S e descreva as classes de 
equivalência associadas. 
 
 
 5 
 
 
3 4 
 
 
 
1 2 
 d e f 
 
 
 
 
 a b c 
 5 
 
 
 4 
 
 
2 3 
 
 
 1 
 
Cursos de Tecnologia da Informação - TI 
 
Matemática Discreta 
 Campus Nova AméricaCampus Nova AméricaCampus Nova AméricaCampus Nova América Prof. Aureo Ruffier 
 
Página 3 de 4 
 
Respostas dos Exercícios 
 
 
1. a) (1, 3), (3, 3) 
b) (4, 2), (5, 3) 
c) (5, 0), (2, 2) 
d) (1, 1), (3, 9) 
 
2. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3. a) Muitos para muitos 
b) Muitos para um 
c) Um para um 
d) Um para muitos 
 
4. a) (2, 6), (3, 17), (0, 0) 
b) (2, 12) 
c) Nenhum 
d) (1, 1), (4, 8) 
 
5. a) Reflexiva, transitiva 
b) Reflexiva, simétrica, transitiva 
c) Simétrica 
 
6. a) x ρ* y ↔ x é algum número de anos mais velho do que y 
b) x ρ* y ↔ x é um ancestral masculino de y 
c) x ρ* y ↔ você pode dirigir de x para y em algum número de dias 
 
 
Cursos de Tecnologia da Informação - TI 
 
Matemática Discreta 
 Campus Nova AméricaCampus Nova AméricaCampus Nova AméricaCampus Nova América Prof. Aureo Ruffier 
 
Página 4 de 4 
7. a) b) c) 
 
 
8. a) b) 
 
Os dois grafos têm estruturas iguais 
 
9. a) ρ = { (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 3), (1, 5), (2, 4), (2, 5), (3, 5), (4, 5) } 
b) ρ = { (a, a), (b, b), (c, c), (d, d), (e, e), (f, f), (a, d), (b, e), (c, f) } 
c) ρ = { (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (2, 5), 
(3, 4), (3, 5), (4, 5) } 
 
10. [a] = { a, c } = [c] 
 
11. [3] = { 1, 2, 3 } e [4] = { 4, 5 } 
 
12. Reflexiva � (x, y) ρ (x, y), pois y = y 
Simétrica � se (x, y) ρ (z, w), então y = w, logo w = y e (z, w) ρ (x, y) 
Transitiva � se (x, y) ρ (z, w), e (z, w) ρ (s, t), então y = w e w = t, logo y = t e 
(x, y) ρ (s, t) 
As classes de equivalência são conjuntos de pares ordenados com as segundas 
componentes iguais.