2ª Lista de Matemática Discreta
Métodos de prova
Exercício 1. Enuncie precisamente cada proposição, incluindo o domínio das variáveis, e dê uma
prova direta para:
1. se a divide b e a divide c então a divide b + c.
2. se a divide b e b divide c então a divide c.
√
3. se a > 0 é composto então a tem um fator primo p com 1 < p ≤
a.
4. se mdc(a, b) > 1 então mdc(a2 , b2 ) > 1.
Exercício 2. Enuncie precisamente cada proposição, incluindo o domínio das variáveis, e prove pela
contra-positiva:
√
1. se n não tem divisor primo d com 1 < d ≤ n então n é primo.
2. se 3n + 2 é ímpar então n é ímpar.
3. se c5 + 7 é par, então c é ímpar.
Exercício 3. Prove que n2 + 1 > 2n sempre que n é um inteiro tomado em {1, 2, 3, 4}.
Exercício 4. Para números reais x e y usamos max{x, y} para denotar o maior deles e usamos min{x, y}
para denotar o menor deles. Prove que max{x, y} + min{x, y} = x + y.
Exercício 5 (desigualdade triangular). Prove que para todo x ∈ R, para todo y ∈ R, |x + y| ≤ |x| + |y|.
Exercício 6. Enuncie precisamente cada proposição, incluindo o domínio das variáveis, prove por
contradição:
1. se a não divide bc, então a não divide b.
2. se 3n + 2 é ímpar então n é ímpar.
√
3. 3 3 não é racional.
Exercício 7. Leia com atenção o seguinte teorema e uma suposta demonstração.
Teorema 1. Para todos a, b, c, d números naturais, se c divide a e c divide b e d divide a e d divide b e
c não divide d, então dc divide a e dc divide b.
Demonstração. Sejam a, b, c, d números naturais tais que c divide a, c divide b, d divide a, d divide b
e c não divide d.
Se d divide a e b, então existem x e y naturais tais que a = xd e b = yd.
Se c divide a então c divide xd.
Se c divide xd e não divide d, então c divide x.
Analogamente, se c divide b então c divide yd.
Se c divide yd e não divide d, então c divide y.
Se c divide x e y, então existem z e w tais que x = cz e y = cw.
Das conclusões acima temos a = xd = (cz)d = (dc)z e b = yd = (cw)d = (dc)w, portanto, dc divide a
e dc divide b.
(a) Dê um contraexemplo para a afirmação feita no teorema.
(b) Indique o(s) erro(s) na demonstração.
1
Exercício 8. Nesse exercício assuma que todas as variáveis têm mesmo domínio e vamos omiti-lo.
Onde está o erro da seguinte suposta demonstração.
Teorema 2. (existe x, P(x)) e (existe x, Q(x)) → existe x, (P(x) e Q(x)) .
Demonstração.
(∃x, P(x)) e (∃x, Q(x))
premissa
((∃x, P(x)) e (∃x, Q(x))) → (∃x, P(x)) por simplificacao
(∃x, P(x)) → P(c)
por instanciacao existencial
de modo que ((∃x, P(x)) e (∃x, Q(x))) → P(c).
Analogamente, a mesma estratégia prova que ((∃x, P(x)) e (∃x, Q(x))) → Q(c) (escreva a prova).
Portanto
((∃x, Q(x)) e (∃x, Q(x))) → P(c) e Q(c)
e por generalização existencial
∃x, (P(x) e Q(x)) .
Exercício 9. Dizem que nos seus primeiros anos
√ de Hogwarts, Harry Potter resolveu usar seus poderes para escrever uma prova análoga de que 4 não é racional, coisa que quase todo mundo sabe que
não é. A prova de Harry Potter foi a seguinte:
√
Teorema 3. 4 não é racional.
√
Demonstração. Se 4 é então existem a, b ∈ N∗ , primos entre si, com a > 4, tais que
a √
= 4.
b
Elevando os dois termos da equação ao quadrado, temos
a2 = 4b2
Logo a2 é divisível por 4 e, portanto, a também o é. Por definição,podemos escrever a = 4k, para
algum k ∈ N, e ficamos com
(4k)2 = 4b2
e, portanto
ou seja
16k 2 = 4b2 ,
b2 = 4k 2 .
Logo b2 é √
divisível por 4 e, portanto, b também o é, o que contraria a escolha de a e b primos entre si.
Portanto, 4 não é racional.
Onde está a mágica?
Exercício 10. Prove que existe um raciona x e um irracional y tais que x y é irracional.
Exercício 11 (Quantificador de unicidade: ∃!). A proposição (∃!x)P(x) indica que existe um único
2
x no domínio do discurso tal que P(x) é verdadeiro. Por exemplo, (∀n ∈ N)(∃!m ∈ N)nm = n é
verdadeiro pois somente o número 1 tem a propriedade de que qualquer outro natural x vezes ele
resulta em x.
Prove que
(∃!x)P(x) ⇔ (∃x) P(x) e (∀y)(P(y) → x = y) .
(1)
Exercício 12. Prove que (∀r < Q)(∃!n ∈ Z)|r − n| < 12 .(Dica: use (1) mostre que existe n e depois mostre
que para qualquer m com a mesma propriedade m = n. Nesse último passo pode ser preciso usar a
desigualdade triangular)
Exercício 13. Considere o predicado sobre os números naturais P(n) : “Se n > 1 então n2 > n”. Prove
P(0). Em que método de prova se encaixa sua demonstração?
Exercício 14. Seja P(n) um predicado a respeito do natural n e seja n0 um número natural fixo. Prove:
Se P(n0 ) é verdade e (P(n0 ) e P(n0 + 1) e · · · e P(k)) → P(k + 1) é verdade para todo k ≥ n0 , então a
sentença P(n) é verdadeira para todo n ≥ n0 .
Exercício 15. Prove usando indução que:
1. para todo n ≥ 1, 9 + 9 · 10 + 9 · 102 + · · · + 9 · 10n−1 = 10n − 1.
2. Desigualdade de Bernoulli: para todo n ≥ 2, (1 + a)n > 1 + na, para todo real a > −1 não nulo.
3. Desigualdade de Bernoulli: para todo n ≥ 0, (1 + a)n ≥ 1 + na, para todo real a > −1.
4. para todo n ≥ 1, 1/(1 · 2) + 1/(2 · 3) + · · · + 1/(n · n + 1) = 1 − 1/(n + 1).
5. para todo n ≥ 3, ((n + 1)/n)n < n.
6. para todo n ≥ 1, (1 + 1/1)(1 + 1/2) · · · (1 + 1/n) ≤ n + 1
7. para todo n ≥ 1, an < 1 para todo 0 ≤ a < 1
8. para todo n ≥ 1,
1 · 3 · · · (2n − 1)
1
1
≤
≤√
2n
2 · 4 · · · (2n)
n+1
9. para todo n ≥ 1, Se x1 , x2 , . . . , xn são números reais então
|x1 + x2 + · · · xn | ≤ |x1 | + |x2 | + · · · |xn |
Exercício 16. Ache uma falha na seguinte prova por indução de que todos os marcianos são da mesma
cor. Vamos provar por indução sobre o número de marcianos em Marte. (não vale contestar a existência de marcianos)
Base. Se o número de marcianos é 1, todos os marcianos são da mesma cor.
Passo. Suponha que existem n marcianos numerados de 1 até n. Removendo um marciano m ∈
{1, . . . , n} de Marte temos, pela hipótese do passo indutivo, que os n − 1 marcianos restantes são
da mesma cor. Resta descobrir a cor do marciano m. Removendo um marciano ` ∈ {1, . . . , n}
com ` , m temos, pelo mesmo motivo, que os marcianos restantes, inclusive m, são da mesma
cor. Portanto, todos os marcianos 1, . . . , n são da mesma cor.
3
Exercício 17. Qual a falha na seguinte prova de 6n = 0 para todo n ≥ 0.
Base. Se n = 0 então 6n = 0.
Passo. Suponha que 6k = 0 para todo 0 ≤ k < n. Tome a, b < n números naturais tais que n = a + b.
Portanto, 6n = 6a + 6b e pela hipótese indutiva 6a = 0 e 6b = 0, logo 6n = 0.
Exercício 18. Para todo natural n, mostre que uma grade de quadrados 2n × 2n com qualquer um de
seus quadrados removidos pode ser coberta por ladrilhos de tamanho fixo em forma de L (conforme
Figura 1(a)).
(a)
(b)
Figura 1: (a) Ladrilho em L. (b) Grade de quadrados 22 × 22 .
Exercício 19 (Variante do Princípio de Indução). Seja P(n) um predicado sobre os naturais e n0 um
natural. Prove:
Se
1. P(n0 ), P(n0 + 1), . . . , p(n0 + (m − 1)) verdadeiros,
2. para todo k ≥ n0 , P(k) → P(k + m) é verdadeiro,
então para todo n ≥ n0 , P(n) é verdadeiro.
Exercício 20. Prove usando indução que qualquer valor maior ou igual a oito pode ser obtido com
cédulas de 5 e 3 reais.
Exercício 21. Prove usando indução que todo número natural não-nulo pode ser expresso como soma
de potências distintas de 2
Exercício 22. Mostre que se n > 3 pontos distintos sobre um círculo são conectados consecutivamente
com segmentos de reta, então a soma dos ângulos internos do polígono resultante é (n − 2)180.
Exercício 23. Num conjunto de 2n moedas de ouro temos uma que é falsa, ou seja pesa menos que
as outras. Mostrar, por indução, que e possível achar a moeda falsa com n pesagens usando uma
balança de dois pratos sem usar peso.
Exercício 24. Mostre que o Princípio da Boa-ordenação implica o Princípio da Indução.
Exercício 25 (Variante do Princípio de Indução). Seja P(n) um predicado sobre os naturais. Prove:
Se
1. P(n) é verdadeiro para todo n potência de 2,
2. para todo k, P(k + 1) → P(k) é verdadeiro,
então para todo n, P(n) é verdadeiro.
4