Exercícios resolvidos sobre conjuntos, indução, relação e função

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 1
Indique se cada uma das seguintes expresso˜es e´ verdadeira, falsa ou se a notac¸a˜o esta´ errada. Nos
casos em que a expressa˜o seja falsa ou a notac¸a˜o esteja errada, explique brevemente sua resposta.
A notac¸a˜o {. . .} indica conjunto, na˜o multiconjunto ou qualquer outra coisa.
1. {a, b} ∪ {a, b, c, d} = {a, b, c, d}
2. {a, b} ∪ {a, c} = {a, a, b, c}
3. ∅ ∈ {a, b, c}
4. ∅ ⊆ {a, b, c}
5. {∅} = {{}}
6. {a} ⊆ {a, {a},{}}
7. a ⊆ {a, {a},{}}
8. {a} × {b, c} = {(b, a), (c, a)}
9. {a} × {b, c} = {a, b} × {c}
10. |P({a, b, c})| = 3 (P(A) e´ o conjunto de todos os subconjuntos de A)
Respostas: 1. Verdadeira. 2. Verdadeira. 3. Falsa, ∅ na˜o e´ um elemento de {a, b, c}.
4. Verdadeira. 5. Verdadeira. 6. Verdadeira. 7. A notac¸a˜o esta´ errada, a na˜o e´ um con-
junto. 8. Falso, {a} × {b, c} = {(a, b), (a, c)}. 9. Falso, {a} × {b, c} = {(a, b), (a, c)} e
{a, b} × {c} = {(a, c), (b, c)}. 10. Falso, |P({a, b, c})| = 23 = 8.
Indique se cada uma das seguintes expresso˜es e´ verdadeira, falsa ou se a notac¸a˜o esta´ errada. Nos
casos em que a expressa˜o seja falsa ou a notac¸a˜o esteja errada, explique brevemente sua resposta.
A notac¸a˜o {. . .} indica conjunto, na˜o multiconjunto ou qualquer outra coisa.
1. {a, b} ∩ {c, d} = ∅
2. {a, b} ∩ {c, d} = {∅}
3. ∅ ∈ ∅
4. ∅ ⊆ ∅
5. {} = {∅}
6. {a} ⊆ {∅, a, b}
7. {a} ∈ {a, {a},{}}
8. a ∈ {a, {a},{}}
9. |{a, b} × {c, d}| = 4
10. P({}) = ∅ (P(A) e´ o conjunto de todos os subconjuntos de A)
Respostas: 1. Verdadeira. 2. Falsa, {a, b}∩{c, d} na˜o conte´m nenhum elemento e {∅} conte´m
um elemento. 3. Falsa, ∅ na˜o conte´m nenhum elemento. 4. Verdadeira. 5. Falsa, o conjunto
{∅} na˜o e´ vazio. 6. Verdadeira. 7. Verdadeira. 8. Verdadeira. 9. Verdadeira. 10. Falsa,
P({}) = {∅}.
Prove, usando induc¸a˜o, que a soma dos quadrados dos primeiros n nu´meros naturais e´
1 + 4 + 9 + . . . + n2 =
n(n + 1)(2n + 1)
6
Resposta:
1. Para n = 1, 1 + 4 + 9 + . . . + n2 = 1 e tambe´m n(n+1)(2n+1)
6
= 1·2·3
6
= 1.
2. Suponha que a fo´rmula e´ verdadeira para n = k ≥ 1, i.e.,
1 + 4 + 9 + . . . + k2 =
k(k + 1)(2k + 1)
6
(1)
3. Mostramos que a fo´rmula e´ verdadeira para n = k + 1, i.e.,
1 + 4 + 9 + . . . + k2 + (k + 1)2 =
(k + 1)(k + 2)(2k + 3)
6
(2)
Somando (k + 1)2 a ambos da Eq. (1),
1 + 4 + 9 + . . . + k2 + (k + 1)2 =
k(k + 1)(2k + 1)
6
+ (k + 1)2
=
(k + 1)[k(2k + 1) + 6(k + 1)
6
=
(k + 1)(2k2 + 7k + 6)
6
(3)
As ra´ızes de 2k2 + 7k + 6 = 0 sa˜o k = −(7 ± √72 − 48/4 = −2 e − 3/2. Enta˜o,
2k2 + 7k + 6 = 2(k + 2)(k + 3/2) = (k + 2)(2k + 3). Substituindo em (3) obtemos (2)
Nossa turma da disciplina Autoˆmatos e Computabilidade possui uma quantidade de alunos n ≥ 2.
Cada aluno possui uma certa quantidade de amigos, dentre os alunos dessa turma (na˜o considere
os amigos que na˜o fazem parte da turma). Suponha que a amizade e´ uma relac¸a˜o sime´trica: se
Joa˜o e´ amigo de Maria, enta˜o Maria tambe´m e´ amiga de Joa˜o. Prove que existem pelo menos
dois alunos que tem a mesma quantidade de amigos.
Resposta: Este problema e´ similar ao problema de provar que todo grafo na˜o direcionado com
2 ou mais no´s conte´m dois no´s que possuem o mesmo grau, visto em aula. Seja n a quantidade
de alunos, e ai, com i = 1, . . . , n a quantidade de amigos de cada um deles. A prova e´ por
contradic¸a˜o: suponha que todos os ai’s sa˜o diferentes. O valor mı´nimo que ai pode ter e´ zero
(quando o aluno i na˜o possui nenhum amigo) e o ma´ximo e´ n− 1 (quando o aluno i e´ amigo
de todos os outros alunos). Isso nos da´ n valores diferentes para ai, de 0 a n − 1, para os n
alunos. Por tanto, deve existir um aluno que na˜o tem amigos (ai = 0) e outro que e´ amigo de
todos os alunos (ai = n− 1), o que e´ uma contradic¸a˜o. Assim, a suposic¸a˜o de que todos os ai’s
sa˜o diferentes deve ser falsa.
Determine se cada uma das seguintes relac¸o˜es e´ uma relac¸a˜o de equivaleˆncia. Se na˜o e´, indique uma
propriedade das relac¸o˜es de equivaleˆncia que na˜o e´ satisfeita (reflexiva, sime´trica ou transitiva).
Explique todas as respostas.
1. R = {(a, b)| a = b} sobre o conjunto N .
2. R = {(a, b)| a < b} sobre o conjunto N .
3. R = {(a, b)| a− b e´ par } sobre o conjunto N .
4. R = {(a, b)| a + b e´ impar } sobre o conjunto N .
5. R = {(a, b)| a2 = b2} sobre o conjunto Z.
Respostas:
1. A relac¸a˜o e´ uma relac¸a˜o de equivaleˆncia. E´ reflexiva, pois a = a; e´ sime´trica, pois se
a = b, enta˜o b = a ; e e´ transitiva, pois se a = b e b = c, enta˜o a = c.
2. A relac¸a˜o na˜o e´ uma relac¸a˜o de equivaleˆncia. Na˜o e´ sime´trica, pois se a < b, enta˜o b 6< a;
tampouco e´ reflexiva, pois a 6< a.
3. A relac¸a˜o e´ uma relac¸a˜o de equivaleˆncia. E´ reflexiva, pois a − a = 0, que e´ um nu´mero
par; e´ sime´trica, pois, se a− b e´ par enta˜o b− a tambe´m e´; e e´ transitiva, pois se a− b e
b− c sa˜o pares, enta˜o a− c = (a− b) + (b− c) e´ uma soma de nu´meros pares e tambe´m
e´ par.
4. A relac¸a˜o na˜o e´ uma relac¸a˜o de equivaleˆncia. Na˜o e´ reflexiva, pois a + a = 2a e´ sempre
par.
5. A relac¸a˜o e´ uma relac¸a˜o de equivaleˆncia. E´ reflexiva, pois a2 = a2; e´ sime´trica, pois se
a2 = b2, enta˜o b2 = a2 ; e e´ transitiva, pois se a2 = b2 e b2 = c2, enta˜o a2 = c2.
Seja A = {a, b, c}. Indique se cada uma das seguintes afirmac¸o˜es e´ verdadeira ou falsa, e explique
sua resposta.
1. A relac¸a˜o R = {(a, b), (b, a)} e´ sime´trica e reflexiva.
2. A relac¸a˜o R = {(a, a), (b, b), (c, c)} na˜o e´ sime´trica e e´ reflexiva.
3. A relac¸a˜o R = {(a, b), (b, c), (c, a)} e´ sime´trica e transitiva.
4. A relac¸a˜o R = {(a, b), (a, c), (a, a)} e´ reflexiva e transitiva.
5. A relac¸a˜o R = {(a, a), (b, b), (c, c)} e´ sime´trica, reflexiva e transitiva.
Respostas:
1. Falsa. A relac¸a˜o na˜o e´ reflexiva, pois (a, a) /∈ R. E´ sime´trica, pois se (x, y) ∈ R, enta˜o
(y, x) ∈ R, para x = a, y = b ou x = b, y = a.
2. Falsa. A relac¸a˜o e´ sime´trica, pois se (x, y) ∈ R, enta˜o (y, x) ∈ R, para x = y = a, b, ou c.
Tambe´m e´ reflexiva, pois (x, x) ∈ R para x = a, b, ou c.
3. Falsa. A relac¸a˜o na˜o e´ sime´trica, pois (a, b) ∈ R, no entanto (b, a) /∈ R, e tampouco e´
transitiva, pois (a, b), (b, c) ∈ R, no entanto (a, c) /∈ R.
4. Falsa. A relac¸a˜o na˜o e´ reflexiva, pois (b, b), (c, c) /∈ R. E´ transitiva, pois se (x, y), (y, z) ∈
R, enta˜o x = y = a e z = a, b, ou c, e (x, z) ∈ R.
5. Verdadeira. A relac¸a˜o e´ reflexiva e sime´trica (item 1), e tambe´m transitiva, pois se
(x, y), (y, z) ∈ R, para x = y = a, b, ou c, enta˜o x = y = z e (x, z) ∈ R.
Determine se cada uma das seguintes func¸o˜es e´ um-a-um (injetora) ou sobre (sobrejetora) ou
ambas (bijetora) ou nenhuma (nem injetora nem sobrejetora). Explique suas respostas.
1. f1 : N → N , f1(x) = x + 1.
2. f2 : Z → Z, f2(x) = 2x + 1.
3. f3 : N → N , f3(x) = x2.
4. f4 : Z → Z, f4(x) = x2.
5. f5 : R → Z, f5(x) = parte inteira de x.
Respostas:
1. A func¸a˜o e´ injetora, pois se x1 + 1 = x2 + 1, enta˜o x1 = x2. Na˜o e´ sobrejetora, pois 1
na˜o pertence ao contradomı´nio.
2. A func¸a˜o e´ injetora, pois se 2x1 + 1 = 2x2 + 1, enta˜o x1 = x2. Na˜o e´ sobrejetora, pois os
nu´meros pares na˜o pertencem ao contradomı´nio.
3. A func¸a˜o e´ injetora, pois se x21 = x
2
2, enta˜o x1 = x2. Na˜o e´ sobrejetora, pois somente os
quadrados perfeitos pertencem ao contradomı´nio.
4. A func¸a˜o na˜o e´ injetora, pois se x21 = x
2
2, enta˜o x1 = ±x2. Na˜o e´ sobrejetora, pois
somente os quadrados perfeitos pertencem ao contradomı´nio.
5. A func¸a˜o na˜o e´ injetora, pois nu´meros reais diferentes podem ter a mesma parte inteira
e diferir na parte decimal. E´ sobrejetora, pois a parte inteira dos nu´meros reais cobre
todo o conjunto de nu´meros inteiros.