O que é uma prova?

 

[(pdf) Versão pdf desta página]
[Versão jsMath desta página]

Em matemática, uma prova é uma argumentação precisa que procura convencer o leitor de que uma certa proposição, previamente enunciada, está correta.

Que "cara" tem uma prova?  Uma prova é uma sequência de afirmações organizada da seguinte maneira:  cada afirmação é consequência simples das afirmações anteriores e das hipóteses da proposição em discussão;  a última afirmação é a proposição que se deseja provar.

 

Exemplo 1

? ? 1 1 B
? ? 2 2 B
? ? 3 B  
? ? B 2  
? ? 2 1  
? ? 3 1  
2 B B 1  
2 3 3 1  

Considere a configuração do jogo Mine Hunt indicada ao lado.  Cada "B" representa uma bomba. As posições em branco não têm bombas. 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 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 acima não contém 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 conter bomba.

 

Exemplo 2

PROPOSIÇÃO:   A raiz quadrada de 2 é irracional,  ou seja,  não existem números inteiros positivos p e q tais que  p/q = √2.

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,  ou seja,
de modo que não exista um 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 p/2.
O número  q2  é par  (pois q2 = p2/2 = (2s)2/2 = 2s2).
O número q é par.
Os números p e q são divisíveis por 2.
Isso contradiz a maneira como escolhemos pq.
A contradição mostra que a raiz quadrada de 2 é irracional.

 

Exemplo 3

PROPOSIÇÃO:   Para qualquer número natural não nulo n tem-se   12 + 22 + 32 + ··· + n2   =   n(n+1)(2n+1)/6 .

PROVA, por indução em n:
Base da indução:  n = 1.
Nesse caso, os dois lados da identidade valem 1 e portanto são iguais.
Passo da indução:  n > 1.
Por hipótese de indução,  12 + 22 + ··· + (n−1)2  =  (n−1)n(2n−1)/6.
Portanto,

12 + 22 + ··· + n2 = 12 + 22 + ··· + (n−1)2  +  n2
  = ((n−1)n(2n−1)/6)  +  n2
  = (n/6) · ((n−1)(2n−1) + 6n)
  = (n/6) · (2n2 − 3n + 1 + 6n)
  = (n/6) · (2n2 + 3n + 1)
  = (n/6) · (n+1)(2n+1)
  = n(n+1)(2n+1)/6 .

 

Eis uma maneira feia de organizar a indução (pois vai de n+1 para n e assim termina com uma expressão que não tem a mesma forma do enunciado):

Base da indução:
Se n = 1 então os dois lados da identidade valem 1 e portanto são iguais.
Passo da indução:
Suponha que a identidade vale para n.
Vamos provar a identidade para n+1:

12 + 22 + ··· + n2 + (n+1)2 = n(n+1)(2n+1)/6  +  (n+1)2
  = ((n+1)/6) · (n(2n+1) + 6(n+1))
  = ((n+1)/6) · (2n2 + 7n + 6)
  = ((n+1)/6) · (n+2)(2n+3)
  = (n+1)(n+2)(2(n+1)+1))/6 .

 

Exemplo 4

PROPOSIÇÃO:   Em qualquer grafo  (V,E),  a soma dos graus dos vértices é igual ao dobro do número de arestas,  ou seja,   ∑vV d(v) = 2 |E|.

PROVA, por indução em |E|:
Base da indução:  |E| = 0.
Nesse caso, ∑ d(v) = 0,  e portanto ∑ d(v) = 2 |E|.

Passo da indução:  |E| > 0.
Hipótese de indução:  a identidade vale em qualquer subgrafo próprio de (V,E).
Seja  xy  uma aresta do grafo.
Seja  F  o conjunto  E − {xy}.
Seja  dF(v) o grau de  v  no grafo  (V,F).
Por hipótese de indução,  ∑ dF(v) = 2 |F|.
Temos  d(x) = 1+dF(x),  d(y) = 1+dF(y)  e  d(v) = dF(v)  para todo v diferente de x e y.
Portanto,  ∑ d(v)  =  1 + 1 + ∑ dF(v)  =  2 + 2 |F|.
Mas 2 + 2 |F|  =  2 |E| , e portanto  ∑ d(v)  =  2 |E|,  como queríamos demonstrar.

 

Eis uma versão errada da indução (pois acrescenta aresta em vez de tirar):

Base da indução:  |E| = 0.
Nesse caso, ∑ d(v) = 0,  e portanto ∑ d(v) = 2 |E|.

Passo da indução:  Vamos supor que  ∑ d(v) = 2 |E|  para um certo grafo (V,E).
Acrescente ao grafo uma nova aresta xy.
Seja  E'  o novo conjunto de arestas e denote por  d'  os graus dos vértices no novo grafo.
Temos  d'(x) = 1+d(x),  d'(y) = 1+d(y)  e  d'(v) = d(v)  para todo v diferente de x e y.
Portanto,  ∑ d'(v)  =  1 + 1 + ∑ d(v)  =  2 + 2 |E|.
Mas  2 + 2 |E|  =  2 |E'|,  e assim  ∑ d'(v)  =  2 |E'|.

 

Exemplo 5

PROPOSIÇÃO:   Em qualquer grafo,  todo vértice não isolado é saturado por um 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.

 

Observações finais

É 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 e agradável.  A propósito, veja o artigo de Reuben Hersh — "Math Lingo vs. Plain English: Double Entendre", The American Mathematical Monthly, v.104 (1997), pp. 48-51, http://www.jstor.org/stable/2974822 — sobre o jargão da matemática.

 


Exercícios

1. Prove, por indução em k, que  20 + 21 + ··· + 2k = 2k+1−1.

2. [D.E. Knuth, "Fundamental Algorithms"]  Seja a um número positivo qualquer. Afirmo que para todo inteiro positivo n tem-se   an−1 = 1.   Eis a prova (por indução em n):  Se n = 1 então  an−1 = a0 = 1  e portanto a afirmação está correta nesse caso. Agora tome n > 1 e suponha, a título de hipótese de indução, que ak−1 = 1 para k = n−1, n−2, …, 1.  Temos então

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 da prova?

3. [D.E. Knuth, "Fundamental Algorithms"]  Afirmo que, para todo número inteiro positivo n, tem-se

 i=1,…,n−1 1/(i · (i+1))  =  3/2 − 1/n .

Eis a prova (por indução em n):  Para n = 1, ambos os lados da equação valem 1/2 e portanto a afirmação está correta nesse caso. Agora tome n > 1 e suponha, como hipótese de indução, que ∑ i=1,…,n−2 1/(i · (i+1))  =  3/2 − 1/(n−1) .  Teremos então

 i=1,…,n−1 1/(i · (i+1)) =  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 ,

como queríamos demonstrar.   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.

4. [Manuel Blum]  Imagine uma dessas barras de chocolate retangulares que consiste em quadradinhos dispostos em linhas e colunas. Uma tal barra pode ser quebrada ao longo de uma linha ou de uma coluna produzindo assim duas barras menores. Qual o número mínimo de quebras necessário para reduzir uma barra com m linhas e n colunas aos seus quadradinhos constituintes?

5. [Manuel Blum]  Imagine uma jarra contendo um certo número de bolas brancas e bolas pretas.  Suponha também que você tem um suprimento ilimitado de bolas brancas fora da jarra.  Agora repita o seguinte procedimento enquanto ele fizer sentido:  retire duas bolas da jarra;  se as duas tiverem a mesma cor, coloque uma bola branca na jarra; se as duas tiverem cores diferentes, coloque uma bola preta na jarra.   Qual a cor da última bola a sobrar na jarra?

 


Veja a página de humor sobre o conceito de prova na Universidade Western Australia


URL of this site: http://www.ime.usp.br/~pf/amostra-de-prova/
Last modified: Fri Oct 4 10:53:46 BRT 2013
Paulo Feofiloff
IME-USP

Valid HTML 4.0!    Valid CSS!

Outros assuntos:   Projeto de Algoritmos em C  |  Literate Programming & CWEB  |  Análise de Algoritmos  |  Minicurso de Análise de Algoritmos  |  Algoritmos em Grafos com Stanford GraphBase  |  Algoritmos para Grafos via Sedgewick  |  Uma Introdução Sucinta à Teoria dos Grafos  |  Exercícios de Teoria dos Grafos  |  Fluxo em Redes  |  Digrafos  |  Algoritmos de Programação Linear  |  Opiniões e notícias