UNIVESP - 2021 - Exercícios de apoio 1 - Semana 5 - Fundamentos Matemáticos da Computação

Prévia do material em texto

1. Uma relação R sobre um conjunto A é transitiva se, e somente se,RoR⊆R. Verifique se R = {(1, 3), (1, 7), (3, 5), (5, 5), (7, 1), (7,
3), (7, 5), (11, 7)} sobre A = {1, 3, 5, 7, 11} é transitiva usando esse resultado teórico. 
Determinando RoR. 
aRb bRc RoR
1 3 3 5 (1, 5)
1 7 7 1 (1, 1)
1 7 7 3 (1, 3)
1 7 7 5 (1, 5)
3 5 5 5 (3, 5)
5 5 5 5 (5, 5)
7 1 1 3 (7, 3)
7 1 1 7 (7, 7)
7 3 3 5 (7, 5)
7 5 5 5 (7, 5)
11 7 7 1 (11, 1)
11 7 7 3 (11, 3)
11 7 7 5 (11, 5)
RoR não é transitiva, pois RoR , por exemplo, o par (1, 5)∈RoR e (1, 5)∉R.
2. Seja R uma relação sobre ℤ, verifique quais das relações abaixo são transitivas através da confirmação de RoR⊆R. 
1. R = {(x, y) : y ≤ x} 
RoR é definida por (x, y) ∈ RoR se ∃ y∈ℤ tal que: 
(x, y) ∈ RoR ⇔ ∃y ∈ ℤ / (x, y) ∈ R e (y, z) ∈ R 
(x, y) ∈ R ⇔ y ≤ x 
(y, z) ∈ R ⇔ z ≤ y 
z ≤ y ≤ x ⇒ z ≤ x 
Logo (x, z) ∈ RoR e R é transitiva.
2. R = {(x, y) : y = x } 
RoR: (x, z) ∈ RoR ⇔ (x, y) ∈ R ∧ (y, z) ∈ R 
(x, y) ∈ R ⇒ y = x
(y, z) ∈ R ⇒ z = y ⇒ z = x 
(x, x ) ∉ R, exceto em casos especiais x = 0, x = 1.
EXERCÍCIOS DE APOIO
Apenas para praticar. Não vale nota.
2
2
2 4
4
Não é transitiva e basta um contraexemplo: 
x = 2, y = 4 ⇒ (2, 2 ) ∈ R 
y = 4, z = 16 ⇒ (4, 4 ) ∈ R 
⇒ (2, 4 ) ∉ R.
3. Seja R uma relação sobre A = {0, 1, 2, 3, 4, 5} definida por R = , verifique se R é uma relação de ordem sobre A. 
R é uma relação de ordem ⇔ é reflexiva, antissimétrica e transitiva. 
Vamos construir a matriz booleana M de R: 
a/b 0 1 2 3 4 5
0 1 0 0 0 0 0
1 1 1 0 0 0 0
2 1 1 1 0 0 0
3 1 1 1 1 0 0
4 1 1 1 1 1 0
5 1 1 1 1 1 1
Reflexiva ⇔ = 1, ∀ i = 0, 1... 5
Antissimétrica ⇔ 
 
Transitiva ⇔ 
 
 
⇒ 
 
Portanto, R é uma relação de ordem sobre A.s
4. Considere a relação de R sobre o conjunto X: 
X = {x1, x2, x3, x4, x5} 
R = {(x1, x1), (x1, x2), (x1, x5), (x2, x1), (x2, x2), (x2, x5), (x3, x3), (x3, x4), (x4, x3), (x4, x4), (x5, x1), (x5, x2), (x5, x5)} 
Escreva a matriz booleana de R e verifique se R é uma relação de equivalência. 
R é uma relação de equivalência ⇔ R é reflexiva, simétrica e transitiva. 
Seja M a matriz booleana de R: 
2
2
2
Reflexiva: ⇒ R é reflexiva. 
Simétrica: M = M ⇒ R é simétrica. 
Transitiva: RoRCR ⇒ R é transitiva. 
Portanto, R é uma relação de equivalência.
5. Verifique se as relações = {(x, y) : x, y ∈ ℤ, x - y = 1} e g = {(x, y) : x, y ∈ ℤ, xy = 0} são funções e, em caso afirmativo, determine
o domínio e a imagem de cada uma delas.
Uma relação é uma função se (a, b) ∈ e (a, c) ∈ , então b = c. 
Para = {(x,y) : x, y ∈ ℤ, x - y = 1} 
(x, y) ∈ ⇔ x - y = 1 ⇔ y = x - 1 
(x, z) ∈ ⇔ x - z = 1 ⇔ z = x - 1 ⇒ y = z 
Portanto, é função. Dom( ) = ℤ Img ( ) = ℤ 
Para g = {(x, y) : x, y ∈ ℤ, xy = 0} 
(x,y) ∈ g ⇔ xy = 0 
(x,z) ∈ g ⇔ xz = 0 
Se x = 0, então xy = 0, ∀ y ∈ ℤ. Portanto, existem infinitos valores em ℤ que y pode assumir. Assim, g não é função.
6. Considere A o conjunto de todos os inteiros pares e B o conjunto de todos os inteiros ímpares. Prove que a função : A→ B,
definida por (x) = x + 1 é bijetora.
Se é bijetora, então ela é injetora e sobrejetora. 
Injetora: Sejam a1, a2 ∈ A, (a1) = (a2) ⇔ a1 + 1 = a2 + 1 ⇔ a1 = a2 
Portanto, é injetora. 
Sobrejetora: Seja b ∈ B, b = 2z + 1, z ∈ ℤ. 
Escolhendo a = 2z, a é par, a ∈ A e (a) = (2z) = 2z + 1 = b 
Portanto, é sobrejetora. 
Como é injetora e sobrejetora, então é bijetora.
7. Sejam as funções = {(-1, 1), (1, 3), (3,-1)} e g = {(1, -1), (3, 3), (-1, 1)}, determine, quando possível, g∘ e ∘g. No caso da
impossibilidade, identifique o motivo. 
T
g∘ = {(-1, -1), (1, 3), (3, 1)} 
Dom(g∘ ) = {-1, 1, 3} e Img(g∘ ) = {-1, 1, 3} 
∘g = {(1, 1), (3, 3), (-1, -1)} 
Dom( ∘g) = {-1, 1, 3} e Img( ∘g) = {-1, 1, 3}
8. Para = {(0,0), (1, 2), (2, 4)} determine a inversa , verifique se é uma função e determine -1∘ e ∘ se possível. 
 = {(0, 0), (2, 1), (4, 2)} 
-1 -1
-1
 e são funções. 
∘ = {(0, 0), (1, 1), (2, 2)} 
∘ = {(0, 0), (2, 2), (4, 4)}
9. Faça a concatenação das duas sequências finitas x e y, definidas por: 
x: {0, 1, 2, 3, 4, 5, 6} → ℤ, tal que x( ) = -2 
 y: {0, 1, 2, 3, 4} → ℤ, tal que y( ) = (-1) . 
x = {(0,-2), (1, -1), (2, 0), (3, 1), (4, 2), (5, 3), (6, 4)}, e |x| = 7. 
 y = {(0, 0), (1, -1), (2, 2), (3, -3), (4, 4)} e |y| = 5 
z é a sequência que concatena as sequências x e y. 
 
z = {(0,-2),(1,-1),(2, 0),(3, 1),(4, 2),(5, 3), (6, 4), (0, 0), (1, -1), (2, 2), (3, -3), (4, 4)}
10. Construa a sequência S = {(a, b): a = , b = z( ) e b ≥ a }, para = {0, 1, 2, 3, 4, 5, 6} e z( ) = - 2 
S = { }
11. Considere o conjunto e a seguinte relação sobre A:
Podemos afirmar que satisfaz as seguintes propriedades:
Reflexiva, antissimétrica e transitiva.
12. Seja a relação . Sobre essa relação, podemos afirmar que:
-1
-1
-1
Essa relação é uma função e sua imagem é definida por 
13. Seja uma relação sobre o conjunto A. A matriz booleana dessa relação é representada por:
Podemos afirmar, a partir da matriz acima, que a relação é:
Irreflexiva e antissimétrica.
14. Seja o conjunto e uma relação de ordem sobre A, representada por:
Sobre os elementos do conjunto mediado por , podemos afirmar que:
3 é mínimo e 4 é maximal.
15. Sejam as funções representadas graficamente por:
Podemos afirmar que é(são) sobrejetora(s):
Apenas a função F .
 
ESCONDER
GABARITO
3