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=2q^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=$ $(2s{)}^2/2=$ $2s^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=$

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

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

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

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

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

xxxxxxxxxxxx $=\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^{\prime }(v)$ o grau de $v$ no grafo $(V,F)\text{.}$

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

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

Portanto,  $\sum g(v)=1+1+\sum g^{\prime }(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