Baixe o app para aproveitar ainda mais
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.
Compartilhar