O que é uma prova?

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.

Exemplo 1

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)\text{.}$

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)\text{.}$

A posição $(2,3)$ é vizinha de duas bombas e há uma bomba em $(3,4)\text{.}$

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)\text{.}$

Agora, o 2 na posição $(5,3)$ garante que não há bomba em $(5,2)$ nem em $(6,2)\text{.}$

Mas isso é inconsistente com o 3 na posição $(6,3)\text{.}$

Esta contradição mostra que $(1,2)$ não pode ter uma bomba.

Exemplo 2

Proposição:  Não existem números inteiros positivos $p$ e $q$ tais que $p/q = \sqrt{2}\text{.}$  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\text{.}$

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\text{.}$

O número $p^2$ é par, pois $p^2 = 2 q^2\text{.}$

O número $p$ é par, pois o produto de quaisquer dois números ímpares é ímpar.

Seja $s$ o número inteiro $p/2\text{.}$

O número $q^2$ é par, pois $q^2 = p^2/2 =$ $(2 s)^2/2 =$ $2 s^2\text{.}$

O número $q$ é par, pois o produto de dois ímpares é ímpar.

Os números $p$ e $q$ são divisíveis por $2\text{.}$

Isso contradiz a maneira como escolhemos $p$ e $q\text{.}$

A contradição mostra que a raiz quadrada de $2$ é irracional.

Exemplo 3

Proposição:  Se $n$ é um número inteiro positivo então $1^2 + 2^2 + 3^2 + \cdots + n^2 =$ $\frac{1}{6}\,n (n+1) (2n+1)\text{.}$

Prova, por indução em $n\text{:}$

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, $1^2 + 2^2 + \cdots + (n - 1)^2 =$ $\frac{1}{6}\,(n-1) n (2n - 1)\text{.}$

Portanto,  $1^2 + 2^2 + \cdots + n^2 = \mbox{}$

xxxxxxxxxxxx $\mbox{} = 1^2 + 2^2 + \cdots + (n-1)^2 + n^2$

xxxxxxxxxxxx $\mbox{} = \frac{1}{6}\,(n-1)n(2n-1) + n^2$

xxxxxxxxxxxx $\mbox{} = \frac{1}{6}\,n\,((n-1)(2n-1) + 6n)$

xxxxxxxxxxxx $\mbox{} = \frac{1}{6}\,n\,(2n^2 - 3n + 1 + 6n)$

xxxxxxxxxxxx $\mbox{} = \frac{1}{6}\,n\,(2n^2 + 3n + 1)$

xxxxxxxxxxxx $\mbox{} = \frac{1}{6}\,n\,(n+1)(2n+1)\text{,}$

como queríamos demonstrar.

Exemplo 4

O grau de um vértice $v$ num grafo é o número de arestas que têm ponta $v\text{.}$ O grau de um vértice $v$ é denotado por $g(v)\text{.}$

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 $\sum_{v\in V} g(v) = 2 |E|\text{.}$

Prova, por indução em $|E|\text{:}$

Base da indução: $|E| = 0\text{.}$

Nesse caso, $\sum g(v) = 0\text{,}$ e portanto $\sum g(v) =$ $2 |E|\text{.}$

Passo da indução: $|E| > 0\text{.}$

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\}\text{.}$

Seja $g'(v)$ o grau de $v$ no grafo $(V, F)\text{.}$

Por hipótese de indução,  $\sum g'(v) = 2 |F|\text{.}$

Temos $g(x) = 1 + g'(x)\text{,}$ $g(y) = 1 + g'(y)$ e $g(v) = g'(v)$ para todo $v$ diferente de $x$ e $y\text{.}$

Portanto,  $\sum g(v) = 1 + 1 + \sum g'(v) = 2 + 2 |F|\text{.}$

Mas $2 + 2 |F| = 2 |E|\text{.}$

Portanto,  $\sum g(v) = 2 |E|\text{,}$ como queríamos demonstrar.

Exemplo 5

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\text{.}$

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\text{.}$

Seja $M$ um emparelhamento máximo em $G\text{.}$

Se $M$ satura $u$ então nada mais temos que provar.

Suponha agora que $M$ não satura $u\text{.}$

Seja $uv$ qualquer uma das arestas que incidem em $u\text{.}$

O emparelhamento $M$ satura $v$ (pois é máximo).

Seja $vw$ a aresta de $M$ que incide em $v\text{.}$

O conjunto $(M \cup \{uv\}) - \{vw\}$ é um emparelhamento.

Esse emparelhamento é máximo (pois tem o mesmo tamanho que $M$).

Esse emparelhamento satura $u\text{.}$

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.  (A propósito, veja o artigo de Reuben Hersh.)

Exercícios

Bibliografia e material suplementar