1-85

1.6  Introdução a Demonstrações   85

matemática, que pode ser usada para demonstrar resultados que valem para todos os inteiros
positivos. No Capítulo 5, vamos introduzir a noção de demonstrações combinatórias.
Nesta seção, introduzimos muitos métodos para demonstrar teoremas da forma ∀x (P (x) →
Q (x)), incluindo demonstrações diretas e demonstrações por contraposição. Existem muitos teore-
mas desse tipo que têm suas demonstrações facilmente construídas pelo método direto através de
hipóteses e definições de termos do teorema. No entanto, é freqüentemente difícil demonstrar um
teorema sem utilizar uma demonstração por contraposição ou uma demonstração por contradição,
ou alguma outra técnica de demonstração. Na Seção 1.7, vamos direcionar estratégias de demons-
trações. Vamos descrever várias possibilidades que podem ser usadas para encontrar demonstrações
quando o método direto não funciona. Construir demonstrações é uma arte que só pode ser apren-
dida através da experiência, incluindo escrever demonstrações, ter uma demonstração sua criticada
e ler e analisar demonstrações.

Exercícios
1. Use uma demonstração direta para mostrar que a soma de a) uma demonstração por contraposição.
dois números inteiros ímpares é par. b) uma demonstração por contradição.
2. Use uma demonstração direta para mostrar que a soma de 19. Demonstre a proposição P (0), em que P (n) é a proposição
dois números inteiros pares é par. “Se n é um número inteiro positivo maior que 1, então
3. Mostre que o quadrado de um número par é um número n2 > n”. Qual tipo de demonstração você utilizou?
par, usando a demonstração direta. 20. Demonstre a proposição P (1), em que P (n) é a proposição
4. Mostre que o inverso aditivo, ou negativo, de um número “Se n é um número inteiro positivo, então n2 ≥ n”. Qual
par é um número par, usando a demonstração direta. tipo de demonstração você utilizou?
5. Demonstre que se m + n e n + p são números inteiros 21. Assuma P (n) como a proposição “Se a e b são números
pares, em que m, n e p são números inteiros, então m + p reais positivos, então (a + b)n ≥ an + bn”. Comprove que
é par. Que tipo de demonstração você utilizou? P (1) é verdadeira. Qual tipo de demonstração você
6. Use uma demonstração direta para mostrar que o produto utilizou?
de dois números ímpares é ímpar. 22. Mostre que se você pegar 3 meias de uma gaveta, com
7. Use uma demonstração direta para mostrar que todo apenas meias azuis e pretas, você deve pegar ou um par de
número inteiro ímpar é a diferença de dois quadrados. meias azuis ou um par de meias pretas.
8. Demonstre que se n é um quadrado perfeito, então n + 2 23. Mostre que pelo menos 10 de quaisquer 64 dias escolhidos
não é um quadrado perfeito. devem cair no mesmo dia da semana.
9. Use um demonstração por contradição para provar que a 24. Mostre que pelo menos 3 de quaisquer 25 dias escolhidos
soma de um número irracional e um racional é irracional. devem cair no mesmo mês do ano.
10. Use uma demonstração direta para mostrar que o produto 25. Use uma demonstração por contradição para mostrar que
de dois números racionais é racional. não há um número racional r para que r3 + r + 1 = 0.
[Dica: Assuma que r = a/b seja uma raiz, em que a e b são
11. Demonstre ou contrarie que o produto de dois números
números inteiros e a/b é o menor termo. Obtenha uma
irracionais é irracional.
equação que envolva números inteiros, multiplicando-os
12. Demonstre ou contrarie que o produto de um número racio- por b3. Então, veja se a e b são pares ou ímpares.]
nal diferente de zero e um número irracional é irracional.
26. Demonstre que se n é um número inteiro positivo, então n
13. Demonstre que se x é irracional, então 1/x é irracional. é par se e somente se 7n + 4 for par.
14. Demonstre que se x é racional e x  0, então 1/x é racional. 27. Demonstre que se n é um número inteiro positivo, então n
15. Use uma demonstração por contraposição para mostrar que se é ímpar se e somente se 5n + 6 for ímpar.
x + y ≥ 2, em que x e y são números reais, então x ≥ 1 ou y ≥ 1. 28. Demonstre que m2 = n2 se e somente se m = n ou m = −n.
☞ 16. Demonstre que se m e n são números inteiros e mn é par, 29. Demonstre ou contrarie que se m e n são números inteiros, tal
então m é par ou n é par. que mn = 1, então ou m = 1 e n = 1, ou m = −1 e n = −1.
17. Mostre que se n é um número inteiro e n3 + 5 é ímpar, 30. Mostre que essas três proposições são equivalentes, em que a
então n é par, usando: e b são números reais: (i) a é menor que b, (ii) a média de a e
a) uma demonstração por contraposição. b é maior que a, e (iii) a média de a e b é menor que b.
b) uma demonstração por contradição. 31. Mostre que essas proposições sobre o número inteiro x
18. Demonstre que se n é um número inteiro e 3n + 2 é par, são equivalentes: (i) 3x + 2 é par, (ii) x + 5 é ímpar, (iii)
então n é par, usando: x2 é par.
86  1 / Os Fundamentos: Lógica e Demonstrações 1-86

32. Mostre que essas proposições sobre o número real x são 37. Mostre que as proposições p1, p2, p3, p4 e p5 podem ser
equivalentes: (i) x é racional, (ii) x/2 é racional, e (iii) 3x − 1 equivalentes, demonstrando que as proposições condicionais
é racional. p1 → p4, p3 → p1, p4 → p2, p2 → p5 e p5 → p3 são
33. Mostre que essas proposições sobre o número real x são verdadeiras.
equivalentes: (i) x é irracional, (ii) 3x + 2 é irracional, (iii) 38. Encontre um contra-exemplo para a proposição: todo
x/2 é irracional. número inteiro positivo pode ser escrito como a soma dos
34. Esta é a razão para encontrar as soluções da equação quadrados de três números inteiros.
2 x 2 - 1 = x correta? (1) 2 x 2 - 1 = x é dado; (2) 2x2 39. Comprove que pelo menos um dos números reais a1, a2,
− 1 = x2, obtido pelo quadrado dos dois lados de (1); (3) x2 . . . , an é maior que ou igual ao valor da média desses
− 1 = 0, obtido pela subtração de x2 dos dois lados de (2); números. Que tipo de demonstração você utilizou?
(4) (x − 1)(x + 1) = 0, obtido pela fatoração do lado
esquerdo de x2 − 1; (5) x = 1 ou x = −1, confirmado, pois 40. Use o Exercício 39 para mostrar que se os primeiros 10
ab = 0 implica que a = 0 ou b = 0. números inteiros positivos forem colocados em círculo, em
qualquer ordem, haverá três números inteiros, em localização
35. Os passos abaixo para encontrar as soluções de x + 3 = 3
consecutiva no círculo, que terão uma soma maior que ou
− x são corretos? (1) x + 3 = 3 − x é dado; (2) x + 3 =
x2 − 6x + 9, obtido tirando a raiz quadrada dos dois lados de igual a 17.
(1); (3) 0 = x2 − 7x + 6, obtido pela subtração de x + 3 dos 41. Comprove que se n é um número inteiro, estas quatro
dois lados de (2); (4) 0 = (x − 1)(x − 6), obtido pela fatoração proposições são equivalentes: (i) n é par, (ii) n + 1 é ímpar,
do lado direito de (3); (5) x = 1 ou x = 6, tirado de (4) (iii) 3n + 1 é ímpar, (iv) 3n é par.
porque ab = 0 implica que a = 0 ou b = 0. 42. Comprove que estas quatro proposições sobre o número
36. Comprove que as proposições p1, p2, p3 e p4 podem ser inteiro n são equivalentes: (i) n2 é ímpar, (ii) 1 − n é par, (iii)
equivalentes mostrando que p1 ↔ p4, p2 ↔ p3 e p1 ↔ p3. n3 é ímpar, (iv) n2 + 1 é par.

1.7   Métodos de Demonstração e Estratégia

Introdução
Auto- Na Seção 1.6 introduzimos uma variedade de métodos de demonstrações e ilustramos como cada
avaliação método pode ser usado. Nesta seção vamos continuar neste esforço. Vamos introduzir muitos
outros importantes métodos de demonstrações, incluindo demonstrações em que consideramos
diferentes casos separadamente e demonstrações em que comprovamos a existência de objetos
com determinada propriedade desejada.
Na Seção 1.6 apenas discutimos brevemente a estratégia por trás da construção das demons-
trações. Essa estratégia inclui a seleção de um método de demonstrações e então a construção
com sucesso de um argumento passo a passo, com base nesse método. Nesta seção, depois que
tivermos desenvolvido um grande arsenal de métodos de demonstração, vamos estudar alguns
aspectos adicionais da arte e da ciência das demonstrações. Vamos prover avanços em como en-
contrar demonstrações trabalhando de trás para frente e adaptando demonstrações existentes.
Quando matemáticos trabalham, eles formulam conjecturas e tentam comprová-las ou ten-
tam encontrar um contra-exemplo. Vamos brevemente descrever esse processo aqui, comprovan-
do resultados sobre ladrilhar tabuleiros de xadrez com dominós ou outros tipos de peças.
Olhando para esse método de ladrilhar, podemos ser capazes de rapidamente formular conjectu-
ras e comprovar teoremas sem que tenhamos desenvolvido uma teoria.
Vamos concluir a seção discutindo o papel das questões abertas. Em particular, vamos discu-
tir alguns problemas interessantes que apenas foram resolvidos depois de permanecerem abertos
por centenas de anos ou porque ainda estão abertos.

Demonstração por Exaustão e Demonstração por Casos

Algumas vezes, não podemos comprovar um teorema usando um único argumento que satisfaça
todos os casos possíveis. Vamos agora introduzir um método que pode ser usado para comprovar