Em matemática, uma prova= demonstração é uma argumentação que procura convencer o leitor de que uma certa uma proposição= afirmação previamente enunciada, está correta. Em outras palavras, uma prova é uma narrativa que ajuda o leitor a entender por que uma dada proposição é verdadeira.
Em geral, as proposições têm a forma
se A então B
,
sendo A a hipótese
e B a tese da proposição.
Mas às vezes a hipótese não é dada explicitamente.
Qual a estrutura de uma prova? Uma prova é um texto, escrito em língua natural (português, ou inglês, ou russo, ou chinês, etc.), que consiste em uma sequência de sentenças gramaticalmente completas. Mais precisamente, uma prova é uma sequência de afirmações em que cada afirmação decorre logicamente das anteriores. A primeira afirmação é a hipótese da proposição e a última afirmação é a tese.
? | ? | 1 | 2 | B |
? | ? | 2 | 3 | B |
? | ? | 3 | B | 2 |
? | ? | B | 2 | 1 |
? | ? | 2 | 1 | 0 |
? | ? | 3 | 1 | 0 |
2 | B | B | 1 | 0 |
 1  | 2 | 2 | 1 | 0 |
Considere a configuração do jogo
Minesweeper
à direita.
Cada B
representa uma bomba.
As posições em branco não têm bombas
e as posições marcadas com ?
podem ou não ter bombas.
Uma posição marcada com um número k
não tem bomba mas é vizinha de exatamente k bombas.
(Cada posição tem até 8 vizinhos:
ao norte, a nordeste, a leste, … , a noroeste.)
Nosso problema é decidir se uma dada posição
?
tem uma bomba ou não.
Cada posição do tabuleiro é especificada por suas coordenadas. Assim, por exemplo, o extremo superior esquerdo do tabuleiro tem coordenadas (1,1) e o cruzamento da primeira linha com a segunda coluna tem coordenadas (1,2).
Proposição: A posição (1,2) da configuração da figura não tem bomba.
Prova, por contradição:
Suponha, por um momento, que há uma bomba em (1,2).
A posição (2,3) é vizinha de duas bombas e há uma bomba em (3,4).
Logo, as posições (2,2) e (3,2) não têm bomba alguma.
Portanto, o 3
na posição (3,3) garante que há uma bomba em (4,2).
Agora, o 2
na posição (5,3) garante que não há bomba em (5,2)
nem em (6,2).
Mas isso é inconsistente com o 3
na posição (6,3).
Esta contradição mostra que (1,2) não pode ter uma bomba.
Proposição: Não existem números inteiros positivos p e q tais que p/q = √. Em outras palavras, a raiz quadrada de 2 é irracional.
Prova, por contradição:
Suponha que existem números inteiros positivos p e q tais que (p/q)2 = 2.
Escolha p e q de modo que eles não tenham divisor comum.
Portanto, não existe número inteiro maior que 1 que divida tanto p quanto q.
O número p2 é par, pois p2 = 2q2.
O número p é par, pois o produto de quaisquer dois números ímpares é ímpar.
Seja s o número inteiro p/2.
O número q2 é par, pois q2 = p2/2 = (2s)2/2 = 2s2.
O número q é par, pois o produto de dois ímpares é ímpar.
Os números p e q são divisíveis por 2.
Isso contradiz a maneira como escolhemos p e q.
A contradição mostra que a raiz quadrada de 2 é irracional.
Proposição: Se n é um número inteiro positivo então 12 + 22 + 32 + ··· + n2 = n (n+1) (2n+1) / 6.
Prova, por indução em n:
Suponha que n = 1 (esta é a base da indução).
Nesse caso, os dois lados da identidade valem 1 e portanto são iguais.
Suponha agora que n > 1 (aqui começa o passo da indução).
Por hipótese de indução, 12 + 22 + ··· + (n−1)2 = (n−1) n (2n−1) / 6.
Portanto, 12 + 22 + ··· + n2 =
xxxxxxxxxxxx = 12 + 22 + ··· + (n−1)2 + n2
xxxxxxxxxxxx = ((n−1) n (2n−1)/6) + n2
xxxxxxxxxxxx = (n/6) ((n−1) (2n−1) + 6n)
xxxxxxxxxxxx = (n/6) (2n2 − 3n + 1 + 6n)
xxxxxxxxxxxx = (n/6) (2n2 + 3n + 1)
xxxxxxxxxxxx = (n/6) (n+1) (2n+1)
xxxxxxxxxxxx = n (n+1) (2n+1)/6,
como queríamos demonstrar.
Mau exemplo. Veja uma maneira feia de organizar a indução. Ela é feia porque vai na direção errada, de n+1 para n, e assim termina com uma expressão que não é idêntica à tese.
Suponha que n = 1 (esta é a base da indução).
Então os dois lados da identidade valem 1 e portanto são iguais.
Suponha agora que a identidade vale para n (aqui começa o passo da indução).
Vamos provar a identidade para n+1:
xx 12 + 22 + ··· + n2 + (n+1)2 =
xxxxxxxx = n (n+1) (2n+1)/6 + (n+1)2
xxxxxxxx = ((n+1)/6) (n(2n+1) + 6(n+1))
xxxxxxxx = ((n+1)/6) (2n2 + 7n + 6)
xxxxxxxx = ((n+1)/6) (n+2) (2n+3)
xxxxxxxx = (n+1) (n+2) (2(n+1)+1))/6.
O grau de um vértice v num grafo é o número de arestas que têm ponta v. O grau de um vértice v é denotado por g(v).
Proposição: Em qualquer grafo, a soma dos graus dos vértices é igual ao dobro do número de arestas. Em outras palavras, se (V, E) é um grafo então ∑ v∈V g(v) = 2 ∣E∣.
Prova, por indução em ∣E∣:
Base da indução: ∣E∣ = 0.
Nesse caso, ∑ g(v) = 0, e portanto ∑ g(v) = 2 ∣E∣.
Passo da indução: ∣E∣ > 0.
Suponha que a identidade vale em todo subgrafo próprio de (V, E) (esta é a hipótese de indução).
Seja xy uma aresta do grafo.
Seja F o conjunto E − {xy}.
Seja g′(v) o grau de v no grafo (V, F).
Por hipótese de indução, ∑ g′(v) = 2 ∣F∣.
Temos g(x) = 1 + g′(x), g(y) = 1 + g′(y) e g(v) = g′(v) para todo v diferente de x e y.
Portanto, ∑ g(v) = 1 + 1 + ∑ g′(v) = 2 + 2 ∣F∣.
Mas 2 + 2 ∣F∣ = 2 ∣E∣.
Portanto, ∑ g(v) = 2 ∣E∣, como queríamos demonstrar.
Errado. Eis uma versão errada da indução. Ela supõe a tese e acrescenta uma aresta ao grafo em vez de tirar uma.
Base da indução: ∣E∣ = 0.
Então ∑ g(v) = 0, e portanto ∑ g(v) = 2 ∣E∣.
Passo da indução: suponha que ∑ g(v) = 2 ∣E∣ para um grafo (V, E).
Acrescente ao grafo uma nova aresta xy.
Seja E′ o novo conjunto de arestas.
Denote por g′ os graus dos vértices no grafo (V, E′).
Temos g′(x) = 1+g(x), g′(y) = 1+g(y) e g′(v) = g(v) para todo v diferente de x e y.
Portanto, ∑ g′(v) = 1 + 1 + ∑ g(v) = 2 + 2 ∣E∣.
Mas 2 + 2 ∣E∣ = 2 ∣E′∣, e assim ∑ g′(v) = 2 ∣E′∣.
Um emparelhamento num grafo é um conjunto de restas que incide no máximo uma vez em cada vértice. Dizemos que um emparelhamento M satura um vértice v se M incide em v.
Proposição: Em qualquer grafo, todo vértice não isolado é saturado por algum emparelhamento máximo.
Prova:
Seja G um grafo e u um vértice não isolado de G.
Seja M um emparelhamento máximo em G.
Se M satura u então nada mais temos que provar.
Suponha agora que M não satura u.
Seja uv qualquer uma das arestas que incidem em u.
O emparelhamento M satura v (pois é máximo).
Seja vw a aresta de M que incide em v.
O conjunto (M ∪ {uv}) − {vw} é um emparelhamento.
Esse emparelhamento é máximo (pois tem o mesmo tamanho que M).
Esse emparelhamento satura u.
É claro que você não precisa seguir fielmente o formato dos exemplos acima: o texto da prova pode ser complementado com comentários e observações que tornem a leitura mais fácil. (A propósito, veja o artigo de Reuben Hersh.)
an−1 = an−2 a1 = an−2 an−2/an−3 = 1 × 1 / 1 = 1.
Portanto,
a afirmação está correta para todo n,
como queríamos provar.
Onde está o erro dessa prova?
[D.E. Knuth, Fundamental Algorithms
]
∑n−1 1/(i (i+1)) = | ||
= | ∑n−2 1/(i (i+1)) + 1/((n−1) n) | |
= | 3/2 − 1/(n−1) + 1/((n−1) n) | |
= | 3/2 − 1/(n−1) + 1/(n−1) − 1/n | |
= | 3/2 − 1/n. |
Onde está o erro da prova?
Alguma coisa deve estar errada, pois
quando n = 6
o lado esquerdo da equação vale 5/6
enquanto o lado direito vale 4/3.
[D.E. Knuth, Fundamental Algorithms
]
What are the most common mistakes people make when writing mathematical proofs?