Ativ 7

Prévia do material em texto

Atividade 07 – Discreta 
Kelvy Hallyson Leôncio Silva – kelvyhallyson4@gmail.com 
Q1 – (b) Considere R ⊆ A² tal que R = {(𝑥, 𝑦) | 𝑥 > 3 ∧ 𝑦 > 3} 
R = {(4,4)} 
 
(e) Considere R ⊆ A² tal que R = {(𝑥, 𝑦) | 𝑥 < 𝑦} 
R = {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)} 
 
(j) Considere R ⊆ A² tal que R = {(𝑥, 𝑦) |(𝑥 = 𝑦) ∨ (𝑥 é 𝑝𝑟𝑖𝑚𝑜 ∧ 𝑦 é 𝑝𝑟𝑖𝑚𝑜) ∨
(𝑥 é 𝑝𝑎𝑟)} 
R = {(1,1), (2,1), (2,2), (2,3), (2,4), (3,2), (3,3), (4,1), (4,2), (4,3), (4,4)} 
 
Q3 – (a) Sejam 𝑎, 𝑏 são inteiros e 𝑚 um inteiro positivo, suponha que 𝑎 = 𝑏, se 𝑎 ≡
𝑏 (𝑚𝑜𝑑 𝑚), pela definição de congruência modular, 𝑚 | (𝑎 − 𝑏). Como 𝑎 = 𝑏, então, 
𝑚 | (𝑎 − 𝑎), assim, 𝑚 | 0, logo, é reflexiva pois todo inteiro positivo divide 0. 
 
(b) Sejam 𝑎, 𝑏 são inteiros e 𝑚 um inteiro positivo, suponha 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚), pela 
definição de congruência modular, 𝑚 | (𝑎 − 𝑏), pela definição de divisibilidade existe 
um inteiro 𝑘 tal que (𝑎 − 𝑏) = 𝑚 ∗ 𝑘, multiplicando ambos os lados da equação por 
−1, obtemos: 
(−1) ∗ (𝑎 − 𝑏) = 𝑚 ∗ 𝑘 ∗ (−1), como 𝑚 é positivo, então: 
(−𝑎 + 𝑏) = 𝑚 ∗ (−𝑘), reorganizando os termos, temos: 
(𝑏 − 𝑎) = 𝑚 ∗ −𝑘, pela definição de divisibilidade, 𝑚 | (𝑏 − 𝑎) e pela definição de 
congruência modular 𝑏 ≡ 𝑎 (𝑚𝑜𝑑 𝑚), logo, é simétrica. 
 
(c) Contra-exemplo: 
4 ≡ 2 (𝑚𝑜𝑑 2), pois 2 | (4 − 2) ou 2 | 2, assim como 2 ≡ 4 (𝑚𝑜𝑑 2), pois 2 | (2 − 4) 
ou 2 | -2, logo, não é anti-simétrica. 
 
(d) Sejam 𝑎, 𝑏, 𝑐 são inteiros e 𝑚 um inteiro positivo. 
Suponha que 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) ∧ 𝑏 ≡ 𝑐 (𝑚𝑜𝑑 𝑚), assim, 𝑚 | (𝑎 − 𝑏) ∧ 𝑚 | (𝑏 − 𝑐), 
pela definição de divisibilidade, existem inteiro 𝑥, 𝑦 tal que 
(𝑎 − 𝑏) = 𝑚 ∗ 𝑥 e (𝑏 − 𝑐) = 𝑚 ∗ 𝑦, assim: 
(𝑎 − 𝑏) + (𝑏 − 𝑐) = (𝑚 ∗ 𝑥) + (𝑚 ∗ 𝑦), usando a associatividade da soma/subtração: 
𝑎 + (−𝑏 + 𝑏) − 𝑐 = (𝑚 ∗ 𝑥) + (𝑚 ∗ 𝑦), assim: 
𝑎 − 𝑐 = (𝑚 ∗ 𝑥) + (𝑚 ∗ 𝑦), pela propriedade distributiva: 
𝑎 − 𝑐 = 𝑚 ∗ (𝑥 + 𝑦), assim, pela definição de divisibilidade 𝑚 | (𝑎 − 𝑐) e pela 
definição de congruência modular 𝑎 ≡ 𝑐 (𝑚𝑜𝑑 𝑚), logo, é transitiva. 
 
Q4 – (e) Reflexividade: 
Seja 𝑥, 𝑦 ∈ ℕ, para a relação 𝑅5 ser reflexiva, para todos 𝑥 e 𝑦, 𝑥 = 𝑦 ∧ (𝑥, 𝑦) ∈ 𝑅5. 
Porém a condição da relação é que 𝑥 ≠ 𝑦, logo, podemos provar por meio de um 
contra-exemplo: 
1 ∈ ℕ, mas, (1,1) ∉ 𝑅5, pois 𝑥 = 𝑦, logo, não é reflexiva. 
 
Simetria: 
Seja 𝑥, 𝑦 ∈ ℕ, para a relação 𝑅5 ser simétrica, se (𝑥, 𝑦) ∈ 𝑅5 então (𝑦, 𝑥) ∈ 𝑅5. 
Suponha que (𝑥, 𝑦) ∈ 𝑅5, assim, 𝑥 ≠ 𝑦, igualmente, 𝑦 ≠ 𝑥, portanto, (𝑦, 𝑥) ∈ 𝑅5, logo, 
ela é simétrica. 
 
Anti-simetria: 
Seja 𝑥, 𝑦 ∈ ℕ, para a relação 𝑅5 ser anti-simétrica, para todos 𝑥 e 𝑦, se (𝑥, 𝑦) ∈ 𝑅5 ∧
𝑥 ≠ 𝑦 então (𝑦, 𝑥) ∉ 𝑅5. Podemos apresentar um contra-exemplo: 
(1,2) ∈ 𝑅5 ∧ 1 ≠ 2, mas, (2,1) ∈ 𝑅5, pois 2 ≠ 1, logo, não é anti-simétrica. 
 
Transitividade: 
Seja 𝑥, 𝑦, 𝑧 ∈ ℕ, para a relação 𝑅5 ser simétrica, se (𝑥, 𝑦) ∈ 𝑅5 ∧ (𝑦, 𝑧) ∈ 𝑅5 então 
(𝑥, 𝑧) ∈ 𝑅5. Podemos apresentar um contra-exemplo: 
(1,2) ∈ 𝑅5 ∧ (2,1) ∈ 𝑅5, então (1,1) ∈ 𝑅5, porém pela condição da relação, 𝑥 ≠ 𝑦, 
então (1,1) ∉ 𝑅5, logo, não é transitiva.