AVALIAÇÃO CONTINUADA - SEMANA 7

Prévia do material em texto

UNIVERSIDADE FEDERAL DO CEARÁ 
CENTRO DE CIÊNCIAS TECNOLÓGICAS 
DEPARTAMENTO DE ENGENHARIA DE COMPUTAÇÃO 
 
 
 
 
 
 
 
 
MATEMÁTICA DISCRETA 
 AVALIAÇÃO CONTINUADA – SEMANA 07 
 Chrystian Gemaque Maciel - 501212 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
QUIXADÁ 
 2021 
1) Seja A = {1, 2, 3, 4}, crie uma relação que: 
b) seja simétrica, antissimétrica e transitiva, mas não seja reflexiva: 
Não-reflexiva: {(1,2), (2,1), (3,1), (3,2), (4,1), (4,2), (4,3), (1,3), (1,4), (2,3), (2,4), 
(3,4)} 
Simétrica: Quando a∈R(b) ⇔ b∈R(a){(1,1), (2,2), (3,3), (4,4)} 
Transitiva: Quando b∈R(a) e c R(a) e c∈R(b) ⇒ c∈R(a) 
Resposta: R ⊆ AxA, tal que R = {(1, 1), (2, 2), (3, 3)} 
 
e) seja antissimétrica e transitiva, mas não seja reflexiva nem simétrica: 
Antissimétrica: Não será assimétrica quando {(1,1), (2,2), (3,3), (4,4)} 
Transitiva: Quando b∈R(a) e c R(a) e c∈R(b) ⇒ c∈R(a) 
Resposta: R ⊆ AxA, tal que R = {(1, 2), (2, 3), (3, 4), (1, 3), (2, 4), (1, 4)} 
 
j) seja reflexiva, mas não seja simétrica, antissimétrica, nem transitiva 
Resposta: Reflexiva: R ⊆ AxA, tal que R = {(1,1), (2,2), (3, 3), (4, 4), (1, 3), (3,1), (4, 
2), (2, 1)} 
 
3) Seja m um inteiro positivo, prove que: 
a) “a relação de congruência no módulo m é reflexiva.” 
Resposta: Se x pertence aos inteiros tal que x ≡ x (mod m), dessa forma temos que provar 
que x ≡ x (mod m), para isso m | (x - x) tem que ser verdadeiro, podemos afirmar que m 
| (x - x) é correto, pois existe um inteiro ‘a’, tal que m.a = (x - x), lembrando que (x - x) 
= 0, ou seja, ‘a’ = 0, assim então provamos que a relação de congruência no módulo m é 
reflexiva. 
Exemplo: 3 ≡ 3 (mod m)  Propriedade Reflexiva, onde escolho que modulo é 5 para 
provar o teorema, 3 ≡ 3 (mod m “5”)  ficando 5 | ( 3 – 3)  5 | 0  0 
 
b) “a relação de congruência no módulo m é simétrica.” 
Resposta: Se x e y pertencem aos inteiros tal que, x ≡ y (mod m) e y ≡ x (mod m), Se x 
≡ y (mod m), ou seja, m|(x - y), ou seja, existe um inteiro ‘a’ tal que m.a = (x - y), Se y ≡ 
x (mod m), ou seja, m|(y - x), ou seja, existe um inteiro ‘b’ tal que m.b = (y - x), se 
multiplicamos m.b = (y - x) por -1, obtemos: -(m.b) = (x - y), mostrando a relação entre 
m.b e m.a, assim provando que se x ≡ y (mod m) então y ≡ x (mod m), dessa forma 
provamos que a relação de congruência no módulo m é simétrica. 
 
Exemplo: 3 ≡ 8 (mod m “5”) e 8 ≡ 3 (mod m “5”) provando a propriedade 
simétrica. 
 
c) “a relação de congruência no módulo m não é antissimétrica.” 
Resposta: Se x e y pertence aos inteiros, tal que, x ≡ x (mod m), mas x não é congruente 
de y (mod m) e y não é congruente de x (mod m), como visto no item b, teremos a relação 
(x, y) e (y, x), o que não condiz com a definição de antissimétrica, que é ∀x ∈ A, ∀y ∈ A, 
( ( (x, y) ∈ R ∧ x 6= y ) → (y, x) ∈/ R ), dessa forma provamos que a relação de 
congruência no módulo m não é antissimétrica. 
 
Exemplo: 3 ≡ 1 (mod m “5”), nesse exemplo a relação de congruência e não é 
simétrica e nem antissimétrica. 
d) “a relação de congruência no módulo m é transitiva.” 
Resposta: Se tivermos x, y, z pertencentes aos inteiros, tal que x ≡ y (mod m), y ≡ z (mod 
m) e x ≡ z (mod m), se x ≡ y (mod m) e y ≡ z (mod m) então x ≡ z (mod m), se x ≡ y (mod 
m), então existe um inteiro ‘a’, tal que m | (x-y), ou seja, m.a = (x-y), se y ≡ z (mod m), 
então existe um inteiro ‘b’, tal que m | (y-z), ou seja, m.b = (y-z), se x ≡ z (mod m), então 
existe um inteiro ‘c’, tal que m | (x-z), ou seja, m.c = (x-z), tendo m.a = (x-y), chegamos 
a conclusão que x = m.a + y, tendo m.b = (y-z), chegamos a conclusão que y = m.b + z, 
dessa forma m.c = m.a + m.b + z - z; m.c = m.(a + b); c = a + b, assim provamos que se 
x ≡ y (mod m) e y ≡ z (mod m) então x ≡ z (mod m), dessa forma provamos que a relação 
de congruência no módulo m é transitiva. 
Exemplo: 3 ≡ 8 (mod m “5”) e 8 ≡ 18 (mod m “5”) então 3 ≡ 18 (mod m “5”). 
 
4) e) R5 ⊆ N × N, tal que R5 = {(x, y) | x ≠ y} 
Resposta: REFLEXIVIDADE: Não satisfaz, pois é impossível ter os pares tipo (1,1), 
já que só entra pares se x ≠ y. 
SIMETRIA: Sejam x e y inteiros, tal que (x, y) pertence a R5, se tivermos (y, x), tal 
que y ≠ x, então (y, x) também pertence a R5, ou seja, existe uma relação simétrica. 
ANTISSIMETRIA: Não satisfaz, pois se pegarmos o par (2, 1) que satisfaz a 
condição x ≠ y, também teremos o par (1, 2) que também satisfaz a condição x ≠ y. 
TRANSITIVIDADE: Se tivermos os inteiro a, b, c pertencentes aos inteiros, se (a, 
b) ∈ R5 e (b, c) ∈ R5, então podemos dizer que (a, c) ∈ R5, como a, b, c são inteiro 
independentes ou seja diferentes, entra na condição x ≠ y. Dessa forma provamos 
que existe a relação de transitividade. 
N×N = {(0,0), (0,1), (1,0), (0,2), (1,1), (2,0), (0,3), (1,2), ..........} 
R5 = {(0,1), (1,0), (0,2), (2,0), (0,3), (3,0), .............}