L6D131

Prévia do material em texto

MAT 01375 – Matema´tica Discreta B 2013/1
Lista de Exerc´ıcios 6
1. Sejam A = {2, 3, 4, 5} e B = {5, 6, 8, 10}. Para cada relac¸a˜o Ri ⊆ A×B abaixo:
• explicite os elementos da relac¸a˜o;
• fac¸a uma representac¸a˜o matricial da relac¸a˜o;
• determine o domı´nio da relac¸a˜o;
• determine a imagem da relac¸a˜o;
• classifique a relac¸a˜o como injetora, sobrejetora, total e/ou funcional.
a) R1 = {(x, y); y e´ divis´ıvel por x}
b) R2 = {(x, y);xy = 40}
c) R3 = {(x, y); y = x+ 3}
e) R4 = {(x, y); 2x < y}
2. Sejam R ⊆ A × B uma relac¸a˜o e R−1 a sua inversa. Prove que R−1 e´ uma
func¸a˜o se, e somente se, R e´ injetora e sobrejetora. Deˆ um exemplo de uma relac¸a˜o
que na˜o e´ uma func¸a˜o, mas cuja inversa e´ uma func¸a˜o.
3. Seja A = {a, b, c}. Determine a representac¸a˜o matricial das seguintes relac¸o˜es
em A× A.
a) S1 = {(a, a), (a, b), (a, c)}
b) S2 = {(a, b), (b, a), (b, b), (c, c)}
c) S3 = {(a, a), (a, b), (a, c), (b, b), (b, c), (c, c)}
d) S4 = {(a, c), (c, a)}
Quais das relac¸o˜es acima sa˜o reflexivas, sime´tricas e/ou transitivas?
4. Classifique as relac¸o˜es abaixo, dadas por sua representac¸a˜o matricial, quanto a
reflexividade, simetria e transitividade. Justifique sua resposta.
T =
1 1 10 1 1
1 1 1
 ,M =

1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
 , N =

1 1 1 0
1 1 1 0
1 1 1 0
0 0 0 1
 .
5. Sejam A = {a, e, i, o, u}. Apresente um exemplo de uma relac¸a˜o em A que e´:
a) injetora e reflexiva
b) sobrejetora e sime´trica
c) anti-sime´trica e transitiva
d) injetora e na˜o total
e) funcional e sobrejetora
f) reflexiva e anti-sime´trica
g) na˜o sime´trica e na˜o anti-sime´trica
h) transitiva e sime´trica e na˜o reflexiva
6. Seja A um conjunto e R ⊆ A× A. Prove ou deˆ um contra-exemplo:
a) Se R e´ sime´trica e transitiva, enta˜o R e´ reflexiva.
b) Se R e´ reflexiva, enta˜o R e´ total.
c) Se R e´ reflexiva, enta˜o R e´ sobrejetora.
d) Se R e´ funcional, enta˜o R na˜o e´ transitiva.
e) Se R e´ sime´trica, enta˜o a relac¸a˜o R−1 coincide com R.
7. Seja Rn ⊂ Z×Z a relac¸a˜o de equivaleˆncia das congrueˆncias mo´dulo n, ou seja,
dizemos que
(a, b) ∈ Rn ⇐⇒ a− b e´ divis´ıvel por n.
Dado a ∈ Z denotaremos por [ a ]n a classe de equivaleˆncia de a com respeito a`
relac¸a˜o R. Descreva a classe de equivaleˆncia [ 4 ]n para:
a) n = 3,
b) n = 5,
c) n = 6.
8. Seja R a relac¸a˜o em N× N definida por:
((a, b), (c, d)) ∈ R⇐⇒ a+ d = b+ c.
a) Mostre que R e´ uma relac¸a˜o de equivaleˆncia.
b) Determine as classes de equivaleˆncia de [(1, 1)]R, [(2, 1)]R e [(3, 2)]R.
9. Seja R uma relac¸a˜o sobre Z dada por
xRy ⇐⇒ 4|(x+ 3y).
a) Mostre que a relac¸a˜o R e´ uma relac¸a˜o de equivaleˆncia;
b) Descreva a classe de equivaleˆncia [0]R.
10. Considere o conjunto Cn das func¸o˜es bijetoras, com domı´nio e imagem {1, . . . , n}.
Seja S ⊂ Cn um subconjunto que contenha a identidade e, para o qual, sempre
que f ∈ S temos f−1 ∈ S.
a) Liste os elementos de C3.
b) Suponha que S e´ o menor conjunto com as propriedades acima que conte´m as
func¸o˜es f1 e f2 tais que f1(1) = 1, f1(2) = 3, f1(3) = 2, f2(1) = 3, f2(2) = 1,
f2(3) = 2. Determine S.
Dizemos que as func¸o˜es g e h em Cn esta˜o relacionadas por RS se existe f ∈
S tal que g = f−1 ◦ h ◦ f .
c) Com f1 e f2 dados no item anterior, calcule f
−1
2 ◦ f1 ◦ f2 e f−11 ◦ f2 ◦ f1.
d) Mostre que, para func¸o˜es invert´ıveis f : A→ B e g : B → C, temos
(g ◦ f)−1 = f−1 ◦ g−1.
e) Mostre que RS e´ uma relac¸a˜o de equivaleˆncia.
(f) Descreva todas as classes de equivaleˆncia em C3 com respeito a` relac¸a˜o RS,
onde S = {I, T} para
I(x) = x e T (x) =

3, se x = 1
2, se x = 2
1, se x = 3