Sol_L6D131

Prévia do material em texto

MAT 01375 – Matema´tica Discreta B 2013/1
Lista de Exerc´ıcios 6
Soluc¸o˜es de Exerc´ıcios Escolhidos
1.
(a) R1 = {(2, 6), (2, 8), (2, 10), (3, 6), (4, 8), (5, 5), (5, 10)}. O domı´nio da relac¸a˜o
e´ A, a imagem e´ B. Uma representac¸a˜o matricial e´ dada por
0 1 1 1
0 1 0 0
0 0 1 0
1 0 0 1
 .
A relac¸a˜o e´ total e sobrejetora, mas na˜o e´ injetora ou funcional.
(c) R3 = {(2, 5), (3, 6), (5, 8)}. O domı´nio da relac¸a˜o e´ {2, 3, 5}, a imagem e´
{5, 6, 8}. Uma representac¸a˜o matricial e´ dada por
1 0 0 0
0 1 0 0
0 0 0 0
0 0 1 0
 .
A relac¸a˜o e´ injetora e funcional, mas na˜o e´ total ou sobrejetora.
5. Exemplos para alguns dos itens pedidos sa˜o:
(a) R = {(a, a), (e, e), (i, i), (o, o), (u, u)}
(b) O exemplo do item (a) ou R = {(a, e), (e, a), (i, o), (o, i), (o, u), (u, o)}.
(c) O exemplo do item (a) ou R = {(i, i)} ou R = {(a, e), (e, i), (a, i), (o, u)}.
(d) R = {(a, a), (e, e), (i, i), (o, o)}
6.
(a) Falso. A relac¸a˜o em A = {a, b, c, d} dada por R = {(b, b), (b, c), (c, b), (d, d)}
e´ sime´trica e transitiva, mas na˜o e´ reflexiva.
(b) Verdadeiro. Prova: Seja x ∈ A. Como R e´ reflexiva, temos que (x, x) ∈ R,
logo x esta´ no domı´nio da relac¸a˜o. Portanto, o domı´nio de R e´ A, de forma
que R e´ total.
(c) Verdadeiro. Prova: Seja x ∈ A. Como R e´ reflexiva, temos que (x, x) ∈ R,
logo x esta´ no contradomı´nio da relac¸a˜o. Portanto, o contradomı´nio de R e´
A, de forma que R e´ sobrejetora.
(d) Falso. A relac¸a˜o em A = {a, b, c, d} dada por R = {(a, a), (b, b), (c, c), (d, d)}
e´ funcional e transitiva.
(e) Verdadeiro. Prova: Para provar que R−1 = R, consideraremos cada uma das
contenc¸o˜es separadamente.
(R−1 ⊆ R): Seja (x, y) ∈ R−1. Por definic¸a˜o de relac¸a˜o inversa, temos (y, x) ∈
R e, como R e´ sime´trica, temos (x, y) ∈ R, como quer´ıamos demonstrar.
(R−1 ⊇ R): Seja (x, y) ∈ R. Como R e´ sime´trica, temos (y, x) ∈ R, de forma
que (x, y) ∈ R−1 pela definic¸a˜o de relac¸a˜o inversa.
Poder´ıamos tambe´m ter escrito
(x, y) ∈ R−1 ⇔ (y, x) ∈ R⇔ (x, y) ∈ R,
onde a primeira equivaleˆncia segue da definic¸a˜o de relac¸a˜o inversa e a segunda,
da simetria de R.
8. Para provar que a relac¸a˜o R e´ de equivaleˆncia, provaremos que e´ reflexiva,
sime´trica e transitiva.
(Reflexividade): Seja (a, b) ∈ N × N. Como a + b = b + a, temos (a, b)R(a, b),
como quer´ıamos demonstrar.
(Simetria): Sejam (a, b), (c, d) ∈ N × N tais que (a, b)R(c, d), isto e´, tais que
a + d = b + c. Isso e´ o mesmo que dizer que c + b = d + a, de forma que
(c, d)R(a, b), como quer´ıamos demonstrar.
(Transitividade): Sejam (a, b), (c, d), (e, f) ∈ N×N tais que (a, b)R(c, d) e (c, d)R(e, f).
Por definic¸a˜o, temos a + d = b + c e c + f = d + e. Note que
a + f + c + d = (a + d) + (c + f) = (b + c) + (d + e) = b + e + c + d.
Isso leva a
a + f + c + d = b + e + c + d =⇒ a + f = b + e,
implicando (a, b)R(e, f), como quer´ıamos demonstrar.
A classe de equivaleˆncia de (1, 1) e´ dada pelo conjunto de pares (a, b) tais que
a + 1 = b + 1⇔ a = b, isto e´,
[(1, 1)]R = {(x, x) : x ∈ N}.
A classe de equivaleˆncia de (2, 1) e´ dada pelo conjunto de pares (a, b) tais que
a + 1 = b + 2⇔ a = b + 1, isto e´,
[(2, 1)]R = {(x + 1, x) : x ∈ N}.
Como (3, 2) ∈ [(2, 1)]R, temos [(3, 2)]R = [(2, 1)]R.
10. O enunciado da questa˜o estava incompleto. O conjunto S tambe´m
precisa ter a propriedade de que f, g ∈ S =⇒ f ◦ g ∈ S.
(a) C3 = {g1, g2, g3, g4, g5, g6}, onde a func¸a˜o gj associa o elemento i ∈ {1, 2, 3} a`
entrada (i, j) da matriz 1 1 2 2 3 32 3 1 3 1 2
3 2 3 1 2 1
 .
(b) A definic¸a˜o do conjunto exige que as inversas das func¸o˜es do conjunto tambe´m
estejam no conjunto. Note que f−11 satisfaz f
−1
1 (1) = 1, f
−1
1 (2) = 3, f
−1
1 (3) =
2, isto e´ f−11 = f1. Da mesma forma f
−1
2 satisfaz f
−1
2 (1) = 2, f
−1
2 (2) =
3, f−12 (3) = 1, que e´ diferente de f1, f2 e deve ser adicionada ao conjunto.
Ale´m disso, falta adicionar a identidade, que coincide com a sua inversa.
Utilizando a notac¸a˜o do item (a), conclu´ımos que S = {g1, g2, g4, g5}.
Com a alterac¸a˜o no enunciado, tambe´m precisamos verificar que qualquer
composic¸a˜o de elementos de S esta´ em S. Isso nos obriga a adicionar g6 =
g2 ◦ g4 e g3 = g2 ◦ g5 a S, de forma que S = C6.
(c) Na notac¸a˜o do item (a), temos f−12 ◦ f1 ◦ f2 = g6 e f−11 ◦ f2 ◦ f1 = g4.
(d) Como f : A→ B e g : B → C sa˜o invert´ıveis, as func¸o˜es inversas f−1 : B → A
e g−1 : C → B esta˜o bem definidas. Ale´m disso, e´ claro que g ◦ f : A→ C e
f−1 ◦ g−1 : C → A. Verificaremos que f−1 ◦ g−1 satisfaz as propriedades da
inversa de g ◦ f .
(i) Dado x ∈ A, temos
(f−1 ◦ g−1) ◦ (g ◦ f)(x) = f−1 (g−1 (g (f(x)))) = f−1 (f(x)) = x,
e portanto (f−1 ◦ g−1) ◦ (g ◦ f) e´ a identidade em A. A primeira igualdade
acima utiliza a definic¸a˜o de composic¸a˜o, a segunda o fato de que g−1 e´ a
inversa de g e a terceira que f−1 e´ a inversa de f .
(ii) Com os mesmos argumentos do item anterior, dado z ∈ C,
(g ◦ f) ◦ (f−1 ◦ g−1)(z) = g (f (f−1 (g−1(z)))) = g (g−1(z)) = z,
e portanto (g ◦ f) ◦ (f−1 ◦ g−1) e´ a identidade em C.
Por definic¸a˜o, temos (g ◦ f)−1 = f−1 ◦ g−1.
(e) Seja S ⊂ Cn um com as propriedades inicadas.
(Reflexividade): Para f ∈ Cn, temos f = I−1 ◦ f ◦ I, onde I denota a
identidade em Cn. Como I ∈ S, conclu´ımos que fRSf .
(Simetria): Sejam f, g ∈ Cn tais que fRSg. Seja h ∈ S tal que g = h−1◦f ◦h.
Note que
h ◦ g ◦ h−1 = h ◦ (h−1 ◦ f ◦ h) ◦ h−1 = (h ◦ h−1) ◦ f ◦ (h ◦ h−1) = I ◦ f ◦ I = f.
Na segunda igualdade, utilizamos a associatividade da composic¸a˜o de func¸o˜es
e, na terceira, a definic¸a˜o de func¸a˜o inversa. A equac¸a˜o acima implica que
f = h ◦ g ◦ h−1 = (h−1)−1 ◦ g ◦ h−1,
de forma que gRSf pelo fato de que h ∈ S =⇒ h−1 ∈ S.
(Transitividade): Sejam f, g, h ∈ Cn tais que fRsg e gRsh. Sejam p, q ∈ S
tais que g = p−1 ◦ f ◦ p e h = q−1 ◦ g ◦ q. Conclu´ımos que
h = q−1 ◦ (p−1 ◦ f ◦ p) ◦ q = (q−1 ◦ p−1) ◦ f ◦ (p ◦ q) = (p ◦ q)−1 ◦ f ◦ (p ◦ q).
Na segunda igualdade, novamente utilizamos a associatividade da composic¸a˜o,
e na terceira, o item (d). Pela definic¸a˜o de S temos que p, q ∈ S =⇒ p◦q ∈ S,
de forma que fRSh.
(f) Na notac¸a˜o do item (a), temos S = {I, g6}. As classes de equivaleˆncia sa˜o
{I, g6}, {g2, g3} e {g4, g5}.