Provas de Teoremas

 

Elaborar provas de teoremas é um atividade que em geral não pode ser ensinada. A processo de construção de provas normalmente é aprendido por experiência: inicialmente se procura compreender e imitar provas existentes com a expectativa que isto conduza à criação de provas originais.

Há, contudo, poucas chances de que se possa provar um teorema sem que se tenha uma compreensão razoável da exposição contida num teorema. Em geral os teoremas podem ser apresentados na forma de uma implicação:

Se P então Q

onde P e Q denotam declarações que podem ser verdade ou falsa (o "ou" é exclusivo: nenhuma delas pode assumir ambos os valores verdade  "verdade" e "falso" ao mesmo tempo - há uma dicotomia) . A declaração P é a hipótese do teorema, enquanto que Q é a conclusão. As implicações são um tipo especial de declarações que são verdadeiras ou falsas em si. Os teoremas são implicações verdadeiras, motivo pelo qual eles apresentam interesse particular.

 

 

Estratégias de Provas

 

Para ilustrar as várias técnicas de prova de teoremas, considere o seguinte teorema:

Seja x um número inteiro. Se x é par, então y=x + 5 é ímpar.

Para efeito destas provas, note que um número inteiro x ou é ímpar ou é par, mas não ambos. Note também que se x é um inteiro par, então x=2n para algum inteiro n. De forma similar, um inteiro ímpar y pode ser expresso por y=2m + 1, onde m é um inteiro.

 

Prova direta

Esta estratégia de prova normalmente inicia por assumir que P (a hipótese) é verdadeira e, então, tenta-se mostrar que Q (a conclusão) é verdadeira.

Prova: assuma que x é um inteiro par. Então x=2n para algum inteiro n, de forma que 
y=x + 5=2n + 5=(2n + 4) + 1=2 (n + 2) + 1.
Fazendo m=n + 2, segue que y=2m + 1, onde m é um inteiro. Consequentemente y é um inteiro ímpar.

 

Prova indireta

Conforme pode ser visto na tabela que se segue, "P -> Q" é logicamente a "~Q -> ~P" (~Q significa "não Q").

 

 

 

 

 

 

 

 

 

 

​

Sendo assim, uma segunda estratégia de prova inicia por  assumir que Q é falsa e, então, mostrar que P é falsa. Esta prova é conhecida como uma prova indireta da implicação.

Prova: assuma que y=x + 5 não é um inteiro ímpar. Então y=x + 5=2n, para algum n inteiro. Segue que
x=2n - 5=(2n - 6) + 1=2 (n - 3) + 1.
Fazendo m=n - 3, temos que x=2m + 1 par algum inteiro m. Logo, x é ímpar, isto é, x não é par.

 

Prova por contradição

Uma variante da prova indireta inicia por assumir que P é verdade e que Q é falsa (esperando, é claro, que isto seja impossível) e, então, tentando mostrar que P é falsa. Desde que P não pode verdade e falsa simultaneamente, a implicação é provada por contradição.

Prova: Assuma que x é um inteiro par. Então x=2n para algum inteiro n. Suponha que y=x + 5 não é ímpar. Então y é par de forma que y=x + 5=2m para algum inteiro m. Consequentemente x=2m - 5=(2m - 6) + 1=2 (m - 3) + 1. Fazendo k=m - 3, segue que x=2k + 1 para algum inteiro k. Portanto x é ímpar. Isto é uma contradição, de forma que y deve ser ímpar.

 

Indução Matemática (princípio primeiro: Princípio da Boa Ordenação)

Uma das mais importantes e úteis técnicas de prova de teoremas é conhecida como indução matemática. Ela é baseada numa propriedade do conjunto dos números inteiros positivos que é a de ser Bem Ordenado.

 

Seja m um inteiro e sejam Sm, Sm+1, Sm+2, ... declarações com as seguints propriedades:

1. Sm é verdade;
2. Sk é verdade -> Sk+1 é verdade.

Então cada uma das declarações Sm, Sm+1, Sm+2, ... é verdade.

 

Por exemplo, considere a soma dos primeiros termos da seqüência: Sn =1 + 3 + 5 + ... + (2n - 1)=n²

Prova:

1. S1 =1=1²;
2. Assuma que Sk =1 + 3 + 5 + ... + (2k - 1)=k² é verdade. Então é preciso mostrar que 

     Sk+1 =1 + 3 + 5 + ... + (2k - 1) + (2k + 1)=(k + 1)² é verdade. Desde que 1 + 3 + 5 + ... + (2k - 1)=k², segue que [1 + 3 + 5 + ... + (2k     - 1)] + (2k + 1)=k² + (2k + 1). Mas como k² + (2k + 1)=(k + 1)², segue que Sk+1 é verdade. Portanto Sm é verdade para qualquer inteiro       positivo m.