Buscar

provas_anteriores_RESPOSTA

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 59 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 59 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 59 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Matema´tica Discreta
Provas Anteriores
1 Lo´gica e Prova
1.1 Introduc¸a˜o a Lo´gica e Tabela Verdade
1. {0, 25 pt} Deˆ um exemplo de uma sentenc¸a que e´ uma proposic¸a˜o e justifique
porque ela e´ uma proposic¸a˜o.
Resposta: “Joa˜o gosta de futebol” e´ uma proposic¸a˜o porque pode ser ver-
dadeiro ou falso, mas na˜o ambos.
2. {0, 25 pt} Deˆ um exemplo de uma sentenc¸a que na˜o e´ uma proposic¸a˜o e justi-
fique porque ela na˜o e´ uma proposic¸a˜o.
Resposta: “Fac¸a todos as questo˜es da prova” na˜o e´ uma proposic¸a˜o porque
na˜o e´ nem verdadeiro nem falso.
3. {0, 5 pt} Fac¸a a tabela verdade de (p→ ¬q)→ (q ∨ ¬p).
Resposta:
p q ¬q (p→ ¬q) ¬p (q ∨ ¬p) (p→ ¬q)→ (q ∨ ¬p)
F F T T T T T
F T F T T T T
T F T T F F F
T T F F F T T
4. {0, 4 pt} Prove por tabela verdade que ¬((q ∧ (q ∨ p)) ∨ ¬q) ≡ F.
Resposta:
p q q ∨ p q ∧ (q ∨ p) ¬q (q ∧ (q ∨ p)) ∨ ¬q ¬((q ∧ (q ∨ p)) ∨ ¬q)
F F F F T T F
F T T T F T F
T F T F T T F
T T T T F T F
5. {0, 7 pt} Prove por tabela verdade que ((p→ q) ∧ (p→ r)) ≡ (p→ (q ∧ r)).
Resposta:
Seja LE (lado esquerdo) = (p→ q) ∧ (p→ r) e
LD (lado direito) = p→ (q ∧ r).
p q r p→ q p→ r LE q ∧ r LD LE ↔ LD
F F F T T T F T T
F F T T T T F T T
F T F T T T F T T
F T T T T T T T T
T F F F F F F F T
T F T F T F F F T
T T F T F F F F T
T T T T T T T T T
Resposta 1: Como a 9a coluna e´ uma tautologia, ((p → q) ∧ (p → r)) ≡
(p→ (q ∧ r)).
Resposta 2: Como a coluna LD e LE teˆm os mesmos valores a cada linha,
((p→ q) ∧ (p→ r)) ≡ (p→ (q ∧ r)).
6. {0, 7 pt} Prove por tabela verdade que ((p∧ q)∨ (p∧ r)) ≡ ¬(p→ ¬(q ∨ r)).
Resposta:
p q r p ∧ q p ∧ r (p ∧ q) ∨ (q ∨ r) q ∨ r ¬(q ∨ r) p→ ¬(q ∨ r) ¬(p→ ¬(q ∨ r))
F F F F F F F T T F
F F T F F F T F T F
F T F F F F T F T F
F T T F F F T F T F
T F F F F F F T T F
T F T F T T T F F T
T T F T F T T F F T
T T T T T T T F F T
Como as colunas 6 e 10 teˆm o mesmo comportamento linha a linha, as ex-
presso˜es ((p ∧ q) ∨ (p ∧ r)) e ¬(p→ ¬(q ∨ r)) sa˜o logicamente equivalentes.
7. {0, 7 pt} Prove por tabela verdade que ((p→ r) ∨ (q → r)) ≡ ((p ∧ q)→ r).
Resposta:
p q r p→ r q → r (p→ r) ∨ (q → r) (p ∧ q) (p ∧ q)→ r
F F F T T T F T
F F T T T T F T
F T F T F T F T
F T T T T T F T
T F F F T T F T
T F T T T T F T
T T F F F F T F
T T T T T T T T
Como as colunas 6 e 8 teˆm o mesmo comportamento linha a linha, as expresso˜es
((p→ r) ∨ (q → r)) e ((p ∧ q)→ r) sa˜o logicamente equivalentes.
8. {0, 7 pt} Prove por tabela verdade que
( ( p→ ((q ∨ ¬¬¬q) ∧ q) ) ∧ (¬p→ q) ) ≡ q.
Resposta: Sejam
A = q ∨ ¬¬¬q
B = (q ∨ ¬¬¬q) ∧ q
C = p→ ((q ∨ ¬¬¬q) ∧ q)
D = ¬p
E = ¬p→ q
F = ( p→ ((q ∨ ¬¬¬q) ∧ q) ) ∧ (¬p→ q)
p q ¬q ¬¬q ¬¬¬q A B C D E F
F F T F T T F T T F F
F T F T F T T T T T T
T F T F T T F F F T F
T T F T F T T T F T T
Como as colunas 2 e 11 teˆm o mesmo comportamento linha a linha, as ex-
presso˜es sa˜o logicamente equivalentes.
9. {0, 7 pt} Prove por tabela verdade que
( ((s ∧ s) ∨ ¬q) ∧ (((¬q → ¬q) ∧ ¬q) ∨ s) ) ≡ (q → s)
Resposta:
q s s ∧ s ¬q (s ∧ s) ¬q → ¬q (¬q → ¬q) ((¬q → ¬q) ((s ∧ s) ∨ ¬q)∧ q → s
∨¬q ∧¬q ∧¬q) ∨ s (((¬q → ¬q) ∧ ¬q) ∨ s)
F F F T T T T T T T
F T T T T T T T T T
T F F F F T F F F F
T T T F T T F T T T
Como as colunas 9 e 10 teˆm o mesmo comportamento linha a linha, as ex-
presso˜es sa˜o logicamente equivalentes.
10. {0, 3 pt} Traduza para uma fo´rmula da lo´gica proposicional: Se chove e molha,
enta˜o ou vou a` praia ou na˜o molha (mas na˜o ambos).
Resposta:
p = chove
q = molha
r = vou a` praia
Traduc¸a˜o: p ∧ q → r ⊕ ¬q
11. {0, 5 pt} Fac¸a a tabela verdade da sua traduc¸a˜o do Quesito 10.
Resposta:
p q r p ∧ q ¬q r ⊕ ¬q p ∧ q → r ⊕ ¬q
F F F F T T T
F F T F T F T
F T F F F F T
F T T F F T T
T F F F T T T
T F T F T F T
T T F T F F F
T T T T F T T
12. {0, 2 pt} Responda “Sim” ou “Na˜o”: a frase do Quesito 10 e´ uma tautologia?
Resposta: Na˜o.
13. {0, 3 pt} Traduza para uma fo´rmula da lo´gica proposicional: Ganhar ou perder
(ou ambos) implica em aprender e na˜o perder.
Resposta:
p = ganhar
q = perder
r = aprender
Traduc¸a˜o: p ∨ q → r ∧ ¬q
14. {0, 5 pt} Fac¸a a tabela verdade da sua traduc¸a˜o do Quesito 13.
Resposta:
p q r p ∨ q ¬q r ∧ ¬q p ∨ q → r ∧ ¬q
F F F F T F T
F F T F T T T
F T F T F F F
F T T T F F F
T F F T T F F
T F T T T T T
T T F T F F F
T T T T F F F
15. {0, 2 pt} Responda “Sim” ou “Na˜o”: a frase do Quesito 13 e´ uma contradic¸a˜o?
Resposta: Na˜o.
1.2 Lo´gica Proposicional - Prova de Equivaleˆncias
1. {1, 0 pt} Prove, sem usar a tabela verdade, que
(p→ ¬q) ∧ (p→ ¬r) ≡ ¬((q ∨ r) ∧ p).
Justifique cada passo da prova com uma equac¸a˜o em anexo.
Resposta:
(p→ ¬q) ∧ (p→ ¬r)
≡ p→ (¬q ∧ ¬r) [27]
≡ ¬p ∨ (¬q ∧ ¬r) [22]
≡ ¬p ∨ ¬(q ∨ r) [17]
≡ ¬(p ∧ (q ∨ r)) [16]
≡ ¬((q ∨ r) ∧ p) [11]
2. {0, 8 pt} Prove com equivaleˆncias lo´gicas que
¬(p ∨ (p ∧ r)) ∨ (¬(q ∨ ¬r)) ≡ (p→ ¬q) ∧ (p→ r).
Justifique cada passo de prova com as equac¸o˜es em anexo.
Resposta:
¬(p ∨ (p ∧ r)) ∨ (¬(q ∨ ¬r))
≡ (¬p) ∨ (¬(q ∨ ¬r)) [18]
≡ (¬p) ∨ (¬q ∧ ¬¬r) [17]
≡ (¬p) ∨ (¬q ∧ r) [9]
≡ p→ (¬q ∧ r) [22]
≡ (p→ ¬q) ∧ (p→ r) [27]
3. {2, 0 pt} Prove que
((r ∨ s)↔ q) ≡ (((¬r ∧ ¬s) ∨ q) ∧ (¬q ∨ (r ∨ s)))
Resposta:
(r ∨ s)↔ q
≡ ((r ∨ s)→ q) ∧ (q → (r ∨ s)) [31]
≡ (¬(r ∨ s) ∨ q) ∧ (q → (r ∨ s)) [22]
≡ (¬(r ∨ s) ∨ q) ∧ (¬q ∨ (r ∨ s)) [22]
≡ ((¬r ∧ ¬s) ∨ q) ∧ (¬q ∨ (r ∨ s)) [17]
4. {2, 0 pt} Prove que
((r ∨ s)↔ q) ≡ (((¬r ∧ ¬s) ∨ q) ∧ (¬q ∨ (r ∨ s)))
Justifique cada passo de prova com exatamente 1 equac¸a˜o da lista em anexo.
A u´nica excec¸a˜o a esta regra e´ o uso de comutatividade e associatividade.
Ou seja, as equac¸o˜es (10), (11), (12), (13), (73), (74), (75) e (76) podem ser
usadas simultaneamente em 1 passo de prova.
Resposta:
(r ∨ s)↔ q
≡ ((r ∨ s)→ q) ∧ (q → (r ∨ s)) [31]
≡ (¬(r ∨ s) ∨ q) ∧ (q → (r ∨ s)) [22]
≡ (¬(r ∨ s) ∨ q) ∧ (¬q ∨ (r ∨ s)) [22]
≡ ((¬r ∧ ¬s) ∨ q) ∧ (¬q ∨ (r ∨ s)) [17]
5. {1, 3 pt} Prove que ((q ∧ r) ∨ ((¬p→ p)→ p)) ≡ T. Justifique cada passo de
prova com exatamente 1 equac¸a˜o da lista em anexo. A u´nica excec¸a˜o a esta
regra e´ o uso de comutatividade e associatividade. Ou seja, as equac¸o˜es (10),
(11), (12) e (13) podem ser usadas simultaneamente em 1 passo de prova.
Resposta:
(q ∧ r) ∨ ((¬p→ p)→ p)
≡ (q ∧ r) ∨ (¬(¬p→ p) ∨ p) [22]
≡ (q ∧ r) ∨ (¬(¬¬p ∨ p) ∨ p) [22]
≡ (q ∧ r) ∨ (¬(p ∨ p) ∨ p) [9]
≡ (q ∧ r) ∨ (¬p ∨ p) [7]
≡ (q ∧ r) ∨ T [10,20]
≡ T [5]
6. {1, 3 pt} Prove que ((p∧ q)∨ (p∧ r)) ≡ ¬(p→ ¬(q∨ r)) utilizando as equac¸o˜es
em anexo. Justifique cada passo de prova com exatamente 1 equac¸a˜o da lista
em anexo. A u´nica excec¸a˜o a esta regra e´ o uso de comutatividade e asso-
ciatividade. Ou seja, as equac¸o˜es (10), (11), (12) e (13) podem ser usadas
simultaneamente em 1 passo de prova.
Resposta:
(p ∧ q) ∨ (p ∧ r)
≡ p ∧ (q ∨ r) [15]
≡ ¬(¬p) ∧ (q ∨ r) [9]
≡ ¬(¬p) ∧ ¬(¬(q ∨ r)) [9]
≡ ¬((¬p) ∨ (¬(q ∨ r))) [17]
≡ ¬(p→ (¬(q ∨ r))) [22]
Outra resposta poss´ıvel:
¬(p→ ¬(q ∨ r))
≡ p ∧ (q ∨ r) [25]
≡ (p ∧ q) ∨ (p ∧ r) [15]
7. {4, 0 pt} Prove que ¬(p↔ q) ≡ (p↔ ¬q). Na˜o utilize a equac¸a˜o 34.
Justifique cada passo de prova com uma das equac¸o˜es ou regra de infereˆncia
no verso.
Resposta:
¬(p↔ q)
≡ ¬((p→ q) ∧ (q → p)) [31]
≡ ¬((¬p ∨ q) ∧ (¬q ∨ p)) [22,22]
≡ ¬(¬p ∨ q) ∨ ¬(¬q ∨ p) [16]
≡ (¬¬p ∧ ¬q) ∨ (¬¬q ∧ ¬p) [17,17]
≡ (p ∧ ¬q) ∨ (q ∧ ¬p) [9,9]
≡ ((p ∧ ¬q) ∨ q) ∧ ((p ∧ ¬q) ∨ ¬p) [14]
≡ ((p ∨ q) ∧ (q ∨ ¬q)) ∧ ((¬p ∨ p) ∧ (¬p ∨ ¬q)) [10,14]
≡ ((p ∨ q) ∧ T) ∧ (T ∧ (¬p ∨ ¬q)) [10,20]
≡ (p ∨ q) ∧ (¬p ∨ ¬q) [10,3]
≡ (p ∨ ¬¬q) ∧ (¬p ∨ ¬q) [9]
≡ (¬p ∨ ¬q) ∧ (¬¬q ∨ p) [10,10]
≡ (p→ ¬q) ∧ (¬q → p) [22,22]
≡ p↔ ¬q [31]
8. {1, 3 pt} Prove que ((p→ r)∨ (q → r)) ≡ ((p∧ q)→ r) utilizando as equac¸o˜es
em anexo. Na˜o utilize a equac¸a˜o 30. Justifique cada passo de prova com
exatamente 1 equac¸a˜o da lista em anexo. A u´nica excec¸a˜o a esta regra e´ o
uso de comutatividade e associatividade. Ou seja, as equac¸o˜es (10), (11), (12)
e (13) podem ser usadas simultaneamente em 1 passo de prova.
Resposta:
(p→ r) ∨ (q → r)
≡ (¬p ∨ r) ∨ (q → r) [22]
≡ (¬p ∨ r) ∨ (¬q ∨ r) [22]
≡ (¬p ∨ ¬q) ∨ (r ∨ r) [10,12]
≡ (¬p ∨ ¬q) ∨ r [7]
≡ ¬(p ∧ q) ∨ r [16]
≡ (p ∧ q)→ r [22]
9. {1, 3 pt} Prove que ( ( p→ ((q∨¬¬¬q)∧q) ) ∧ (¬p→ q) ) ≡q utilizando as
equac¸o˜es em anexo. Justifique cada passo de prova com exatamente 1 equac¸a˜o
da lista em anexo. A u´nica excec¸a˜o a esta regra e´ o uso de comutatividade e
associatividade. Ou seja, as equac¸o˜es (10), (11), (12) e (13) podem ser usadas
simultaneamente em 1 passo de prova.
Resposta:
( p→ ((q ∨ ¬¬¬q) ∧ q) ) ∧ (¬p→ q)
≡ ( p→ ((q ∨ ¬q) ∧ q) ) ∧ (¬p→ q) [9]
≡ ( p→ (T ∧ q) ) ∧ (¬p→ q) [20]
≡ (p→ q) ∧ (¬p→ q) [10,3]
≡ (p ∨ ¬p)→ q [28]
≡ T→ q [20]
≡ ¬T ∨ q [22]
≡ F ∨ q [2]
≡ q [10,4]
10. {1, 0 pt} Prove utilizando as equac¸o˜es em anexo que:
( ∀x¬∃y( (∃zQ(x, y, z))→ P (x, y) ) ) ≡ ( ∀x∀y( ¬(∀z¬Q(x, y, z)) ∧ ¬P (x, y) ) )
Justifique cada passo de prova com exatamente 1 equac¸a˜o da lista em anexo.
A u´nica excec¸a˜o a esta regra e´ o uso de comutatividade e associatividade. Ou
seja, as equac¸o˜es (10), (11), (12) e (13) podem ser usadas simultaneamente em
1 passo de prova.
Resposta:
∀x¬∃y( (∃zQ(x, y, z))→ P (x, y) )
≡ ∀x∀y¬( (∃zQ(x, y, z))→ P (x, y) ) [35]
≡ ∀x∀y( (∃zQ(x, y, z)) ∧ ¬P (x, y) ) [26]
≡ ∀x∀y( ¬¬(∃zQ(x, y, z)) ∧ ¬P (x, y) ) [9]
≡ ∀x∀y( ¬(∀z¬Q(x, y, z)) ∧ ¬P (x, y) ) [36]
11. {2, 0 pt} Prove utilizando as equac¸o˜es em anexo que:
( ((p→ q) ∧ (q → p))→ (p→ q) ) ≡ T
Justifique cada passo de prova com exatamente 1 equac¸a˜o da lista em anexo.
A u´nica excec¸a˜o a esta regra e´ o uso de comutatividade e associatividade. Ou
seja, as equac¸o˜es (10), (11), (12) e (13) podem ser usadas simultaneamente em
1 passo de prova.
Resposta:
((p→ q) ∧ (q → p))→ (p→ q)
= ((p→ q)→ (p→ q)) ∨ ((q → p)→ (p→ q)) [30]
= (¬(p→ q) ∨ (p→ q)) ∨ ((q → p)→ (p→ q)) [22]
= T ∨ ((q → p)→ (p→ q)) [10,20]
= T [10,5]
12. {1, 3 pt} Prove que
( ((s ∧ s) ∨ ¬q) ∧ (((¬q → ¬q) ∧ ¬q) ∨ s) ) ≡ (q → s)
utilizando as equac¸o˜es em anexo. Justifique cada passo de prova com exata-
mente 1 equac¸a˜o da lista em anexo. A u´nica excec¸a˜o a esta regra e´ o uso de
comutatividade e associatividade. Ou seja, as equac¸o˜es (10), (11), (12) e (13)
podem ser usadas simultaneamente em 1 passo de prova.
Resposta:
((s ∧ s) ∨ ¬q) ∧ (((¬q → ¬q) ∧ ¬q) ∨ s)
≡ (s ∨ ¬q) ∧ (((¬q → ¬q) ∧ ¬q) ∨ s) [8]
≡ (s ∨ ¬q) ∧ (((¬(¬q) ∨ ¬q) ∧ ¬q) ∨ s) [22]
≡ (s ∨ ¬q) ∧ (((q ∨ ¬q) ∧ ¬q) ∨ s) [9]
≡ (s ∨ ¬q) ∧ ((T ∧ ¬q) ∨ s) [20]
≡ (s ∨ ¬q) ∧ (¬q ∨ s) [11,3]
≡ ¬q ∨ s [10,8]
≡ q → s [22]
13. {1, 0 pt} Prove utilizando as equac¸o˜es em anexo que:
( ∀x∃y(¬P (x, y) ∧ ¬Q(x, y)) ) ≡ ( ¬∃x∀y(P (x, y) ∨Q(x, y)) )
Justifique cada passo de prova com exatamente 1 equac¸a˜o da lista em anexo.
A u´nica excec¸a˜o a esta regra e´ o uso de comutatividade e associatividade. Ou
seja, as equac¸o˜es (10), (11), (12) e (13) podem ser usadas simultaneamente em
1 passo de prova.
Resposta:
∀x∃y(¬P (x, y) ∧ ¬Q(x, y))
≡ ∀x∃y¬(P (x, y) ∨Q(x, y)) [17]
≡ ∀x¬∀y(P (x, y) ∨Q(x, y)) [36]
≡ ¬∃x∀y(P (x, y) ∨Q(x, y)) [35]
14. {2, 0 pt} Prove utilizando as equac¸o˜es em anexo que:
( ¬(¬p ∧ q) ∧ ¬(¬q ∧ p) ) ≡ (p↔ q)
Justifique cada passo de prova com exatamente 1 equac¸a˜o da lista em anexo.
A u´nica excec¸a˜o a esta regra e´ o uso de comutatividade e associatividade. Ou
seja, as equac¸o˜es (10), (11), (12) e (13) podem ser usadas simultaneamente em
1 passo de prova.
Resposta:
¬(¬p ∧ q) ∧ ¬(¬q ∧ p)
(¬¬p ∨ ¬q) ∧ ¬(¬q ∧ p) [16]
(¬¬p ∨ ¬q) ∧ (¬¬q ∨ ¬p) [16]
(p ∨ ¬q) ∧ (¬¬q ∨ ¬p) [9]
(p ∨ ¬q) ∧ (q ∨ ¬p) [9]
(q → p) ∧ (q ∨ ¬p) [10,22]
(q → p) ∧ (p→ q) [10,22]
p↔ q [11,31]
15. {1, 0 pt} Prove que
( ((p ∧ ¬q) ∧ (r ∨ ¬(¬p ∨ q)))→ (p ∧ ¬q) ) ≡ T
utilizando as equac¸o˜es em anexo. Justifique cada passo de prova com exata-
mente 1 equac¸a˜o da lista em anexo. A u´nica excec¸a˜o a esta regra e´ o uso de
comutatividade e associatividade. Ou seja, as equac¸o˜es (10), (11), (12) e (13)
podem ser usadas simultaneamente em 1 passo de prova.
Resposta:
(p ∧ ¬q) ∧ (r ∨ ¬(¬p ∨ q))→ (p ∧ ¬q)
≡ (p ∧ ¬q) ∧ (r ∨ (¬(¬p) ∧ ¬q)))→ (p ∧ ¬q) [17]
≡ (p ∧ ¬q) ∧ (r ∨ (p ∧ ¬q))→ (p ∧ ¬q) [9]
≡ (p ∧ ¬q) ∧ ((p ∧ ¬q) ∨ r)→ (p ∧ ¬q) [10]
≡ (p ∧ ¬q)→ (p ∧ ¬q) [19]
≡ ¬(p ∧ ¬q) ∨ (p ∧ ¬q) [22]
≡ T [10,20]
16. {1, 0 pt} Sejam as premissas
∃z(¬R(z) ∨ ¬S(z)),
(¬∃x¬(P (x))) ∨ (∀z(R(z) ∧ S(z))) e
(∀x(P (x)))→ (∃y(Q(y))).
Conclua, usando as equac¸o˜es em anexo, que ∃y(Q(y)). Justifique cada passo
de prova com exatamente 1 equac¸a˜o da lista em anexo. A u´nica excec¸a˜o a
esta regra e´ o uso de comutatividade e associatividade. Ou seja, as equac¸o˜es
(10), (11), (12) e (13) podem ser usadas simultaneamente em 1 passo de prova.
Resposta:
1. ∃z(¬R(z) ∨ ¬S(z)) [Premissa]
2. ∃z¬(R(z) ∧ S(z)) [16 em 1]
3. ¬∀z(R(z) ∧ S(z)) [36 em 1]
4. (¬∃x¬(P (x))) ∨ (∀z(R(z) ∧ S(z))) [Premissa]
5. (¬∃x¬(P (x))) [40 em 3 e 4]
6. ∀x¬¬(P (x)) [35 em 5]
7. ∀x(P (x)) [9 em 6]
8. (∀x(P (x)))→ (∃y(Q(y))) [Premissa]
9. ∃y(Q(y)) [37 em 7 e 8]
17. {1, 0 pt} Prove que
∀x∀z( ¬P (x, z) ∧ (∃k∀y(Q(x, z, k, y) ∧ ¬R(x, z, k, y))) )
≡ ¬∃x∃z( P (x, z) ∨ (∀k∃y(¬Q(x, z, k, y) ∨R(x, z, k, y))) )
utilizando as equac¸o˜es em anexo. Justifique cada passo de prova com exata-
mente 1 equac¸a˜o da lista em anexo. A u´nica excec¸a˜o a esta regra e´ o uso de
comutatividade e associatividade. Ou seja, as equac¸o˜es (10), (11), (12) e (13)
podem ser usadas simultaneamente em 1 passo de prova.
Resposta:
∀x∀z( ¬P (x, z) ∧ (∃k∀y(Q(x, z, k, y) ∧ ¬R(x, z, k, y))) )
≡ ∀x∀z( ¬P (x, z) ∧ (∃k∀y(¬¬Q(x, z, k, y) ∧ ¬R(x, z, k, y))) ) [9]
≡ ∀x∀z( ¬P (x, z) ∧ (∃k∀y¬(¬Q(x, z, k, y) ∨R(x, z, k, y))) ) [17]
≡ ∀x∀z( ¬P (x, z) ∧ (∃k¬∃y(¬Q(x, z, k, y) ∨R(x, z, k, y))) ) [35]
≡ ∀x∀z( ¬P (x, z) ∧ (¬∀k∃y(¬Q(x, z, k, y) ∨R(x, z, k, y))) ) [36]
≡ ∀x∀z¬( P (x, z) ∨ (∀k∃y(¬Q(x, z, k, y) ∨R(x, z, k, y))) ) [17]
≡ ∀x¬∃z( P (x, z) ∨ (∀k∃y(¬Q(x, z, k, y) ∨R(x, z, k, y))) ) [35]
≡ ¬∃x∃z( P (x, z) ∨ (∀k∃y(¬Q(x, z, k, y) ∨R(x, z, k, y))) ) [35]
18. {1, 0 pt} Prove que
p ∧ ((¬¬¬¬p ∨ p) ∨ (r → s)) ≡ p
utilizando as equac¸o˜es em anexo. Justifique cada passo de prova com exata-
mente 1 equac¸a˜o da lista em anexo. A u´nica excec¸a˜o a esta regra e´ o uso de
comutatividade e associatividade. Ou seja, as equac¸o˜es (10), (11), (12) e (13)
podem ser usadas simultaneamente em 1 passo de prova.
Resposta:
p ∧ ((¬¬¬¬p ∨ p) ∨ (r → s))
≡ p ∧ ((¬¬p ∨ p) ∨ (r → s)) [9]
≡ p ∧ ((p ∨ p) ∨ (r → s)) [9]
≡ p ∧ (p ∨ (r → s)) [7]
≡ p [19]
Lembre-se: ¬¬¬¬p ∨ p significa (¬¬¬¬p) ∨ p.
19. {1, 0 pt} Sejam as premissas
( ∀x(Q(x)→ R(x)) )→ ( ∃y∀k(S(y, k) ∧ P (y, k)) ) e
∀y∃k(¬S(y, k) ∨ ¬P (y, k)).
Conclua, usando as equac¸o˜es em anexo, que ∃x(Q(x) ∧ ¬R(x)).
Justifique cada passo de prova com exatamente 1 equac¸a˜o da lista em anexo.
A u´nica excec¸a˜o a esta regra e´ o uso de comutatividade e associatividade. Ou
seja, as equac¸o˜es (10), (11), (12) e (13) podem ser usadas simultaneamente em
1 passo de prova.
Resposta:
1. ∀y∃k(¬S(y, k) ∨ ¬P (y, k)) [Premissa]
2. ∀y∃k¬(S(y, k) ∧ P (y, k)) [16 em 1]
3. ∀y¬∀k(S(y, k) ∧ P (y, k)) [36 em 2]
4. ¬∃y∀k(S(y, k) ∧ P (y, k)) [35 em 3]
5. ( ∀x(Q(x)→ R(x)) )→ ( ∃y∀k(S(y, k) ∧ P (y, k)) ) [Premissa]
6. ¬∀x(Q(x)→ R(x)) [38 em 4 e 5]
7. ∃x¬(Q(x)→ R(x)) [36 em 6]
8. ∃x(Q(x) ∧ ¬R(x)) [26 em 7]
20. {1, 0 pt} Prove que
( ∀x∃k(Q(x, k) ∨R(x, k)) ) ∨ ( ∃z∀w(¬R(z, w) ∧ S(z, w)) )
≡ ¬( ( ∃x∀k¬(Q(x, k) ∨R(x, k)) ) ∧ ( ∀z∃w(R(z, w) ∨ ¬S(z, w)) ) )
Justifique cada passo de prova com exatamente 1 equac¸a˜o da lista em anexo.
A u´nica excec¸a˜o a esta regra e´ o uso de comutatividade e associatividade. Ou
seja, as equac¸o˜es (10), (11), (12) e (13) podem ser usadas simultaneamente em
1 passo de prova.
Resposta:
( ∀x∃k(Q(x, k) ∨R(x, k)) ) ∨ ( ∃z∀w(¬R(z, w) ∧ S(z, w)) )
≡ ( ∀x∃k¬¬(Q(x, k) ∨R(x, k)) ) ∨ ( ∃z∀w(¬R(z, w) ∧ S(z, w)) ) [9]
≡ ( ∀x¬∀k¬(Q(x, k) ∨R(x, k)) ) ∨ ( ∃z∀w(¬R(z, w) ∧ S(z, w)) ) [36]
≡ ( ¬∃x∀k¬(Q(x, k) ∨R(x, k)) ) ∨ ( ∃z∀w(¬R(z, w) ∧ S(z, w)) ) [35]
≡ ( ¬∃x∀k¬(Q(x, k) ∨R(x, k)) ) ∨ ( ∃z∀w(¬R(z, w) ∧ ¬¬S(z, w)) ) [9]
≡ ( ¬∃x∀k¬(Q(x, k) ∨R(x, k)) ) ∨ ( ∃z∀w¬(R(z, w) ∨ ¬S(z, w)) ) [17]
≡ ( ¬∃x∀k¬(Q(x, k) ∨R(x, k)) ) ∨ ( ∃z¬∃w(R(z, w) ∨ ¬S(z, w)) ) [35]
≡ ( ¬∃x∀k¬(Q(x, k) ∨R(x, k)) ) ∨ ( ¬∀z∃w(R(z, w) ∨ ¬S(z, w)) ) [36]
≡ ¬( ( ∃x∀k¬(Q(x, k) ∨R(x, k)) ) ∧ ( ∀z∃w(R(z, w) ∨ ¬S(z, w)) ) ) [36]
1.3 Lo´gica Proposicional - Prova de Premissa-Conclusa˜o
1. {1, 0 pt} Sejamp = eu tomo a vacina H1N1
q = eu passo mal
r = eu morro
s = eu assisto a` aula
Se eu tomo a vacina H1N1, enta˜o eu passo mal e na˜o morro. Se eu na˜o tomo a
vacina H1N1, enta˜o eu morro ou na˜o passo mal (ou ambos). Se eu passo mal,
enta˜o eu na˜o assisto a` aula. Eu assisti a` aula.
Dadas as premissas acima, prove que eu na˜o tomei a vacina H1N1.
Resposta:
1. p→ (q ∧ ¬r) [Premissa]
2. ¬p→ (r ∨ ¬q) [Premissa]
3. q → (¬s) [Premissa]
4. s [Premissa]
5. ¬¬s [9 em (4)]
6. ¬q [38 em (3) e (5)]
7. ¬q ∨ ¬¬r [41 em (6)]
8. ¬(q ∧ ¬r) [16 em (7)]
9. ¬p [38 em (1) e (7)]
2. {1 pt} Dadas as 3 premissas p → q, p e ¬q. Conclua que (1 > 2). Justifique
cada passo de prova com uma das equac¸o˜es ou regra de infereˆncia em anexo.
Resposta:
1. p→ q [Premissa]
2. ¬q [Premissa]
3. ¬p [38 em (1) e (2)]
4. p [Premissa]
5. p ∧ ¬p [43 em (3) e (4)]
6. F [21 em (5)]
7. (1 > 2) ∨ F [41 em (6)]
8. (1 > 2) [4]
3. {1, 0 pt} Dada a premissa ¬(p → p), prove que (q ∨ r). Justifique cada passo
de prova com uma equac¸a˜o ou regra de infereˆncia em anexo. A u´nica excec¸a˜o
a esta regra e´ o uso de comutatividade e associatividade. Ou seja, as equac¸o˜es
(10), (11), (12) e (13) podem ser usadas simultaneamente em 1 passo de prova.
Resposta:
1. ¬(p→ p) [Premissa]
2. p ∧ (¬p) [26 em (1)]
3. p [42 em (2)]
4. ¬p [42 em (2)]
5. p ∨ q [41 em (3)]
6. ¬p ∨ r [41 em (4)]
7. q ∨ r [45 em (6) e (7)]
4. {1, 0 pt} Dadas as premissas ((t∧ u)→ (¬s)), (¬(t∧ u)→ (q ∧ p)), (¬q ∨¬p)
e s. Prove que F (falso). Justifique cada passo de prova com uma equac¸a˜o
ou regra de infereˆncia em anexo. A u´nica excec¸a˜o a esta regra e´ o uso de
comutatividade e associatividade. Ou seja, as equac¸o˜es (10), (11), (12) e (13)
podem ser usadas simultaneamente em 1 passo de prova.
Resposta:
1. ¬(t ∧ u)→ (q ∧ p) [Premissa]
2. ¬q ∨ ¬p [Premissa]
3. ¬(q ∧ p) [16 em (2)]
4. ¬¬(t ∧ u) [38 em (1) e (3)]
5. t ∧ u [9 em (4)]
6. (t ∧ u)→ (¬s) [Premissa]
7. ¬s [37 em (5) e (6)]
8. s [Premissa]
9. s ∧ ¬s [43 em (7) e (8)]
10. F [21 em (9)]
5. {1, 0 pt} Dadas as premissas (p→ ¬q), q, (¬(p∨t)→ s) e (¬t), prove s usando
as equac¸o˜es em anexo.
Resposta:
1. p→ ¬q [Premissa]
2. q [Premissa]
3. ¬(p ∨ t)→ s [Premissa]
4. ¬t [Premissa]
5. ¬¬q [9 em 2]
6. ¬p [38 em 1 e 5]
7. ¬p ∧ ¬t [43 em 4 e 6]
8. ¬(p ∨ t) [17 em 7]
9. s [37 em 3 e 8]
6. {2, 0 pt} Dadas as premissas ((t → s) → (q ∧ r)) e ¬t, prove r usando as
equac¸o˜es em anexo.
Resposta:
1. ¬t [Premissa]
2. ¬t ∨ s [41 em 1]
3. t→ s [22 em 2]
4. (t→ s)→ (q ∧ s) [Premissa]
5. q ∧ s [37 em 3 e 4]
6. s [42 em 5]
7. {1, 0 pt} Dadas as premissas ¬(p → q) ∨ (r ∧ s) e ¬((r ∧ s) ∧ ¬t), prove que
((p→ q)→ t) usando as equac¸o˜es em anexo.
Resposta:
1. ¬(p→ q) ∨ (r ∧ s) [Premissa]
2. ¬((r ∧ s) ∧ ¬t) [Premissa]
3. (p→ q)→ (r ∧ s) [22 em 1]
4. ¬(¬((r ∧ s)→ t)) [26 em 2]
5. (r ∧ s)→ t [9 em 4]
6. (p→ q)→ t [39 em 3 e 5]
8. {2, 0 pt} Dadas as premissas ((k ∨ s) → (p ∨ q)), ¬q e k, prove que (p ∨ t)
usando as equac¸o˜es em anexo.
Resposta:
1. k [Premissa]
2. k ∨ s [41 em 1]
3. (k ∨ s)→ (p ∨ q) [Premissa]
4. p ∨ q [37 em 2 e 3]
5. ¬q [Premissa]
6. p [40 em 4 e 5]
7. p ∨ t [41 em 6]
2 Estruturas Ba´sicas: Conjuntos, Func¸o˜es, Sequeˆncias
e Somato´rios
2.1 Conjuntos
1. Seja A4 B a diferenc¸a sime´trica dada por
A4 B = (A ∪ B)− (A ∩ B).
Prove as equac¸o˜es abaixo. Cada passo da prova deve ser justificada com a
“Definic¸a˜o de 4” ou pelas equac¸o˜es em anexo.
a) {0, 4 pt} A4 A = ∅
Resposta:
A4 A
= (A ∪ A)− (A ∩ A) [Def. 4]
= A− (A ∩ A) [70]
= A− A [71]
= {x | x ∈ A ∧ x /∈ A} [62]
= {x | x ∈ A ∧ x ∈ A} [65]
= {x | x ∈ A ∩ A} [60]
= {x | x ∈ ∅} [84]
= ∅ [47]
b) {0, 4 pt} A4 B = B 4 A
Resposta:
A4 B
= (A ∪ B)− (A ∩ B) [Def. 4]
= (B ∪ A)− (A ∩ B) [73]
= (B ∪ A)− (B ∩ A) [74]
= B 4 A [Def. 4]
c) {0, 4 pt} A4 U = A, onde U e´ o conjunto universo.
Resposta:
A4 U
= (A ∪ U)− (A ∩ U) [Def. 4]
= U − (A ∩ U) [68]
= U − A [67]
= {x | x ∈ U ∧ x /∈ A} [62]
= {x | x ∈ U ∧ x ∈ A} [65]
= {x | x ∈ U ∩ A} [60]
= {x | x ∈ A ∩ U} [74]
= {x | x ∈ A} [67]
= A [47]
2. {2,5 pt} Prove que
( ((A ∩ B) ∪ (A ∩ C)) ∩ U ) ∪ (C ∪ E) = (C ∩ E) ∪ (A ∩ (B ∪ C)),
onde U e´ o conjunto universo.
Resposta:
( ((A ∩ B) ∪ (A ∩ C)) ∩ U ) ∪ (C ∪ E)
= ( (A ∩ (B ∪ C)) ∩ U ) ∪ (C ∪ E) [77]
= ( A ∩ (B ∪ C) ) ∪ (C ∪ E) [67]
= ( A ∩ (B ∪ C) ) ∪ (C ∩ E) [79]
= ( A ∩ (B ∪ C) ) ∪ (C ∩ E) [72]
= (C ∩ E) ∪ ( A ∩ (B ∪ C) ) [73]
3. {3, 5 pt} Prove que A ∪ (B ∪ C) = (A ∪ B) ∪ C sem utilizar a equac¸a˜o 76.
Ou seja, cada passo de prova deve ser justificado por uma equac¸a˜o da pa´gina
seguinte exceto a equac¸a˜o 76.
Resposta:
A ∪ (B ∪ C)
= {x | x ∈ A ∨ (x ∈ (B ∪ C))} [57]
= {x | x ∈ A ∨ (x ∈ B ∨ x ∈ C)} [58]
= {x | (x ∈ A ∨ x ∈ B) ∨ x ∈ C} [12]
= {x | x ∈ (A ∪B) ∨ x ∈ C} [58]
= {x | x ∈ (A ∪B) ∪ C} [58]
= (A ∪B) ∪ C [47]
4. {1.0 pt} Prove que (x ∈ U) ≡ T, onde U e´ o conjunto universo.
Resposta:
x ∈ U
≡ x ∈ (A ∪ A) [83]
≡ x ∈ A ∨ x ∈ A [58]
≡ x ∈ A ∨ x /∈ A [65]
≡ x ∈ A ∨ ¬(x ∈ A) [46]
≡ T [20]
5. {1, 0 pt} Prove que ((A− C) ∩ (C − B)) = ∅
Resposta:
(A− C) ∩ (C − B)
= {x | x ∈ (A− C) ∧ x ∈ (C −B)} [59]
= {x | (x ∈ A ∧ x /∈ C) ∧ (x ∈ (C − B)} [63]
= {x | (x ∈ A ∧ x /∈ C) ∧ (x ∈ C ∧ x /∈ B)} [63]
= {x | (x ∈ A ∧ x /∈ B) ∧ (x ∈ C ∧ x /∈ C)} [11,13]
= {x | (x ∈ A ∧ x /∈ B) ∧ (x ∈ C ∧ ¬(x ∈ C))} [46]
= {x | (x ∈ A ∧ x /∈ B) ∧ F} [21]
= {x | F} [6]
= ∅ [53]
6. Sejam as equac¸o˜es
P (x) = x /∈ x (85)
S = {x | P (x)} (86)
Prove o Paradoxo de Russell utilizando as equac¸o˜es de 1 a 86. Justifique cada
passo de prova com exatamente 1 equac¸a˜o da lista em anexo. A u´nica excec¸a˜o
a esta regra e´ o uso de comutatividade e associatividade. Ou seja, as equac¸o˜es
(10), (11), (12), (13), (73), (74), (75) e (76) podem ser usadas simultaneamente
em 1 passo de prova.
a) {1, 5 pt} Dada a premissa S ∈ S, conclu´ımos F.
Resposta:
1. S ∈ S [Premissa]
2. S ∈ {x | P (x)} [86]
3. P (S) [48]
4. S /∈ S [85]
5. ¬(S ∈ S) [46]
6. (S ∈ S) ∧ ¬(S ∈ S) [43 em (1) e (5)]
7. F [21]
b) {1, 5 pt} Dada a premissa S /∈ S, conclu´ımos F.
Resposta:
1. S /∈ S [Premissa]
2. ¬(S ∈ S) [46]
3. ¬(S ∈ {x | P (x)}) [86]
4. ¬(P (S)) [48]
5. ¬(S /∈ S) [85]
6. ¬(¬(S ∈ S)) [46]
7. S ∈ S [9]
8. (S ∈ S) ∧ ¬(S ∈ S) [43 em (2) e (7)]
9. F [21]
7. {4, 0 pt} Prove que (A − B) ∩ (B − A) = ∅. Justifique cada passo de prova
com exatamente 1 das equac¸o˜es do verso. A u´nica excec¸a˜o a esta regra e´ o
uso das equac¸o˜es (10), (11), (12), (13), (73), (74), (75) e (76) que podem ser
usadas simultaneamente em 1 passo de prova.
Resposta:
(A− B) ∩ (B − A)
= {x | x ∈ (A−B) ∧ x ∈ (B − A)} [59]
= {x | (x ∈ A ∧ x /∈ B) ∧ x ∈ (B − A)} [63]
= {x | (x ∈ A ∧ x /∈ B) ∧ (x ∈ B ∧ x /∈ A)} [63]
= {x | (x ∈ A ∧ x /∈ A) ∧ (x ∈ B ∧ x /∈ B)} [11,13]
= {x | (x ∈ A ∧ ¬(x ∈ A)) ∧ (x ∈ B ∧ x /∈ B)} [46]
= {x | (x ∈ A ∧ ¬(x ∈ A)) ∧ (x ∈ B ∧ ¬(x ∈ B)} [46]
= {x | F ∧ (x ∈ B ∧ ¬(x ∈ B))} [21]
= {x | F ∧ F} [21]
= {x | F} [6]
∅ [53]
8. {1, 0 pt} Prove que (A ∪ (B − A)) = (A ∪ B). Justifique cada passo de prova
com uma equac¸a˜o ou regra de infereˆncia em anexo. A u´nica excec¸a˜o a esta
regra e´ o uso de comutatividade e associatividade. Ou seja, as equac¸o˜es (10),
(11), (12), (13), (73), (74), (75) e (76) podem ser usadas simultaneamente em
1 passo de prova.
Resposta:
A ∪ (B − A)
= {x | (x ∈ A) ∨ (x ∈ (B − A))} [57]
= {x | (x ∈ A) ∨ ((x ∈ B) ∧ (x /∈ A))} [62]
= {x | ((x ∈ A) ∨ (x ∈ B)) ∧ ((x ∈ A) ∨ (x /∈ A))} [14]
= {x | ((x ∈ A) ∨ (x ∈ B)) ∧ ((x ∈ A) ∨ ¬(x ∈ A))} [46]
= {x | ((x ∈ A) ∨ (x ∈ B)) ∧ T} [20]
= {x | (x ∈ A) ∨ (x ∈ B)} [3]
= A ∪B [57]
9. {2, 25 pt} Prove que ((A − B) − A) = ∅. Justifique cada passo de prova com
uma equac¸a˜o ou regra de infereˆncia em anexo. A u´nica excec¸a˜o a esta regra
e´ o uso de comutatividade e associatividade. Ou seja, as equac¸o˜es (10), (11),
(12) e (13) podem ser usadas simultaneamente em 1 passo de prova.
Resposta:
(A−B)− A
= {x | (x ∈ (A− B)) ∧ x /∈ A} [62]
= {x | (x ∈ A ∧ x /∈ B) ∧ x /∈ A} [63]
= {x | (x /∈ B) ∧ (x ∈ A ∧ x /∈ A)} [11,13]
= {x | (x /∈ B) ∧ (x ∈ A ∧ ¬(x ∈ A)} [46]
= {x | (x /∈ B) ∧ F} [21]
= {x | F} [6]
= ∅ [53]
10. {2, 25 pt} Dadas as premissas (x ∈ B), (¬(x ∈ B) → (x ∈ D)),((x ∈ D) →
((x ∈ A)∧ (x ∈ C))), conclua que x ∈ (A∪E). Justifique cada passo de prova
com uma equac¸a˜o ou regra de infereˆncia em anexo. A u´nica excec¸a˜o a esta
regra e´ o uso de comutatividade e associatividade. Ou seja, as equac¸o˜es (10),
(11), (12), (13), (73), (74), (75) e (76) podem ser usadas simultaneamente em
1 passo de prova.
Resposta:
1. x ∈ B [Premissa]
2. x /∈ B [65 em (1)]
3. ¬(x ∈ B) [46 em (2)]
4. ¬(x ∈ B)→ (x ∈ D) [Premissa]
5. (x ∈ D)→ ((x ∈ A) ∧ (x ∈ C)) [Premissa]
6. ¬(x ∈ B)→ ((x ∈ A) ∧ (x ∈ C)) [39 em (4) e (5)]
7. (x ∈ A) ∧ (x ∈ C) [37 em (3) e (6)]
8. (x ∈ A) [42 em (7)]
9. (x ∈ A) ∨ (x ∈ E) [41 em (8)]
10. x ∈ (A ∪ E) [58 em (9)]
11. {1, 0 pt} Prove que ((A ∪ B) ∩ A) = (B − A). Justifique cada passo de prova
com uma equac¸a˜o ou regra de infereˆncia em anexo. A u´nica excec¸a˜o a esta
regra e´ o uso de comutatividade e associatividade. Ou seja, as equac¸o˜es (10),
(11), (12), (13), (73), (74), (75) e (76) podem ser usadas simultaneamente em
1 passo de prova.
Resposta:
(A ∪ B) ∩ A
= {x | (x ∈ (A ∪ B)) ∧ (x ∈ A)} [59]
= {x | ((x ∈ A) ∨ (x ∈ B)) ∧ (x ∈ A)} [57]
= {x | ((x ∈ A ∨ (x ∈ B)) ∧ (x /∈ A)} [65]
= {x | ((x ∈ A ∨ (x ∈ B)) ∧ ¬(x ∈ A)} [46]
= {x | (¬(x ∈ A) ∧ (x ∈ A)) ∨ (¬(x ∈ A) ∧ (x ∈ B))} [11,15]
= {x | F ∨ (¬(x ∈ A) ∧ (x ∈ B))} [11,21]
= {x | ¬(x ∈ A) ∧ (x ∈ B)} [11,4]
= B − A [11,64]
12. {2, 25 pt} Prove que A ∩ A = {x | T}. Justifique cada passo de prova com
uma equac¸a˜o ou regra de infereˆncia em anexo. A u´nica excec¸a˜o a esta regra
e´ o uso de comutatividade e associatividade. Ou seja, as equac¸o˜es (10), (11),
(12) e (13) podem ser usadas simultaneamente em 1 passo de prova.
Resposta:
A ∩ A
= {x | x /∈ (A ∩ A)} [64]
= {x | ¬(x ∈ (A ∩ A))} [46]
= {x | ¬(x ∈ A ∧ x ∈ A)} [60]
= {x | ¬(x ∈ A ∧ x /∈ A)} [65]
= {x | ¬(x ∈ A ∧ ¬(x ∈ A))} [46]
= {x | ¬(F)} [21]
= {x | T} [1]
13. {2, 25 pt} Dada a premissa x /∈ A, conclua que x /∈ (A ∩ B). Justifique cada
passo de prova com uma equac¸a˜o ou regra de infereˆncia em anexo. A u´nica
excec¸a˜o a esta regra e´ o uso de comutatividade e associatividade. Ou seja,
as equac¸o˜es (10), (11), (12), (13), (73), (74), (75) e (76) podem ser usadas
simultaneamente em 1 passo de prova.
Resposta:
1. x /∈ A [Premissa]
2. ¬(x ∈ A) [46 em (1)]
3. ¬(x ∈ A) ∨ ¬(x ∈ B) [41 em (2)]
4. ¬((x ∈ A) ∧ (x ∈ B)) [17 em (3)]
5. ¬(x ∈ (A ∩ B)) [60 em (4)]
6. x /∈ (A ∩B) [46 em (5)]
14. {4, 0 pt} Prove que (A − (B ∪ C)) = ((A − B) ∩ (A − C)). Justifique
cada passo de prova com uma das equac¸o˜es ou regra de infereˆncia no verso.
Somente as equac¸o˜es (10), (11), (12), (13), (73), (74), (75) e (76) podem ser
usadas simultaneamente em 1 passo de prova.
Resposta:
A− (B ∪ C)
= {x | (x ∈ A) ∧ (x /∈ (B ∪ C))} [62]
= {x | (x ∈ A) ∧ ¬(x ∈ (B ∪ C))} [46]
= {x | (x ∈ A) ∧ ¬((x ∈ B) ∨ (x ∈ C))} [58]
= {x | (x ∈ A) ∧ (¬(x ∈ B) ∧ ¬(x ∈ C))} [17]
= {x | (x ∈ A) ∧ ((x /∈ B) ∧ ¬(x ∈ C))} [46]
= {x | (x ∈ A) ∧ ((x /∈ B) ∧ (x /∈ C))} [46]
= {x | ((x ∈ A) ∧ (x ∈ A)) ∧ ((x /∈ B) ∧ (x /∈ C))} [8]
= {x | ((x ∈ A) ∧ (x /∈ B)) ∧ ((x ∈ A) ∧ (x /∈ C))} [11,13]
= {x | (x ∈ (A−B)) ∧ ((x ∈ A) ∧ (x /∈ C))} [63]
= {x | (x ∈ (A−B)) ∧ (x ∈ (A− C))} [63]
= (A−B) ∩ (A− C) [59]
15. {2, 0 pt} Prove utilizando as equac¸o˜es em anexo que:
∅ = {x | T}
Justifique cada passo de prova com exatamente 1 equac¸a˜o da lista em anexo.
A u´nica excec¸a˜o a esta regra e´ o uso de comutatividade e associatividade.
Ou seja, as equac¸o˜es (10), (11), (12), (13), (73), (74), (75) e (76) podem ser
usadas simultaneamente em 1 passo de prova.
Resposta:
∅
= {x | x /∈ ∅} [64]
= {x | ¬(x ∈ ∅)} [46]
= {x | ¬F} [54]
= {x | T} [1]
16. {4, 0 pt} Sejam as premissas (x ∈ (A ∩ B)) e ( (x ∈ (B ∪ C)) → (x ∈ D) ).
Conclua que x ∈ (D ∪ A).
Justifique cada passo de prova com uma das equac¸o˜es ou regra de infereˆncia
no verso. A u´nica excec¸a˜o a esta regra e´ o uso de comutatividade e associa-
tividade. Ou seja, as equac¸o˜es (10), (11), (12), (13), (73), (74), (75) e (76)
podem ser usadas simultaneamente em 1 passo de prova.
Resposta:
1. x ∈ (A ∩ B) [Premissa]
2. (x ∈ A) ∧ (x ∈ B) [60 em (1)]
3. x ∈ B [42 em (2)]
4. (x ∈ B) ∨ (x ∈ C) [41 em (3)]
5. x ∈ (B ∪ C) [58 em (4)]
6. (x ∈ (B ∪ C))→ (x ∈ D) [Premissa]
7. x ∈ D [37 em (5) e (6)]
8. (x ∈ D) ∨ (x ∈ A) [41 em (7)]
9. x ∈ (D ∪ A) [58 em (8)]
17. {2, 0 pt} Prove utilizando as equac¸o˜es em anexo que:
(A ∩ A) ∪ (B ∩ (C ∩ C)) = A
Justifique cada passo de prova com exatamente 1 equac¸a˜o da lista em anexo.
A u´nica excec¸a˜o a esta regra e´ o uso de comutatividade e associatividade.
Ou seja, as equac¸o˜es (10), (11), (12), (13), (73), (74), (75) e (76) podem ser
usadas simultaneamente em 1 passo de prova.
Resposta:
(A ∩ A) ∪ (B ∩ (C ∩ C))
= A ∪ (B ∩ (C ∩ C)) [71]
= A ∪ (B ∩ (C ∩ C)) [72]
= A ∪ (B ∩ ∅) [84]
= A ∪ ∅ [69]
= A [66]
18. {3, 0 pt} Prove que (x ∈ (A ∩ B) ∩ C) ≡ (x ∈ B ∩ (C ∩ A)). Justifique cada
passo de prova com uma das equac¸o˜es ou regra de infereˆncia no verso. A u´nica
excec¸a˜o a esta regra e´ o uso de comutatividade e associatividade. Ou seja, as
equac¸o˜es (10), (11), (12), (13), (73) e (75) podem ser usadas simultaneamente
em 1 passo de prova. Na˜o utilize as equac¸o˜es 74 e 76 em nenhum passo
(seja simultaneamente ou na˜o).
Resposta:
x ∈ (A ∩B) ∩ C
≡ x ∈ (A ∩ B) ∧ x ∈ C [60]
≡ (x ∈ A ∧ x ∈ B) ∧ x ∈ C [60]
≡ x ∈ B ∧ (x ∈ C ∧ x ∈ A) [11,13]
≡ x ∈ B ∧ x ∈ (C ∩ A) [60]
≡ x ∈ B ∩ (C ∩ A) [60]
19. {2, 0 pt} Sejam as premissas (¬(x ∈ ∅) → x ∈ (A ∩ B) ∩ C) e ((x ∈ A ∧ x ∈
B)→ x ∈ (D ∩ E)). Conclua, usando as equac¸o˜es em anexo, que x ∈ E.
Justifique cada passo de prova com exatamente 1 equac¸a˜o da lista em anexo.
A u´nica excec¸a˜o a esta regra e´ o uso de comutatividade e associatividade. Ou
seja, as equac¸o˜es (10), (11), (12) e (13) podem ser usadas simultaneamente em
1 passo de prova.
Resposta:
1. ¬(x ∈ ∅)→ x ∈ (A ∩ B) ∩ C [Premissa]
2. ¬F→ x ∈ (A ∩ B) ∩ C [54 em 1]
3. ¬¬F ∨ x ∈ (A ∩ B) ∩ C [22 em 2]
4. F ∨ x ∈ (A ∩ B) ∩ C [9 em 3]
5. x ∈ (A ∩ B) ∩ C [10,4 em 4]
6. x ∈ (A ∩ B) ∧ x ∈ C [60 em 5]
7. x ∈ (A ∩ B) [42 em 6]
8. x ∈ A ∧ x ∈ B [60 em 7]
9. (x ∈ A ∧ x ∈ B)→ x ∈ (D ∩ E) [Premissa]
10. x ∈ (D ∩ E) [37 em 8 e 9]
11. x ∈ D ∧ x ∈ E [60 em 10]
12. x ∈ E [42 em 11]
20. {2, 0 pt} Prove que A ∪ (B ∩ (C ∩ ∅)) = U , onde U e´ o conjunto universo.
Justifique cada passo de prova com exatamente 1 equac¸a˜o da lista em anexo.
A u´nica excec¸a˜o a esta regra e´ o uso de comutatividade e associatividade.
Ou seja, as equac¸o˜es (10), (11), (12), (13), (73), (74), (75) e (76) podem ser
usadas simultaneamente em 1 passo de prova.
Resposta:
A ∪ (B ∩ (C ∩ ∅))
= A ∪ (B ∩ ∅) [69]
= A ∪ ∅ [69]
= {x | x ∈ A ∨ x ∈ ∅} [57]
= {x | x ∈ A ∨ x /∈ ∅} [65]
= {x | x ∈ A ∨ ¬(x ∈ ∅)} [46]
= {x | x ∈ A ∨ ¬F} [54]
= {x | x ∈ A ∨ T} [1]
= {x | T} [5]
= {x | x ∈ A ∨ ¬(x ∈ A)} [20]
= {x | x ∈ A ∨ x /∈ A} [46]
= {x | x ∈ A ∨ x ∈ A} [65]
= A ∪ A [57]
= U [83]
21. {2, 0 pt} Prove que ∅ = ∅ sem utilizar a equac¸a˜o 72.
Justifique cada passo de prova com exatamente 1 equac¸a˜o da lista em anexo.
A u´nica excec¸a˜o a esta regra e´ o uso de comutatividade e associatividade.
Ou seja, as equac¸o˜es (10), (11), (12), (13), (73), (74), (75) e (76) podem ser
usadas simultaneamente em 1 passo de prova.
Resposta:
∅
= {x | x /∈ ∅} [64]
= {x | ¬(x ∈ ∅)} [46]
= {x | ¬(x /∈ ∅)} [65]
= {x | ¬¬(x ∈ ∅)} [46]
= {x | x ∈ ∅} [9]
= ∅ [47]
22. {2, 0 pt} Sejam as premissas ( (x /∈ A) → ¬(x ∈ (B − C)) ) e
( (x ∈ (A ∩ ∅)) ∨ (x ∈ (B − C)) ). Conclua, usando as equac¸o˜es em anexo,
que x ∈ A.
Justifique cada passo de prova com exatamente 1 equac¸a˜o da lista em anexo.
A u´nica excec¸a˜o a esta regra e´ o uso de comutatividade e associatividade. Ou
seja, as equac¸o˜es (10), (11), (12) e (13) podem ser usadas simultaneamente em
1 passo de prova.
Resposta:
1. (x ∈ (A ∩ ∅)) ∨ (x ∈ (B − C)) [Premissa]
2. (x ∈ ∅) ∨ (x ∈ (B − C)) [69 em 1]
3. F ∨ (x ∈ (B − C)) [54 em 2]
4. x ∈ (B − C) [10,4 em 3]
5. ¬¬(x ∈ (B − C)) [9 em 4]
6. (x /∈ A)→ ¬(x ∈ (B − C)) [Premissa]
7. ¬(x /∈ A) [38 em 5 e 6]
8. ¬(¬(x ∈ A)) [46 em 7]
9. x ∈ A [9 em 8]
23. {2, 0 pt} Prove que U = ∅, onde U e´ oconjunto universo. Justifique cada passo
de prova com exatamente 1 equac¸a˜o da lista em anexo. A u´nica excec¸a˜o a
esta regra e´ o uso de comutatividade e associatividade. Ou seja, as equac¸o˜es
(10), (11), (12), (13), (73), (74), (75) e (76) podem ser usadas simultaneamente
em 1 passo de prova.
Resposta:
U
= {x | x /∈ U} [64]
= {x | x /∈ (A ∪ A)} [83]
= {x | ¬(x ∈ (A ∪ A))} [46]
= {x | ¬(x ∈ A ∨ x ∈ A)} [58]
= {x | ¬(x ∈ A ∨ x /∈ A)} [65]
= {x | ¬(x ∈ A ∨ ¬(x ∈ A))} [46]
= {x | ¬T} [20]
= {x | F} [2]
= ∅ [53]
24. {2, 0 pt} Prove que (A ∩B)− C = (A− C) ∩ (B − C).
Justifique cada passo de prova com exatamente 1 equac¸a˜o da lista em anexo.
A u´nica excec¸a˜o a esta regra e´ o uso de comutatividade e associatividade.
Ou seja, as equac¸o˜es (10), (11), (12), (13), (73), (74), (75) e (76) podem ser
usadas simultaneamente em 1 passo de prova.
Resposta:
(A ∩ B)− C
= {x | x ∈ (A ∩ B) ∧ x /∈ C} [62]
= {x | (x ∈ A ∧ x ∈ B) ∧ x /∈ C} [60]
= {x | (x ∈ A ∧ x ∈ B) ∧ (x /∈ C ∧ x /∈ C)} [8]
= {x | (x ∈ A ∧ x /∈ C) ∧ (x ∈ B ∧ x /∈ C)} [11,13]
= {x | (x ∈ A− C) ∧ (x ∈ B − C)} [63,63]
= (A−B) ∩ (B − C) [59]
2.2 Func¸o˜es
1. Seja f a func¸a˜o definida por
f(x) =


x+ 2, se x ≤ −1
x2, se − 1 < x ≤ 1
x, se x > 1
Analise cada proposic¸a˜o abaixo. Se for verdadeira, justifique. Se for falsa,
mostre um contra-exemplo.
a) {0, 2 pt} A func¸a˜o e´ injetora no domı´nio dos reais no intervalo [−1, 1] e
contra-domı´nio R.
Resposta: Falso. Para x1 = 1 e x2 = −1, f(1) = f(−1) = 1.
b) {0, 2 pt} A func¸a˜o e´ injetora no domı´nio R e contra-domı´nio R.
Resposta: Falso. Mesmo argumento anterior.
c) {0, 2 pt} A func¸a˜o e´ sobrejetiva no domı´nio dos reais no intervalo [1,+∞)
e contra-domı´nio R.
Resposta: Falso. Na˜o existe nenhum x mapeado a y = −10.
d) {0, 2 pt} A func¸a˜o na˜o possui inversa no domı´nio R e contra-domı´nio R.
Resposta: Verdadeiro. Para ter inversa, a func¸a˜o tem que ser injetora.
A letra b) mostra que na˜o e´ injetora.
2. {1, 0 pt} Seja A o conjunto dos assentos em um teatro. Seja C o conjunto dos
clientes que compraram um ingresso. Gostar´ıamos de fazer um sistema que
so´ vendesse ingressos com lugar marcado. Antes de fazermos um programa,
devemos modelar o problema matematicamente. Descreva os problemas (se
houver) de modelarmos a marcac¸a˜o de lugares para uma pec¸a como:
a) Uma relac¸a˜o (sem ser func¸a˜o) entre C e A.
Resposta: Permite um cliente em n assentos e um assento marcado para
m clientes.
b) Uma func¸a˜o de C para A.
Resposta: Permite n clientes para 1 assento.
c) Uma func¸a˜o injetora de C para A.
Resposta: Na˜o ha´ problemas.
d) Uma func¸a˜o sobrejetora de C para A.
Resposta: Permite n clientes para 1 assento e so´ modela casa cheia.
e) Uma func¸a˜o bijetora de C para A.
Resposta: Todos assentos marcados: so´ modela casa cheia.
Qual dos modelos acima e´ o mais adequado?
Resposta: letra c.
3. {1, 0 pt} Sejam g : A → B e f : B → C. Fac¸a um desenho similar ao da
Figura 1 retratando f e g de tal maneira que f na˜o seja injetiva, mas tanto g
quanto (f ◦ g) sejam injetivas.
A B C
fg
Figura 1: Exemplo de resposta.
Resposta: Veja a Figura 2.
A B C
g
f
Figura 2: Resposta.
4. Seja h uma func¸a˜o com domı´nio em R. Defina o conjunto imagem para:
a) {1, 0 pt} h(x) = bdxec. Resposta: Z
b) {1, 0 pt} h(x) = bxc+d−xe. Resposta: {0}
5. Sejam h e h′ duas func¸o˜es com domı´nio em R.
(a) {1, 0 pt} Se h(x) = dxe − bxc, qual o conjunto imagem de h?
Resposta: {0, 1}
(b) {1, 0 pt} Se h′(x) = bxc+b−xc, qual o conjunto imagem de h′?
Resposta: {0,−1}
6. A func¸a˜o que calcula o valor absoluto ou o mo´dulo de x, f(x) = |x|, e´ definida
para um domı´nio dos reais e contra-domı´nio dos reais. Defina um novo domı´nio
e um novo contra-domı´nio de forma que:
a) {0, 5 pt} f seja injetiva mas na˜o seja sobrejetiva;
Resposta: Domı´nio=R+, Contra-domı´nio=R.
b) {0, 5 pt} f seja sobrejetiva mas na˜o seja injetiva;
Resposta: Domı´nio=R, Contra-domı´nio=R+.
c) {0, 5 pt} f possua inversa.
Resposta: Domı´nio=R+, Contra-domı´nio=R+.
7. Desenhe o gra´fico de:
a) {0, 5 pt} bxc
Resposta: http://www.wolframalpha.com/input/?i=floor(x)
b) {0, 5 pt} dbxce
Resposta: http://www.wolframalpha.com/input/?i=ceil(floor(x))
b) {0, 5 pt} b2xc
Resposta: http://www.wolframalpha.com/input/?i=floor(2x)
8. Sobre func¸o˜es.
a){1, 0 pt} Sejam A = {1, 2, 3} e B = {a, b, c, d, e}. Defina uma func¸a˜o f1 que
seja injetiva mas na˜o seja sobrejetiva de A para B.
Resposta: f1 = {(1, a), (2, b), (3, c)}.
b){1, 0 pt} Sejam C = {1, 2, 3, 4} e D = {a, b, c, d}. Defina uma func¸a˜o f2
que na˜o seja sobrejetiva e na˜o seja injetiva de C para D.
Resposta: f2 = {(1, a), (2, a), (3, c), (4, c)}.
c){1, 0 pt} Sejam E = {1, 2, 3} e F = {a, b, c}. Defina uma func¸a˜o f3 que
tenha inversa de E para F .
Resposta: f3 = {(1, a), (2, b), (3, c)}.
Obs. “Defina uma func¸a˜o” significa “liste os pares”. Por exemplo, {(1, a), (2, d), (3, a)}
e´ uma definic¸a˜o de func¸a˜o de A para B.
9. Desenhe o gra´fico das func¸o˜es abaixo e diga se elas sa˜o “injetivas”, “sobrejeti-
vas”, “bijetivas“ ou “nenhuma delas”. Na˜o precisa provar um teorema sobre
isto. Basta apenas dizer o que a func¸a˜o e´ baseado no gra´fico. A palavra
“gra´fico” aqui tem o mesmo significado de gra´fico em Ca´lculo: uma curva ou
reta no plano xy. Fac¸a seu gra´fico com o eixo x no intervalo de −2 a +4.
a) {0, 5 pt} f(x) = bx/2c+ dx/2e, onde f tem domı´nio real e contra-domı´nio
real.
Resposta: Nenhuma delas. Gra´fico:
b) {0, 5 pt} g(x) = dxe+1, onde g tem domı´nio real e contra-domı´nio inteiro.
Resposta: Sobrejetiva. Gra´fico:
10. Desenhe o gra´fico das func¸o˜es abaixo e diga se elas sa˜o “injetivas”, “sobrejeti-
vas”, “bijetivas“ ou “nenhuma delas”. Na˜o precisa provar um teorema sobre
isto. Basta apenas dizer o que a func¸a˜o e´ baseado no gra´fico. A palavra
“gra´fico” aqui tem o mesmo significado de gra´fico em Ca´lculo: uma curva ou
reta no plano xy. Fac¸a seu gra´fico com o eixo x no intervalo de −2 a +4.
a) {0, 5 pt} f(x) = 2 · dx/2e, onde f tem domı´nio real e contra-domı´nio in-
teiro.
Resposta: Nenhuma delas. Gra´fico:
b) {0, 5 pt} f(x) = bxc − dxe, onde f tem domı´nio real e contra-domı´nio
{0,−1}.
Resposta: Sobrejetiva. Gra´fico:
3 Fundamentos: Algoritmos, Inteiros e Matrizes
3.1 Algoritmos
1. Qual o big-O de:
a) {0, 25 pt} a(n) = (n+ 3n3 + 8n2) + (63n(log n) + 5) Resposta: n3
b) {0, 25 pt} b(n) = (n+ 153)(log n)(√3 + 8) Resposta: n(log n)
c) {0, 25 pt} c(n) = (132n7 + 363n11 + 5) + (53 · 2n + 23n!) Resposta: n!
d) {0, 25 pt} d(n) = 35n+ 9324n(log n) + 634n2 Resposta: n2
e) {0, 25 pt} e(n) = (4n(log n)) + (8log n) + n Resposta: n(log n)
f) {0, 25 pt} f(n) = (36log n) + (235n + 54n) + (642 + 3n + 5n2 + 11n3)
Resposta: n3
2. {0, 25 pt} Ponha as func¸o˜es acima em ordem de complexidade. Escreva sua
resposta da seguinte forma: “{c, e} melhor que {a, d, f} melhor que {b}” (isto
e´ um exemplo).
Esta resposta exemplo significa que c(n) e e(n) sa˜o equivalentes e ambos sa˜o
melhores que a(n), d(n) e f(n), que, por sua vez, sa˜o equivalentes entre si e
melhores que b(n).
Resposta: {b, e} melhor que {d} melhor que {a, f} melhor que {c}
3. Encontre func¸o˜es f ′(n), g′(n), h′(n) e k′(n) que sa˜o big-Θ de f(n), g(n), h(n)
e k(n), respectivamente.
a) {0, 2 pt} f(n) = 5n+ (log n) Resposta: f ′(n) = n
b) {0, 2 pt} g(n) = 10n3 + 5n7 + 400 Resposta: g′(n) = n7
c) {0, 2 pt} h(n) = (5 + 80n3)(n2 + 3) Resposta: h′(n) = n5
d) {0, 2 pt} k(n) = 10 · 2n + 5000 Resposta: k′(n) = 2n
4. Encontre func¸o˜es f ′(n), g′(n), h′(n) e k′(n) que sa˜o big-O de f(n), g(n), h(n)
e k(n), respectivamente.
a) {0, 5 pt} f(n) = (100 + 92n)(10 + log n)
Resposta: f ′(n) = n(log n) ou pior
b) {0, 5 pt} g(n) = n2 + 200n8 + 510n13 + 5n7 + 400n
Resposta: g′(n) = n13 ou pior
c) {0, 5 pt} h(n) = n(log n) + 5n! + 80n3
Resposta: h′(n) = n! ou pior
d) {0, 5 pt} k(n) = n18 + 2n + 5000
Resposta: k′(n) = 2n ou pior
5. Sejam H(n) = n2 + 2n+ 1 e J(n) = n2 (veja a figura abaixo).
a){0, 5 pt} Defina valores para k e C tal que H(n) seja O(J(n)). Justifique
sua resposta.
Resposta:k = 1, 5 e C = 4. Justificativa: para todo x > 1, 5 o gra´fico
de H(n) esta´ sempre abaixo de 4J(n).
b){0, 5 pt} Defina valores para k e C tal que J(n) seja O(H(n)). Justifique
sua resposta.
Resposta: k = 1, 5 e C = 1. Justificativa: para todo x > 1, 5 o gra´fico
de J(n) esta´ sempre abaixo de 1H(n).
“Defina valores” significa dar valores nume´ricos. Por exemplo: “k = −5, 3 e
C = 5283”.
H(n)
J(n)
4J(n)
0
2
4
6
8
10
12
14
16
0 0.5 1 1.5 2
x**2+2*x+1
x**2
4*x**2
6. Calcule o big-O de
a){0, 25 pt} (n2 + 3n+ 10)(5n3 + 2n10)(n3 · n10)
Resposta: n25
b){0, 25 pt} (5 + 3)(log n)(n+ 34 + 4n)
Resposta: n(log n)
c){0, 25 pt} 2n + (n(log n)) + (n3 + 3n2 + 2)
Resposta: 2n
d){0, 25 pt} (n+ (3n+ 4) + (5n))(n2 + n)
Resposta: n3
7. Sejam f(n) = n3n2 + n(log n) e g(n) = (8 + 4)(2n).
a) {0, 25 pt} Defina uma func¸a˜o que seja big-Θ de f(n).
Resposta: n5
b) {0, 25 pt} Defina uma func¸a˜o h(n) que seja big-O de f(n), mas na˜o seja
big-Θ de f(n).
Resposta: Qualquer func¸a˜o estritamente melhor que n5 (na˜o empatado
com n5). Por exemplo, n4, n3, n2, etc.
c) {0, 25 pt} Defina uma func¸a˜o que seja big-Θ de g(n).
Resposta: 2n
d) {0, 25 pt} Defina uma func¸a˜o k(n) que seja big-O de g(n), mas na˜o seja
big-Θ de g(n).
Resposta: Qualquer func¸a˜o estritamente melhor que 2n (mas na˜o em-
patado com 2n). Por exemplo, n1000, n3, n2, etc.
8. Sejam f(n) = n4n3n2n e g(n) = n(1 + (log n)).
a) {0, 25 pt} Defina uma func¸a˜o que seja big-Θ de f(n).
Resposta: n10
b) {0, 25 pt} Defina uma func¸a˜o h(n) que seja big-O de f(n), mas na˜o seja
big-Θ de f(n).
Resposta: Qualquer func¸a˜o estritamente melhor que n10 (na˜o empatado
com n10). Por exemplo, n9, n8, n7, n6, etc.
c) {0, 25 pt} Defina uma func¸a˜o que seja big-Θ de g(n).
Resposta: n(log n)
d) {0, 25 pt} Defina uma func¸a˜o k(n) que seja big-O de g(n), mas na˜o seja
big-Θ de g(n).
Resposta: Qualquer func¸a˜o estritamente melhor que n(log n) (mas na˜o
empatado com n(log n)). Por exemplo, n, n+ 3, 4, etc.
3.2 Inteiros
1. {0, 25 pt} Seja xn uma sequeˆncia de nu´meros pseudo-aleato´rios definida como:
x0 = 0
xn+1 = (4xn + 5) mod 6.
Quantos nu´meros diferentes sa˜o gerados (contando com x0) antes de a sequeˆncia
repetir valores?
Resposta: 4. Pois, x0 = 0, x1 = 5, x2 = 1, x3 = 3, x4 = 5, . . .
2. {0, 25 pt} Encontre o mdc de 26 e 16 utilizando a te´cnica de fatorac¸a˜o.
Resposta: (26 = 21 · 131) e (16 = 24 · 130). mdc(26, 16) = 21 · 130 = 2.
3. {0, 25 pt} Encontre o mmc de 14 e 20 utilizando a te´cnica de fatorac¸a˜o.
Resposta: (14 = 21 ·50 ·71) e (20 = 22 ·51 ·70). mmc(14, 20) = 22 ·51 ·71 = 140.
4. {0, 75 pt}
Teorema 1. (ab)m = ambm.
Teorema 2 (Pequeno Teorema de Fermat). Se p e´ primo e a e´ inteiro na˜o
divis´ıvel por p, enta˜o ap−1 ≡ 1 (mod p).
Prove que o resto da divisa˜o de 16.777.216.000.000.000.000 por 13 e´ 1. Note
que 412 = 16.777.216.
Resposta:
16.777.216.000.000.000.000
= 16.777.216 · 1.000.000.000.000 [Aritme´tica]
= 412 · 1012 [Aritme´tica]
= (4 · 10)12 [Teorema 1]
= 4012 [Aritme´tica] {0, 25 pt}
Sejam a = 40 e p = 13.
Como 40 = 13 · 3 + 1, enta˜o 40 na˜o e´ divis´ıvel por 13 {0, 25 pt}.
Pelo Pequeno Teorema de Fermat, 4013−1 ≡ 1 (mod 13). Ou seja, o resto da
divisa˜o de 4012 e´ 1. {0, 25 pt}
5. {3, 5 pt} Sejam a e b inteiros positivos. Prove que ab = mdc(a, b) ·mmc(a, b).
Dica: defina a e b como fatorac¸a˜o de primos e use as definic¸o˜es de mdc e
mmc baseado em fatorac¸a˜o de primos. Caso precise, utilize o Teorema 1:
min(x, y) +max(x, y) = x+ y.
Resposta:
Sejam a = pa11 p
a2
2 · . . . · pann e b = pb11 pb22 · . . . · pbnn .
a · b
= (pa11 p
a2
2 · . . . · pann ) · (pb11 pb22 · . . . · pbnn ) [Definic¸a˜o a e b]
= pa1+b11 p
a2+b2
2 · . . . · pan+bnn [Aritme´tica]
= p
min(a1,b1)+max(a1,b1)
1 · . . . · pmin(an,bn)+max(an,bn)n [Teorema 1]
= (p
min(a1,b1)
1 · . . . · pmax(an,bn)n ) · (pmax(a1,b1)1 · . . . · pmax(an,bnn ) [Aritme´tica]
= mdc(a, b) ·mmc(a, b) [Def. mdc e mmc]
6. O algoritmo abaixo se propo˜e a imprimir os fatores primos de um nu´mero
inteiro n > 0.
input: inteiro n > 0
primo := 2;
while (primo ≤ n) {
if (n mod primo == 0) {
print(primo);
n := n div primo;
primo := 2;
}
else {
primo := prox primo(n);
}
}
print(n);
a) {1, 0 pt} O algoritmo funciona? Resposta: Sim.
b) {2, 0 pt} Existe alguma correc¸a˜o ou melhoria poss´ıvel? Qual? Resposta:
Sim. Melhoria: o lac¸o so´ precisa ir ate´
√
n.
7. Seja f(n) = (n + 4) mod 26 a func¸a˜o que encripta uma mensagem de texto
considerando o alfabeto
A=0, B=1, C=2, D=3, E=4, F=5, G=6, H=7, I=8, J=9, K=10, L=11, M=12,
N=13, O=14, P=15, Q=16, R=17, S=18, T=19, U=20, V=21, W=22, X=23,
Y=24, Z=25.
a) {0, 2 pt} Encripte a mensagem “ZEUS”. Exiba os ca´lculos que te levam a`
resposta.
Resposta:
f(Z) = f(25) = (25 + 4) mod 26 = 3 = D
f(E) = f(4) = (4 + 4) mod 26 = 8 = I
f(U) = f(20) = (20 + 4) mod 26 = 24 = Y
f(S) = f(18) = (18 + 4) mod 26 = 22 = W
“DIYW”
b) {0, 2 pt} Defina a func¸a˜o f−1(n) que desencripta mensagens de f(n). Re-
sposta: f−1 = (n− 4) mod 26
c) {0, 2 pt} Desencripte a mensagem “GCBA”. Exiba os ca´lculos que te levam
a` resposta.
Resposta:
f−1(G) = f−1(6) = (6− 4) mod 26 = 2 = C
f−1(C) = f−1(2) = (2− 4) mod 26 = 24 (veja abaixo)= Y
f−1(B) = f−1(1) = (1− 4) mod 26 = 23 (veja abaixo)= X
f−1(A) = f−1(0) = (0− 4) mod 26 = 22 (veja abaixo)= W
−2/26 = −0, 08. Portanto, −2 div 26 = b−0, 08c = −1.
Enta˜o, −2 = 26 · (−1) + r. Ou seja, r = 24.
−3/26 = −0, 12. Portanto, −3 div 26 = b−0, 12c = −1.
Enta˜o, −3 = 26 · (−1) + r. Ou seja, r = 23.
−4/26 = −0, 15. Portanto, −4 div 26 = b−0, 15c = −1.
Enta˜o, −4 = 26 · (−1) + r. Ou seja, r = 22.
8. {0, 6 pt} Sejam mdc(p, q) = 23345170 e q = 253458710. Utilize a definic¸a˜o de
mdc em termos de fatores primos para encontrar p.
Obs. Existem infinitas respostas. Basta escrever 1 delas.
Resposta: Seja p = 2x3y5z7k. Comomdc(p, q) = 2min(x,5)3min(y,4)5min(z,8)7min(k,10),
temos que encontrar
x, tal que min(x, 5) = 3
y, tal que min(y, 4) = 4
z, tal que min(z, 8) = 1
k, tal que min(k, 10) = 0
Ou seja p = 233y5170, onde y ≥ 4. Poss´ıveis respostas: 23345170, 23355170,
23365170, 23375170, 23385170, . . .
9. {1, 0 pt} Resolva o sistema de equac¸o˜es abaixo.
x ≡ 2 (mod 3)
x ≡ 1 (mod 4)
x ≡ 3 (mod 5)
• Mostre seus ca´lculos;
• Deixe expl´ıcito os valores de cada Mk
• Deixe expl´ıcito os valores de cada yk
• Dica: sempre que calcular yk e x, teste se estes nu´meros esta˜o corretos.
Resposta:
Crite´rios de correc¸a˜o:
Ca´lculo dos Mk : {0, 25 pt}
Ca´lculo dos yk : {0, 5 pt}
Ca´lculo de x : {0, 25 pt}
M1 =
3·4·5
3
= 20, M2 =
3·4·5
4
= 15, M3 =
3·4·5
5
= 12.
y1 e´ o inverso de 20 mo´dulo 3. Ca´lculo:
Pelo algoritmo de Euclides:
20 = 6 · 3 + 2
3 = 1 · 2 + 1
Enta˜o:
1 = 3− 1 · 2
1 = 3− 1(20− 6 · 3)
1 = 3− 20 + 6 · 3
1 = (−1) · 20 + 7 · 3
Ou seja, y1 = −1.
y2 e´ o inverso de 15 mo´dulo 4. Ca´lculo:
Pelo algoritmo de Euclides:
15 = 3 · 4 + 3
4 = 1 · 3 + 1Enta˜o:
1 = 4− 1 · 3
1 = 4− 1(15− 3 · 4)
1 = 4− 15 + 3 · 4
1 = (−1)15 + 4 · 4
Ou seja, y2 = −1.
y3 e´ o inverso de 12 mo´dulo 5. Ca´lculo:
Pelo algoritmo de Euclides:
12 = 2 · 5 + 2
5 = 2 · 2 + 1Enta˜o:
1 = 5− 2 · 2
1 = 5− 2(12− 2 · 5)
1 = 5− 2 · 12 + 4 · 5
1 = (−2)12 + 5 · 5
Ou seja, y3 = −2.
x = (2 ·20 · (−1))+ (1 ·15 · (−1))+ (3 ·12 · (−2)) = −127. Ou qualquer soluc¸a˜o
y, tal que y ≡ −127 (mod 60), por exemplo: y = 53.
10. Calcule o inverso de
a) {1, 0 pt} 4 mo´dulo 9. Resposta: -2
b) {1, 0 pt} 2 mo´dulo 17. Resposta: -8
c) {1, 0 pt} 7 mo´dulo 26. Resposta: -11
Teste sua soluc¸a˜o!
11. {2, 0 pt} Calcule x usando o teorema Chineˆs do Resto. Deixe expl´ıcito os
valores de Mk e yk.
x ≡ 1 (mod 2)
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
Resposta: M1 = 15, M2 = 10, M3 = 6. y1 = y2 = y3 = 1. x = 53
12. Sejam a, b, c, d e m inteiros, onde m ≥ 2, c > 0 e d > 0. Descubra valo-
res nume´ricos para a, b, c, d e m que tornem as proposic¸o˜es abaixo falsas.
Observac¸a˜o. Os valores para a, b, c, d e m sa˜o diferentes nas letras (a) e (b).
A resposta deve estar neste formato:
(a) a = 3, b = 4, c = 8, m = 3
(b) a = 5, b = 3, c = 2, d = 7, m = 4
(a) {1, 0 pt} (ac ≡ bc (mod m))→(a ≡ b (mod m))
Resposta: Uma poss´ıvel resposta e´: a = 3, b = 4, c = 2 e m = 2.
Justificativa: estes valores fazem (ac ≡ bc (mod m)) ser T (porque 3 · 2
mod 2 = 4 · 2 mod 2) e (a ≡ b (mod m)) ser F (porque 3 mod 2 6= 4
mod 2). Portanto, a implicac¸a˜o e´ F.
(b) {1, 0 pt} ( (a ≡ b (mod m)) ∧ (c ≡ d (mod m)) ) → (ac ≡ bd (mod m))
Resposta: Uma poss´ıvel resposta e´: a = 3, b = 3, c = 1, d = 6, m = 5.
Justificativa: similar a` letra (a).
13. {1, 0 pt} Use o Teorema Chineˆs do Resto para encontrar uma soluc¸a˜o para
o sistema de equac¸o˜es abaixo. Exiba seus ca´lculos. Sugesta˜o: teste seu
resultado para ter certeza que calculou corretamente.
x ≡ 1 (mod 3)
x ≡ 2 (mod 4)
x ≡ 3 (mod 5)
Para sua ajuda, segue abaixo a fo´rmula do Teorema Chineˆs do Resto. Em um
sistema de equac¸o˜es
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
...
x ≡ an (mod mn)
A soluc¸a˜o e´ x = a1M1y1 + a2M2y2 + . . .+ anMnyn. Onde, m = m1m2 . . .mn,
Mk = m/mk e yk e´ o inverso de Mk mo´dulo mk.
Resposta: Sejam m = 3 · 4 · 5 = 60, M1 = 4 · 5 = 20, M2 = 3 · 5 = 15,
M3 = 3 · 4 = 12, m1 = 3, m2 = 4, m5 = 5.
Ca´lculo de y1 (inverso de 20 mo´dulo 3). Pelo algoritmo de Euclides, sabemos
que 20 = 3 · 6+2 e 3 = 2 · 1+1. Substituindo a primeira equac¸a˜o na segunda,
temos que 1 = 4 · 3 + (−1) · 20. Ou seja, y1 = −1.
Ca´lculo de y2 (inverso de 15 mo´dulo 4). Pelo algoritmo de Euclides, sabemos
que 15 = 4 · 3+3 e 4 = 3 · 1+1. Substituindo a primeira equac¸a˜o na segunda,
temos que 1 = 4 · 4 + (−1) · 15. Ou seja, y2 = −1.
Ca´lculo de y3 (inverso de 12 mo´dulo 5). Pelo algoritmo de Euclides, sabemos
que 12 = 5 · 2+2 e 5 = 2 · 2+1. Substituindo a primeira equac¸a˜o na segunda,
temos que 1 = 5 · 5 + (−2) · 12. Ou seja, y3 = −2.
Aplicando a fo´rmula, temos que x = 1 · (−1) · 20+ 2 · (−1) · 15+ 3 · (−2) · 12 =
−122.
14. Calcule o MDC de
a){0, 5 pt} 30 e 12 utilizando o me´todo da fatorac¸a˜o.
Resposta:
30 = 2 · 3 · 5 = 213151
12 = 2 · 2 · 3 = 223150
MDC(30, 12) = 2min(1,2)3min(1,1)5min(1,0) = 223150 = 6
b){0, 5 pt} 126 e 48 utilizando o algoritmo de Euclides.
Resposta:
126 = 48 · 2 + 30
48 = 30 · 1 + 18
30 = 18 · 1 + 12
18 = 12 · 1 + 6
12 = 6 · 2 + 0
MDC(126, 48) = 6
Nas duas letras acima, exiba seus ca´lculos.
15. Calcule (e exiba seus ca´lculos):
a){0, 25 pt} O inverso de 43 mo´dulo 15.
Resposta:
43 = 15 · 2 + 13
15 = 13 · 1 + 2
13 = 2 · 6 + 1
1
= 13− 2 · 6
= 13− (15− 13) · 6
= 13− 15 · 6 + 13 · 6
= 13 · 7− 15 · 6
= (43− 15 · 2) · 7− 15 · 6
= (43 · 7)− 15 · 14− 15 · 6
= 43 · 7− 15 · 20
Resposta = 7
b){0, 25 pt} O inverso de 15 mo´dulo 43.
Resposta: -20
c){0, 25 pt} Um x, tal que 5x ≡ 2 (mod 34).
Resposta:
5 = 34 · 0 + 5
34 = 5 · 6 + 4
5 = 4 · 1 + 1
1
= 5− 4 · 1
= 5− (34− 5 · 6)1
= 5− 34 + 5 · 6
= 5 · 7− 34
= (5− 34 · 0)7− 34
= (5− 0)7− 34
= 5 · 7− 34
Resposta = 7 · 2 = 14.
d){0, 25 pt} Um x, tal que 74x ≡ 5 (mod 33).
Resposta:
74 = 33 · 2 + 8
33 = 8 · 4 + 1
1
= 33− 8 · 4
= 33− (74− 33 · 2)4
= 33− 74 · 4 + 33 · 8
= 33 · 9− 74 · 4
Resposta = −4 · 5 = −20.
16. Calcule o MDC de
a){0, 5 pt} 52 e 24 utilizando o me´todo da fatorac¸a˜o.
Resposta:
52 = 2 · 2 · 13 = 2230131
24 = 2 · 2 · 2 · 3 = 2331130
MDC(52, 24) = 2min(2,3)3min(1,0)13min(1,0) = 2230130 = 4
b){0, 5 pt} 212 e 88 utilizando o algoritmo de Euclides.
Resposta:
212 = 88 · 2 + 36
88 = 36 · 2 + 16
36 = 16 · 2 + 4
16 = 4 · 4 + 0
MDC(212, 88) = 4
17. {1, 0 pt} Use o Teorema Chineˆs do Resto para encontrar uma soluc¸a˜o para
o sistema de equac¸o˜es abaixo. Exiba seus ca´lculos. Sugesta˜o: teste seu
resultado para ter certeza que calculou corretamente.
x ≡ 4 (mod 5)
x ≡ 3 (mod 3)
x ≡ 2 (mod 8)
Para sua ajuda, segue abaixo a fo´rmula do Teorema Chineˆs do Resto. Em um
sistema de equac¸o˜es
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
...
x ≡ an (mod mn)
A soluc¸a˜o e´ x = a1M1y1 + a2M2y2 + . . .+ anMnyn. Onde, m = m1m2 . . .mn,
Mk = m/mk e yk e´ o inverso de Mk mo´dulo mk.
Resposta: Sejam m = 5 · 3 · 8 = 120, M1 = 3 · 8 = 24, M2 = 5 · 8 = 40,
M3 = 5 · 3 = 15, m1 = 5, m2 = 3, m3 = 8.
Ca´lculo de y1 (inverso de 24 mo´dulo 5):
24 = 5 · 4 + 4
5 = 4 · 1 + 1
1
= 5− 4
= 5− (24− 5 · 4)
= 5− 24 + 5 · 4
= 5 · 5− 24
y1 = −1.
Ca´lculo de y2 (inverso de 40 mo´dulo 3):
40 = 3 · 13 + 1
1
= 40− 3 · 13
y2 = 1.
Ca´lculo de y3 (inverso de 15 mo´dulo 8):
15 = 8 · 1 + 7
8 = 7 · 1 + 1
1
= 8− 7
= 8− (15− 8)
= 8− 15 + 8
= 2 · 8− 15
y3 = −1.
x = 4 · 24 · (−1) + 3 · 40 · 1 + 2 · 15 · (−1) = −96 + 120− 30 = −6.
18. {1, 0 pt} Use o Teorema Chineˆs do Resto para encontrar uma soluc¸a˜o para
o sistema de equac¸o˜es abaixo. Exiba seus ca´lculos. Sugesta˜o: teste seu
resultado para ter certeza que calculou corretamente.
x ≡ 2 (mod 3)
x ≡ 3 (mod 4)
x ≡ 4 (mod 5)
Para sua ajuda, segue abaixo a fo´rmula do Teorema Chineˆs do Resto. Em um sistema de
equac¸o˜es
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
...
x ≡ an (mod mn)
A soluc¸a˜o e´ x = a1M1y1 + a2M2y2 + . . .+ anMnyn. Onde, m = m1m2 . . .mn,
Mk = m/mk e yk e´ o inverso de Mk mo´dulo mk.
Resposta: Sejam m = 3 · 4 · 5 = 60, M1 = 60/3 = 20, M2 = 60/4 = 15,
M3 = 60/5 = 12, m1 = 3, m2 = 4, m3 = 5.
Ca´lculo de y1 (inverso de 20 mo´dulo 3):
20 = 3 · 6 + 2
3 = 2 · 1 + 1
1
= 3− 2 · 1
= 3− (20− 3 · 6) · 1
= 3− 20 + 6 · 3
= (−1) · 20 + 7 · 3
y1 = −1.
Ca´lculo de y2 (inverso de 15 mo´dulo 4):
15 = 4 · 3 + 3
4 = 3 · 1 + 1
1
= 4− 3 · 1
= 4− (15− 4 · 3) · 1
= 4− 15 + 4 · 3
= (−1) · 15 + 4 · 4
y2 = −1.
Ca´lculo de y3 (inverso de 12 mo´dulo 5):
12 = 5 · 2 + 2
5 = 2 · 2 + 1
1
= 5− 2 · 2
= 5− 2 · (12− 5 · 2)
= 5− 2 · 12 + 4 · 5
= (−2) · 12 + 5 · 5
y3 = −2.
x = 2 · 20 · (−1) + 3 · 15 · (−1) + 4 · 12 · (−2) = −40− 45− 96 = −181.
19. {1, 0 pt} Use o Teorema Chineˆs do Resto para encontrar uma soluc¸a˜o para
o sistema de equac¸o˜es abaixo. Exiba seus ca´lculos. Sugesta˜o: teste seu
resultado para ter certeza que calculou corretamente.
x ≡ 1 (mod 3)
x ≡ 3 (mod 4)
x ≡ 3 (mod 5)
Para sua ajuda, segue abaixo a fo´rmula do Teorema Chineˆs do Resto. Em um sistema de
equac¸o˜es
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
...
x ≡ an (mod mn)
A soluc¸a˜o e´ x = a1M1y1 + a2M2y2 + . . .+ anMnyn. Onde, m = m1m2 . . .mn,
Mk = m/mk e yk e´ o inverso de Mk mo´dulo mk.
Resposta: Sejam m = 3 · 4 · 5 = 60, M1 = 60/3 = 20, M2 = 60/4 = 15,
M3 = 60/5 = 12, m1 = 3, m2 = 4, m3 = 5.
Ca´lculo de y1 (inverso de 20 mo´dulo 3):
20 = 3 · 6 + 2
3 = 2 · 1 + 1
1
= 3− 2 · 1
= 3− (20− 3 · 6) · 1
= 3− 20 + 3 · 6
= (−1) · 20 + 7 · 3
y1 = −1.
Ca´lculo de y2 (inverso de 15 mo´dulo 4):
15 = 4 · 3 + 3
4 = 3 · 1 + 1
1
= 4− 3 · 1
= 4− (15− 4 · 3) · 1
= 4− 15 + 4 · 3
= (−1) · 15 + 4 · 4
y2 = −1.
Ca´lculo de y3 (inverso de 12 mo´dulo 5):
12 = 5 · 2 + 2
5 = 2 · 2 + 1
1
= 5− 2 · 2
= 5− 2 · (12− 5 · 2)
= 5− 2 · 12 + 4 · 5
= (−2) · 12 + 5 · 5
y3 = −2.
x = 1 · 20 · (−1) + 3 · 15 · (−1) + 3 · 12 · (−2) = −20− 45− 72 = −137.
4 Induc¸a˜o e Recursa˜o
4.1 Induc¸a˜o Matema´tica
1. {2, 0 pt} Queremos provar que ((8n−2n) mod 6) = 0 para todo inteiro n ≥ 1.
Prove por induc¸a˜o matema´tica. Caso precise, utilize o Teorema 1: 8k+1 −
2k+1 = 8(8k − 2k) + 8 · 2k − 2 · 2k
Resposta:
Base.
(81 − 21) mod 6
= 6 mod 6 [Aritme´tica]
= 0 [Def. mod ]
Passo indutivo.
(8k+1 − 2k+1) mod 6
= (8(8k − 2k) + 8 · 2k − 2 · 2k) mod 6 [Teorema 1]
= (8(8k − 2k) + 2k(8− 2)) mod 6 [Aritme´tica]
= (8(8k − 2k) + 2k · 6) mod 6 [Aritme´tica]
= ((((8 mod 6)((8k − 2k) mod 6)) mod 6) + 2k · 6) mod 6 [Aritme´tica]
= ((((8 mod 6) · 0) mod 6) + 2k · 6) mod 6 [Hipo´tese de Induc¸a˜o]
= ((0 mod 6) + 2k · 6) mod 6 [Aritme´tica]
= (0 + 2k · 6) mod 6 [Def. mod ]
= (2k · 6) mod 6 [Aritme´tica]
= 0 [Def. mod ]
2. {1, 0 pt} Seja P (n) =
(
n∑
i=1
i2 =
n(n+ 1)(2n+ 1)
6
)
.
Prove por induc¸a˜o que P (n) e´ verdade para n ≥ 1.
• Mostre seus ca´lculos;
• Escreva o objetivo de prova do caso base e do passo indutivo.
• Escreva a hipo´tese de induc¸a˜o
• Justifique da melhor forma poss´ıvel cada passo de prova.
• Utilize a Equac¸a˜o 1 abaixo caso precise:
k(k + 1)(2k + 1) + 6(k + 1)2
6
=
(k + 1)((k + 1) + 1)(2(k + 1) + 1)
6
[1]
Resposta:
Crite´rios de correc¸a˜o:
Objetivo de prova da base: {0, 2 pt}
Prova da base: {0, 2 pt}
Objetivo de prova dopasso indutivo: {0, 2 pt}
Hipo´tese de induc¸a˜o: {0, 2 pt}
Prova do passo indutivo: {0, 2 pt}
Base. Objetivo de prova:
1∑
i=1
i2 =
1(1 + 1)(2 · 1 + 1)
6
Prova:
1∑
i=1
i2
= 12 [Def.
∑
]
= 1 [12 = 1]
= 1(1+1)(2·1+1)
6
[Aritme´tica]
Induc¸a˜o. Objetivo de prova:
k+1∑
i=1
i2 =
(k + 1)((k + 1) + 1)(2(k + 1) + 1)
6
Hipo´tese de induc¸a˜o:
k∑
i=1
i2 =
k(k + 1)(2k + 1)
6
Prova:
k+1∑
i=1
i2
=
k∑
i=1
ik + (k + 1)2 [Def.
∑
]
= k(k+1)(2k+1)
6
+ (k + 1)2 [Hipo´tese de Induc¸a˜o]
= k(k+1)(2k+1)+6(k+1)
2
6
[Denominador comum]
= (k+1)((k+1)+1)(2(k+1)+1)
6
[Eq. 1]
3. Ao provarmos por induc¸a˜o que
(4 + 10 + 16 + . . .+ (6n− 2)) = (n(3n+ 1))
para todo n > 0:
a) {0, 2 pt} Qual o objetivo de prova do caso base?
Resposta: 6 · 1− 2 = 1 · (3 · 1 + 1)
b) {0, 2 pt} Prove o caso base.
Resposta:
6 · 1− 2
= 4 [Aritme´tica]
= 3 + 1 [Aritme´tica]
= 3 · 1 + 1 [Aritme´tica]
= 1 · (3 · 1 + 1) [Aritme´tica]
c) {0, 2 pt} Qual o objetivo de prova do passo indutivo?
Resposta: (4 + 10 + 16 + . . . + (6k − 2) + (6(k + 1)− 2)) = ((k + 1) ·
(3 · (k + 1) + 1))
d) {0, 2 pt} Qual a hipo´tese de induc¸a˜o?
Resposta: (4 + 10 + 16 + . . .+ (6k − 2)) = (k(3k + 1))
e) {0, 2 pt} Prove o passo indutivo. Justifique cada passo com os termos
“[Aritme´tica]”, “[Hipo´tese de Induc¸a˜o]” ou com “[100]”, cuja equac¸a˜o e´
dada abaixo:
(3k2 + 7k + 4) = ((k + 1)(3(k + 1) + 1)) [100]
Resposta:
4 + 10 + 16 + . . .+ (6k − 2) + (6(k + 1)− 2)
= k(3k + 1) + (6(k + 1)− 2) [Hipo´tese de Induc¸a˜o]
= 3k2 + k + 6k + 6− 2 [Aritme´tica]
= 3k2 + 7k + 4 [Aritme´tica]
= (k + 1)(3(k + 1) + 1) [100]
4. Ao provarmos por induc¸a˜o matema´tica que
n+ n = 2n
para todo n ≥ 0:
a) {0, 5 pt} Qual o objetivo de prova do caso base?
Resposta: 0 + 0 = 2 · 0
b) {0, 5 pt} Prove o caso base. Justifique cada passo com “Aritme´tica”.
Resposta:
0 + 0
= 0 [Aritme´tica]
= 2 · 0 [Aritme´tica]
c) {0, 5 pt} Qual o objetivo de prova do passo indutivo?
Resposta: (k + 1) + (k + 1) = 2(k + 1)
d) {0, 5 pt} Qual a hipo´tese de induc¸a˜o?
Resposta: k + k = 2k
e) {1, 0 pt} Prove o passo indutivo. Justifique cada passo com “Hipo´tese de
Induc¸a˜o” ou com uma das equac¸o˜es abaixo. Na˜o pode justificar com
“Aritme´tica”.
2(x+ 1) = 2x+ 2 [100]
(x+ y) + (x+ y) = (x+ x) + (y + y) [101]
(1 + 1) = 2 [102]
Resposta:
(k + 1) + (k + 1)
= (k + k) + (1 + 1) [101]
= 2k + (1 + 1) [Hipo´tese de Induc¸a˜o]
= 2k + 2 [102]
= 2(k + 1) [100]
5. Seja a func¸a˜o F definida da seguinte forma:
F (1) = 5
F (n) = F (n− 1) + 5n
Queremos provar por induc¸a˜o matema´tica que 5+10+15+ . . .+5n = F (n),
para todo n > 0.
a){0, 15 pt} Qual o objetivo de prova do caso base?
Resposta: 5 · 1 = F (1).
b){0, 15 pt} Prove o caso base. Justifique com “Aritme´tica” ou “Definic¸a˜o de
F”.
Resposta:
5 · 1
= 5 [Aritme´tica]
= F (1) [Definic¸a˜o de F (n)]
c){0, 15 pt} Qual o objetivo de prova do passo indutivo?
Resposta: 5 + 10 + 15 + . . .+ 5k + 5(k + 1) = F (k + 1).
d){0, 15 pt} Qual a hipo´tese de induc¸a˜o?
Resposta: 5 + 10 + 15 + . . .+ 5k = F (k).
e){0, 40 pt} Prove o passo indutivo. Justifique seus passos de prova com
“Aritme´tica”, “Hipo´tese de Induc¸a˜o” ou “Definic¸a˜o de F”.
Resposta:
5 + 10 + 15 + . . .+ 5k + 5(k + 1)
= F (k) + 5(k + 1) [Hipo´tese de Induc¸a˜o]
= F ((k + 1)− 1) + 5(k + 1) [Aritme´tica]
= F (k + 1) [Definic¸a˜o de F ]
6. Queremos provar por induc¸a˜o matema´tica que todo nu´mero par, ao ser dividido
por 2, tem resto 0. Ou seja, queremos provar que (2n mod 2) = 0 para todo
n ≥ 0:
a){0, 5 pt} Qual o objetivo de prova do caso base?
Resposta: ((2 · 0) mod 2) = 0.
b){0, 5 pt} Prove o caso base.
Resposta:
((2 · 0) mod 2)
= 0 mod 2 [Aritme´tica]
= 0 [Aritme´tica]
c){0, 5 pt} Qual o objetivo de prova do passo indutivo?
Resposta: (2(k + 1) mod 2) = 0.
d){0, 5 pt} Qual a hipo´tese de induc¸a˜o?
Resposta: (2k mod 2) = 0.
e){1, 0 pt} Prove o passo indutivo. Justifique seus passos de prova com “Arit-
me´tica”, “Hipo´tese de Induc¸a˜o” ou “[1]”, onde [1] e´ a equac¸a˜o abaixo:
((2k + 2) mod 2) = (((2k mod 2) + (2 mod 2)) mod 2) [1]
Resposta:
2(k + 1) mod 2
= (2k + 2) mod 2 [Aritme´tica]
= ((2k mod 2) + (2 mod 2)) mod 2 [1]
= (0 + (2 mod 2)) mod 2 [Hipo´tese de Induc¸a˜o]
= (0 + 0) mod 2 [Aritme´tica]
= 0 mod 2 [Aritme´tica]
= 0 [Aritme´tica]
7. Queremos provar por induc¸a˜o matema´tica que todo nu´mero ı´mpar, ao ser
dividido por 2, tem resto 1. Ou seja, queremos provar que ((2n−1)mod 2) = 1
para todo n > 0:
a){0, 15 pt} Qual o objetivo de prova do caso base?
Resposta: ((2 · 1− 1) mod 2) = 1.
b){0, 15 pt} Prove o caso base.
Resposta:
((2 · 1− 1) mod 2)
= (2− 1) mod 2 [Aritme´tica]
= 1 mod 2 [Aritme´tica]
= 1 [Aritme´tica]
c){0, 15 pt} Qual o objetivo de prova do passo indutivo?
Resposta: ((2(k + 1)− 1) mod 2) = 1.
d){0, 15 pt} Qual a hipo´tese de induc¸a˜o?
Resposta: ((2k − 1) mod 2) = 1.
e){0, 40 pt} Prove o passo indutivo. Justifique seus passos de prova com
“Aritme´tica”, “Hipo´tese de Induc¸a˜o” ou “[1]”, onde [1] e´ a equac¸a˜o
abaixo:
(((2k−1)+2)mod 2) = ((((2k−1)mod 2)+(2mod 2))mod 2) [1]
Resposta:
(2(k + 1)− 1) mod 2
= (2k + 2− 1) mod 2 [Aritme´tica]
= ((2k − 1) + 2) mod 2 [Aritme´tica]
= (((2k − 1) mod 2) + (2 mod 2)) mod 2 [1]
= (1 + (2 mod 2)) mod 2 [Hipo´tese de Induc¸a˜o]
= (1 + 0) mod 2 [Aritme´tica]
= 1 mod 2 [Aritme´tica]
= 1 [Aritme´tica]
8. Queremos provar por induc¸a˜o matema´tica que
(0 mod 2) · (2 mod 2) · (4 mod 2) · (6 mod 2) · . . . · (2n mod 2) = 0
para todo n ≥ 0.
a){0, 5 pt} Qual o objetivo de prova do caso base?
Resposta: ((2 · 0) mod 2) = 0.
b){0, 5 pt} Prove o caso base.
Resposta:
((2 · 0) mod 2)
= 0 mod 2 [Aritme´tica]
= 0 [Aritme´tica]
c){0, 5 pt} Qual o objetivo de prova do passo indutivo?
Resposta:
(0 mod 2) · (2 mod 2) · . . . · (2k mod 2) · (2(k + 1) mod 2) = 0
d){0, 5 pt} Qual a hipo´tese de induc¸a˜o?
Resposta:
(0 mod 2) · (2 mod 2) · . . . · (2k mod 2) = 0
e){1, 0 pt} Prove o passo indutivo. Justifique seus passos de prova com “Arit-
me´tica” ou “Hipo´tese de Induc¸a˜o”.
Resposta:
(0 mod 2) · (2 mod 2) · . . . · (2k mod 2) · (2(k + 1) mod 2)
= 0 · (2(k + 1) mod 2) [Hipo´tese de Induc¸a˜o]
= 0 [Aritme´tica]
9. Queremos provar por induc¸a˜o matema´tica que
n+ n+ n+ n = 4n
para todo n ≥ 0.
a){0, 15 pt} Qual o objetivo de prova do caso base?
Resposta: 0 + 0 + 0 + 0 = 4 · 0.
b){0, 15 pt} Prove o caso base.
Resposta:
0 + 0 + 0 + 0
= 0 [Aritme´tica]
= 4 · 0 [Aritme´tica]
c){0, 15 pt} Qual o objetivo de prova do passo indutivo?
Resposta:
(k + 1) + (k + 1) + (k + 1) + (k + 1) = 4 · (k + 1)
d){0, 15 pt} Qual a hipo´tese de induc¸a˜o?
Resposta:
k + k + k + k = 4k
e){0, 40 pt} Prove o passo indutivo. Justifique seus passos de prova com
“Aritme´tica” ou “Hipo´tese de Induc¸a˜o”. Utilize, obrigatoriamente,
a hipo´tese de induc¸a˜o na sua prova.
Resposta:
(k + 1) + (k + 1) + (k + 1) + (k + 1)
= (k + k + k + k) + 4 [Aritme´tica]
= 4k + 4 [Hipo´tese de Induc¸a˜o]
= 4(k + 1) [Aritme´tica]
10. Queremos provar por induc¸a˜o matema´tica que
(1 mod 2) + (3 mod 2) + (5 mod 2) + . . .+ ((2n− 1) mod 2) = n
para todo n > 0.
a){0, 15 pt} Qual o objetivo de prova do caso base?
Resposta: (1 mod 2) = 1.
b){0, 15 pt} Prove o caso base. Justifique cada passo com “Aritme´tica”.
Resposta:
1 mod 2
= 1 [Aritme´tica]
c){0, 15 pt} Qual o objetivo de prova do passo indutivo?
Resposta:
(1 mod 2) + (3 mod 2) + (5 mod 2) + . . .+ ((2k− 1) mod 2) + ((2(k+
1)− 1) mod 2) = (k + 1)
d){0, 15 pt} Qual a hipo´tese de induc¸a˜o?
Resposta:
(1 mod 2) + (3 mod 2) + (5 mod 2) + . . .+ ((2k − 1) mod 2) = k
e){0, 40 pt} Prove o passo indutivo. Justifique seus passos de prova com
“Aritme´tica”, “Hipo´tese de Induc¸a˜o” ou “[100]”, onde [100] e´ a equac¸a˜o
dada (de grac¸a) abaixo:
((2k + 1) mod 2) = 1 [100]
Use, obrigatoriamente, a hipo´tese de induc¸a˜o na sua prova.
Resposta:
(1 mod 2) + (3 mod 2) + (5 mod 2) + . . .
. . .+ ((2k − 1) mod 2) + ((2(k + 1)− 1) mod 2)
= k + ((2(k + 1)− 1) mod 2) [Hipo´tese de Induc¸a˜o]
= k + ((2k + 2− 1) mod 2) [Aritme´tica]
= k + ((2k + 1) mod 2) [Aritme´tica]
= k + 1 [100]
4.2 Induc¸a˜o Estrutural1. Seja o conjunto de strings A = {“1”,“11”,“111”, . . .} definido assim:
Caso base. O string “1” pertence a A.
Caso recursivo. Seja s um string que pertenc¸a a A. Enta˜o o string “1”+s
tambe´m pertence a` A.
Obs1. O s´ımbolo de + acima e´ uma concatenac¸a˜o de strings. Exemplo:
“xyz”+“abc” = “xyzabc”, “1”+“111” = “1111”.
Obs2. Todos elementos de A sa˜o provenientes do passo base e passo recursivo.
Seja C(s) a func¸a˜o que retorna o comprimento do string s. Por exemplo,
C(“1”) = 1, C(“11111”) = 5, etc.
Seja F (s) a func¸a˜o que retorna a soma dos d´ıgitos do string s. Por exemplo,
F (“1”) = 1, F (“123”) = 1 + 2 + 3 = 6, F (“1111”) = 1 + 1 + 1 + 1 = 4, etc.
Queremos provar por induc¸a˜o estrutural que C(s) = F (s) para todo s ∈ A.
a) {0, 3 pt} Qual o objetivo de prova do caso base? Resposta: C(“1”) =
F (“1”)
b) {0, 3 pt} Prove o caso base (justifique cada passo de prova com “Def. de
C” ou “Def. de F”).
Resposta:
C(“1”)
= 1 [Def. de C]
= F (“1”) [Def. de F ]
c) {0, 3 pt}Qual o objetivo de prova do passo indutivo? Resposta: C(“1”+s) =
F (“1”+s)
d) {0, 3 pt} Qual a hipo´tese de induc¸a˜o? Resposta: C(s) = F (s)
e) {0, 3 pt} Prove o passo indutivo (justifique cada passo de prova com “Def.
de C”, “Def. de F” ou “Hipo´tese de Induc¸a˜o”).
Resposta:
C(“1”+s)
= 1 + C(s) [Def. de C]
= 1 + F (s) [Hipo´tese de Induc¸a˜o]
= F (“1”+s) [Def. de F ]
2. Seja o conjunto de strings A = {“2”,“22”,“222”, . . .} definido assim:
Caso base. “2” ∈ A.
Caso recursivo. Se s ∈ A, enta˜o “2”+s ∈ A.
Obs1. O s´ımbolo de + acima concatena strings. Exemplo: “2”+“222” = “2222”.
Obs2. Todos elementos de A sa˜o provenientes do passo base e passo recursivo.
Seja C(s) a func¸a˜o que retorna o comprimento do string s.
Por exemplo, C(“2”) = 1, C(“22222”) = 5, etc.
Seja P (s) a func¸a˜o que retorna o produto dos d´ıgitos do string s.
Por exemplo, P (“2”) = 2, P (“222”) = 2 · 2 · 2 = 8.
Queremos provar por induc¸a˜o estrutural que 2C(t) = P (t), para todo t ∈ A.
a) {0, 5 pt} Qual o objetivo de prova do caso base?
Resposta: 2C(“2“) = P (“2“)
b) {0, 5 pt} Prove o caso base (justifique cada passo de prova com “Def. de
C”, “Def. de P” ou “Aritme´tica”).
Resposta:
2C(“2“)
= 21 [Def. de C]
= 2 [Aritme´tica]
= P (“2”) [Def. de P ]
c) {0, 5 pt} Qual o objetivo de prova do passo indutivo?
Resposta: C(“2“+s) = P (“2”+s)
d) {0, 5 pt} Qual a hipo´tese de induc¸a˜o?
Resposta: 2C(s) = P (s)
e) {0, 5 pt} Prove o passo indutivo. Justifique cada passo de prova com
“Hipo´tese de Induc¸a˜o” ou com uma das equac¸o˜es abaixo:
21+n = 2 · 2n [1]
C(“2”+s) = 1 + C(s) [2]
P (“2”+s) = 2 · P (s) [3]
Resposta:
2C(“2“+s)
= 21+C(s) [2]
= 2 · 2C(s) [1]
= 2 · P (s) [Hipo´tese de Induc¸a˜o]
= P (“2”+s) [3]
3. Seja o conjunto de strings contendo programas de computador:
A = {“x = 2 ; ”, “x = 2 ; x = x+ 2 ; ”, “x = 2 ; x = x+2 ; x = x+ 2 ; ”, . . .}
Note que os programas teˆm apenas atribuic¸o˜es. A definic¸a˜o formal e´:
Caso base. “x = 2 ; ” ∈ A.
Passo recursivo. Se s ∈ A, enta˜o (s+ “x = x+ 2 ; ”) ∈ A.
Obs1. O s´ımbolo de + aplicado a s concatena strings. Exemplo: “a”+“bcd” = “abcd”.
O s´ımbolo de + aplicado a x e´ soma aritme´tica.
Obs2. Todos elementos de A sa˜o provenientes do passo base e passo recursivo.
Seja EXEC (s) a func¸a˜o que retorna o valor de x ao te´rmino da execuc¸a˜o do
programa s.
Por exemplo, EXEC (“x = 2 ; ”) = 2, EXEC (“x = 2 ; x = x+ 2 ; ”) = 4, etc.
Seja ATR(s) a func¸a˜o que retorna o nu´mero de atribuic¸o˜es contidos em s.
Por exemplo, ATR(“x = 2 ; ”) = 1, ATR(“x = 2 ; x = x+ 2 ; ”) = 2.
Queremos provar por induc¸a˜o estrutural que EXEC (s) = 2 · ATR(s), para
todo s ∈ A.
a) {0, 5 pt} Qual o objetivo de prova do caso base?
Resposta: EXEC (“x = 2 ; ”) = 2 · ATR(“x = 2 ; ”)
b) {1, 0 pt} Prove o caso base (justifique cada passo de prova com “Def. de
EXEC“, “Def. de ATR” ou “Aritme´tica”).
Resposta:
EXEC(“x = 2 ; ”)
= 2 [Def. de EXEC ]
= 2 · 1 [Aritme´tica]
= 2 · ATR(“x = 2 ; ”) [Def. de ATR]
c) {0, 5 pt} Qual o objetivo de prova do passo indutivo?
Resposta: EXEC (s+ “x = x+ 2 ; ”) = 2 · ATR(s+ “x = x+ 2 ; ”)
d) {0, 5 pt} Qual a hipo´tese de induc¸a˜o?
Resposta: EXEC (s) = 2 · ATR(s)
e) {1, 0 pt} Prove o passo indutivo. Justifique cada passo de prova com
“Aritme´tica”, “Definic¸a˜o de EXEC”, “Definic¸a˜o de ATR”, “Hipo´tese de
Induc¸a˜o” ou com a equac¸o˜es [1] ou [2] abaixo:
EXEC (s+ “x = x+ 2 ; ”) = 2 + EXEC (s) [1]
ATR(s+ “x = x+ 2 ; ”) = 1 + ATR(s) [2]
Resposta:
EXEC (s+ “x = x+ 2 ; ”)
= 2 + EXEC (s) [1]
= 2 + 2 · ATR(s) [Hipote´se de Induc¸a˜o]
= 2(1 + ATR(s)) [Aritme´tica]
= 2(ATR(s+ “x = x+ 2 ; ”) [2]
4. Seja o conjunto de strings de bits A = {“0”,“1”,“01”,“10”, . . .} definido assim:
Passo base 1. “0” ∈ A.
Passo base 2. “1” ∈ A.
Passo recursivo. Se s ∈ A e t ∈ A, enta˜o s+ t ∈ A.
Obs1. O s´ımbolo de + acima concatena strings. Exemplo: “ab”+“cd” = “abcd”.
Obs2. Todos elementos de A sa˜o provenientes dos passos base e passo recursivo.
Seja UNS (s) a func¸a˜o que retorna a quantidade de bits 1 do string s.
Por exemplo, UNS (“0”) = 0, UNS (“1”) = 1, UNS (“010”) = 1, etc.
Seja S(s) a func¸a˜o que retorna a soma dos bits do string s.
Por exemplo, S(“0”) = 0, S(“1”) = 1, S(“0101”) = 2, S(“0101011”) = 4, etc.
Queremos provar por induc¸a˜o estrutural que UNS (t) = S(t), para todo t ∈ A.
a) {0, 5 pt} Quais os objetivos de prova dos casos base?
Resposta: (UNS (“0”) = S (“0”)) e (UNS (“1”) = S (“1”))
b) {1, 0 pt} Prove os casos base (justifique cada passo de prova com “Def. de
UNS”, “Def. de S” ou “Aritme´tica”).
Resposta:
UNS (“0”)
= 0 [Def. de UNS ]
= S(“0”) [Def. de S ]
UNS (“1”)
= 1 [Def. de UNS ]
= S(“1”) [Def. de S ]
c) {0, 5 pt} Qual o objetivo de prova do passo indutivo?
Resposta: UNS (s+ t) = S (s+ t)
d) {0, 5 pt} Quais as hipo´teses de induc¸a˜o?
Resposta: (UNS (s) = S (s)) e (UNS (t) = S (t))
e) {1, 0 pt} Prove o passo indutivo. Justifique cada passo de prova com
“Hipo´tese de Induc¸a˜o” ou com uma das equac¸o˜es abaixo:
UNS (s+ t) = UNS (s) + UNS (t) [1]
S (s+ t) = S (s) + S (t) [2]
Resposta:
UNS (s+ t)
= UNS (s) + UNS (t) [1]
= S (s) + S (t) [Hipo´tese de Induc¸a˜o]
= S (s+ t) [2]
5. Seja A o conjunto definido recursivamente abaixo.
Caso base. 17 ∈ A.
Passo recursivo. Se n ∈ A, enta˜o (n+ n) ∈ A.
Queremos provar por induc¸a˜o estrutural que ∀n ∈ A ( (n mod 17) = 0 ).
a) {0, 5 pt} Qual o objetivo de prova do caso base?
Resposta: 17 mod 17 = 0
b) {1, 0 pt} Prove o caso base (justifique cada passo de prova com “Def. de
mod ” ou “Aritme´tica”).
Resposta:
17 mod 17
= 0 [Def. de mod ]
c) {0, 5 pt} Qual o objetivo de prova do passo indutivo?
Resposta: (n+ n) mod 17 = 0
d) {0, 5 pt} Qual a hipo´tese de induc¸a˜o?
Resposta: n mod 17 = 0
e) {1, 0 pt} Prove o passo indutivo. Justifique cada passo de prova com “Ar-
itme´tica”, “Definic¸a˜o de mod ”, “Hipo´tese de Induc¸a˜o” ou com a equac¸a˜o
[1] abaixo:
((x+ y) mod z) = (((x mod z) + (y mod z)) mod z) [1]
Resposta:
(n+ n) mod 17
= ((n mod 17) + (n mod 17)) mod 17 [1]
= (0 + 0) mod 17 [Hipote´se de Induc¸a˜o (2x)]
= 0 mod 17 [Aritme´tica]
= 0 [Definic¸a˜o de mod ]
6. Seja A definido recursivamente abaixo.
Caso base. 1 ∈ A.
Passo recursivo. Se n ∈ A, enta˜o (n+ 2) ∈ A.
Queremos provar, por induc¸a˜o estrutural, que ∀n ∈ A(((n− 1) mod 2) = 0).
a){0, 5 pt} Qual o objetivo de prova do caso base?
Resposta: ((1− 1) mod 2) = 0
b){0, 5 pt} Prove o caso base. Justifique com “Aritme´tica” ou “Definic¸a˜o de
mod ”.
Resposta:
(1− 1) mod 2
= 0 mod 2 [Aritme´tica]
= 0 [Def. mod ]
c){1, 0 pt} Qual o objetivo de prova do passo indutivo?
Resposta: (((n+ 2)− 1) mod 2) = 0
d){1, 0 pt} Qual a hipo´tese de induc¸a˜o?
Resposta: ((n− 1) mod 2) = 0
e){1, 0 pt} Prove o passo indutivo. Justifique seus passos de prova com “Arit-
me´tica”, “Hipo´tese de Induc¸a˜o”, “Definic¸a˜o de mod ”, “[1]” ou “[2]”,
onde [1] e [2] sa˜o as equac¸o˜es abaixo:
((x+ y) mod z) = (((x mod z) + (y mod z)) mod z) [1]
(((n+ 2)− 1) mod 2) = (((n− 1) + 2) mod 2) [2]
Resposta:
((n+ 2)− 1) mod 2
= ((n− 1) + 2) mod 2 [2]
= (((n− 1) mod 2) + (2 mod 2)) mod 2 [1]
= (0 + (2mod 2)) mod 2 [Hipo´tese de Induc¸a˜o]
= (0 + 0) mod 2 [Definic¸a˜o de mod ]
= 0 [Definic¸a˜o de mod ]
7. Seja A o conjunto de strings definido recursivamente abaixo.
Caso base. “ana” ∈ A.
Passo recursivo. Se s ∈ A, enta˜o s+ s ∈ A.
Obs1. O s´ımbolo de + acima concatena strings. Exemplo: “a”+“bcd” = “abcd”.
Obs2. Todos elementos de A sa˜o provenientes do passo base e passo recursivo.
Seja CONTAA(s) a func¸a˜o que retorna a quantidade de letras “a” do string s.
Por exemplo, CONTAA(“anaanaana”) = 6.
Seja CONTAN (s) a func¸a˜o que retorna a quantidade de letras “n” do string s.
Por exemplo, CONTAN(“anaanaana”) = 3.
Queremos provar por induc¸a˜o estrutural que CONTAA(s) = 2 ·CONTAN (s),
para todo s ∈ A.
a) {0, 5 pt} Qual o objetivo de prova do caso base?
Resposta: CONTAA(“ana”) = 2 · CONTAN (“ana”)
b) {1, 0 pt} Prove o caso base. Justifique cada passo de prova com “Def. de
CONTAA“, “Def. de CONTAN ” ou “Aritme´tica”.
Resposta:
CONTAA(“ana”)
= 2 [Def. de CONTAA]
= 2 · 1 [Aritme´tica]
= 2 · CONTAN (“ana”) [Def. de CONTAN ]
c) {0, 5 pt} Qual o objetivo de prova do passo indutivo?
Resposta: CONTAA(s+ s) = 2 · CONTAN (s+ s)
d) {0, 5 pt} Qual a hipo´tese de induc¸a˜o?
Resposta: CONTAA(s) = 2 · CONTAN (s)
e) {1, 0 pt} Prove o passo indutivo. Justifique cada passo de prova com “Ar-
itme´tica”, “Definic¸a˜o de CONTAA”, “Definic¸a˜o de CONTAN ”, “Hipo´tese
de Induc¸a˜o” ou com as equac¸o˜es [1] ou [2] abaixo:
CONTAA(s+ s) = CONTAA(s) + CONTAA(s) [1]
CONTAN (s+ s) = CONTAN (s) + CONTAN (s) [2]
Resposta:
CONTAA(s+ s)
= CONTAA(s) + CONTAA(s) [1]
= 2 · CONTAN (s) + 2 · CONTAN (s) [Hipo´tese de Induc¸a˜o (2x)]
= 2(CONTAN (s) + CONTAN (s)) [Aritme´tica]
= 2CONTAN (s+ s) [2]
8. Seja A o conjunto definido recursivamente abaixo.
Caso base. 2 ∈ A.
Passo recursivo. Se n ∈ A, enta˜o n2 ∈ A.
Obs. Todos elementos de A sa˜o provenientes do passo base e passo recursivo.
Queremos provar por induc¸a˜o estrutural que ((n mod 2) = 0), para todo
n ∈ A.
a){0, 5 pt} Qual o objetivo de prova do caso base?
Resposta: (2 mod 2) = 0.
b){0, 5 pt} Prove o caso base. Justifique cada passo com “Aritime´tica” ou
“Definic¸a˜o de mod ”.
Resposta:
(2 mod 2)
= 0 [Definic¸a˜o de mod ]
c){1, 0 pt} Qual o objetivo de prova do passo indutivo?
Resposta:
(n2 mod 2) = 0
d){1, 0 pt} Qual a hipo´tese de induc¸a˜o?
Resposta:
(n mod 2) = 0
e){1, 0 pt} Prove o passo indutivo. Justifique seus passos de prova com “Arit-
me´tica”, “Definic¸a˜o de mod ”, “Hipo´tese de Induc¸a˜o” ou “[1]”, onde [1]
e´ a equac¸a˜o abaixo:
((x · y) mod z) = ( ((x mod z) · (y mod z)) mod z ) [1]
Resposta:
n2 mod 2
= (n · n) mod 2 [Aritme´tica]
= ((n mod 2) · (n mod 2)) mod 2 [1]
= (0 · (n mod 2)) mod 2 [Hipo´tese de Induc¸a˜o]
= 0 mod 2 [Aritme´tica]
= 0 [Definic¸a˜o de mod ]
5 Relac¸o˜es
1. {2 pt} Seja R uma relac¸a˜o em A = {a, b, c, d} dada por
R = {(a, d), (b, a), (b, c), (c, a), (c, d), (d, c)}.
Utilize matrizes para calcular o fecho transitivo de R.
Resposta:
Assumindo que a linha e a coluna representam os ve´rtices a, b, c e d (nesta
ordem):
MR =


0 0 0 1
1 0 1 0
1 0 0 1
0 0 1 0

 MR∗ =


1 0 1 1
1 0 1 1
1 0 1 1
1 0 1 1


A fo´rmula e´ Mr ∨ (Mr �Mr) ∨ (Mr �Mr �Mr) ∨ (Mr �Mr �Mr �Mr).
2. Seja R uma relac¸a˜o em A = {1, 2, 3, 4} definida por:
R = {(1, 2), (2, 1), (3, 1), (4, 2), (4, 3)}.
Defina:
a) {1, 0 pt} O fecho reflexivo de R;
Resposta: R′ = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (3, 3), (4, 2), (4, 3), (4, 4)}.
b) {1, 0 pt} O fecho sime´trico de R;
Resposta: R’ = {(1, 2), (1, 3), (2, 1), (2, 4), (3, 1), (3, 4), (4, 2), (4, 3)}.
c) {2, 0 pt} O fecho transitivo de R; Utilize matrizes e mostre seus ca´lculos.
Resposta:
MR∗ =


1 1 0 0
1 1 0 0
1 1 0 0
1 1 1 0

R′ = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
3. {2, 0 pt} Seja R uma relac¸a˜o em A = {1, 2, 3, 4} definida por
R = {(2, 1), (2, 3), (3, 1), (3, 4), (4, 1), (4, 3)}
Utilize matrizes para calcular o fecho transitivo de R.
Resposta:
MR∗ =


0 0 0 0
1 0 1 1
1 0 1 1
1 0 1 1


4. Sejam B = {1, 2, 3} e R = {(1, 1), (1, 2), (2, 1)} uma relac¸a˜o em B.
a) {0, 25 pt} Defina o fecho reflexivo de R.
Resposta: {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}
b) {0, 25 pt} Defina o fecho sime´trico de R.
Resposta: {(1, 1), (1, 2), (2, 1)}
5. {2 pt} Sejam A = {1, 2, 3} e R = {(1, 2), (2, 1), (1, 3)} uma relac¸a˜o em A.
Calcule a matriz MR∗ que representa o fecho transitivo de R.
Resposta:
MR =

0 1 11 0 0
0 0 0


MR◦R =

0 1 11 0 0
0 0 0

�

0 1 11 0 0
0 0 0

 =

1 0 00 1 1
0 0 0


M(R◦R)◦R =

1 0 00 1 1
0 0 0

�

0 1 11 0 0
0 0 0

 =

0 1 11 0 0
0 0 0


MR∗ =MR ∨MR◦R ∨M(R◦R)◦R =

1 1 11 1 1
0 0 0


6. Seja A = {1, 2, 3, 4}.
a) {1, 0 pt} Defina uma relac¸a˜o em A que seja reflexiva, sime´trica e antis-
sime´trica simultaneamente.
Resposta: {(1, 1), (2, 2), (3, 3), (4, 4)}
b) {1, 0 pt} Defina uma relac¸a˜o em A que seja irreflexiva e sime´trica simul-
taneamente.
Resposta: {(2, 1), (1, 2)}
c) {1, 0 pt} Defina uma relac¸a˜o em A que seja irreflexiva e assime´trica simul-
taneamente.
Resposta: {(2, 1)}
7. A empresa Golac¸o oferece voos (Recife,Aracaju), (Aracaju, Joa˜o Pessoa) e
(Joa˜o Pessoa, Recife).
a){2, 0 pt} Calcule o fecho transitivo desta relac¸a˜o usando matrizes. Exiba
seus ca´lculos. Fac¸a uma matriz com linha e coluna representando Recife,
Aracaju e Joa˜o Pessoa (nesta ordem).
Resposta: Assumindo linha e coluna na ordem Recife, Aracaju e Joa˜o
Pessoa.
MR =

0 1 00 0 1
1 0 0


MR◦R =

0 1 00 0 1
1 0 0

�

0 1 00 0 1
1 0 0

 =

0 0 11 0 0
0 1 0


M(R◦R)◦R =

0 0 11 0 0
0 1 0

�

0 1 00 0 1
1 0 0

 =

1 0 00 1 0
0 0 1


MR∗ =MR ∨MR◦R ∨M(R◦R)◦R =

1 1 11 1 1
1 1 1


b){0, 5 pt} Baseado na matriz do fecho transitivo, liste os pares de voos
poss´ıveis com a Golac¸o (incluindo voos com escalas).
Resposta: (Recife, Recife), (Recife, Aracaju), (Recife, Joa˜o Pessoa),
(Aracaju, Recife), (Aracaju, Aracaju), (Aracaju, Joa˜o Pessoa), (Joa˜o
Pessoa, Recife), (Joa˜o Pessoa, Aracaju), (Joa˜o Pessoa, Joa˜o Pessoa),
8. Seja A = {1, 2, 3, 4}.
{1, 0 pt} Defina uma relac¸a˜o R1 em A que seja reflexiva.
Resposta: R1 = {(1, 1), (2, 2), (3, 3), (4, 4)}.
Obs. R1 e´ reflexiva, antissime´trica e transitiva e serviria como resposta a
todas as letras a), b) e c).
{1, 0 pt} Defina uma relac¸a˜o R2 em A que seja reflexiva e antissime´trica.
Resposta: R2 = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (3, 4)}.
{1, 0 pt} Defina uma relac¸a`o R3 em A que seja reflexiva, antissime´tria e
transitiva.
Resposta: R3 = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 3), (1, 3)}.
9. Seja PESSOAS = {Joa˜o,Maria,Raimundo,Teresa}.
a){0, 5 pt} Liste os pares da relac¸a˜o R = {(a, b) | a amava b} em PESSOAS
baseado no texto de Drummond: “Joa˜o amava Teresa que amava Raimundo
que amava Maria.”
Resposta:
R = {(Joa˜o,Teresa), (Teresa,Raimundo), (Raimundo,Maria)}
b){0, 5 pt} A relac¸a˜o R e´ transitiva? Justifique sua resposta.
Resposta: A relac¸a˜o na˜o e´ transitiva. Justificativa: Joa˜o amava Teresa
e Teresa amava Raimundo, mas Joa˜o na˜o amava Raimundo.
c){1, 0 pt} Utilize matrizes para calcular o fecho transitivo. Fac¸a uma matriz
com linha e coluna representando Joa˜o, Maria, Raimundo e Teresa (nesta
ordem).
Resposta:
MR =


0 0 0 1
0 0 0 0
0 1 0 0
0 0 1 0


MR◦R =


0 0 0 1
0 0 0 0
0 1 0 0
0 0 1 0

�


0 0 0 1
0 0 0 0
0 1 0 0
0 0 1 0

 =


0 0 1 0
0 0 0 0
0 0 0 0
0 1 0 0


M(R◦R)◦R =


0 0 1 0
0 0 0 0
0 0 0 0
0 1 0 0

�


0 0 0 1
0 0 0 0
0 1 0 0
0 0 1 0

 =


0 1 0 0
0 0 0 0
0 0 0 0
0 0 0 0


M((R◦R)◦R)◦R =


0 1 0 0
0 0 0 0
0 0 0 0
0 0 0 0

�


0 0 0 1
0 0 0 0
0 1 0 0
0 0 1 0

 =


0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0


MR∗ =MR ∨MR◦R ∨M(R◦R)◦R ∨M((R◦R)◦R)◦R =


0 1 1 1
0 0 0 0
0 1 0 0
0 1 1 0


d){0, 5 pt} Liste os pares que compo˜em o fecho transitivo.
Resposta:
R∗ = {(Joa˜o,Maria),
(Joa˜o,Raimundo),
(Joa˜o,Teresa),
(Raimundo,Maria),

Outros materiais