Matemática

Estrategias para Provas de Teoremas

Fonte: http://www.inf.ufsc.br

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, mas não ambas. 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 é impar.

Para efeito destas provas, note que um número inteiro x ou é impar 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 impar 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 impar.

Prova Indireta

Conforme pode ser visto na tabela que se segue, "P -> Q" é logicamente a "~Q -> ~P".

Tabela Verdade
P Q ~Q ~P P -> Q
~Q -> ~P

v v
f

f

v

v

v f
v

f

f

f

f v
f

v

v

v

f f
v

v

v

v

**Tabela Verdade**
P	Q	~Q	~P	P -> Q	~Q -> ~P
v	v	f	f	v	v
v	f	v	f	f	f
f	v	f	v	v	v
f	f	v	v	v	v

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 impar. 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 é impar, 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 é impar. 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 é impar. Isto é uma contradição, de forma que y deve ser impar.

Indução Matemática (Princípio Primeiro)

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 S_m, S_m+1, S_m+2, ... declarações com as seguints propriedades:

S_m é verdade;

S_k é verdade -> S_k+1 é verdade,

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

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

Prova:

S₁ = 1 = 1²

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

S_k+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 S_k+1 é verdade. Portanto S_m é verdade para qualquer inteiro positivo m.

- Prova De Irracionalidade Do Número De Euler
Na matemática, o número de Euler é uma das mais importantes constantes reais. A demonstração de que este número é irracional é considerada um dos mais elegantes teoremas de matemática. A demonstração baseia-se...

- O Algoritmo Da Divisão Parte Iv [o Fim]
Esta é a última postagem da série que teve o objetivo de demonstrar o algoritmo da divisão: Se a é um número inteiro qualquer e b é um número inteiro maior do que zero, então existem dois números inteiros q e r tais...

- O Algoritmo Da Divisão Parte Iii
Nesta série de postagens estamos demonstrando o algoritmo da divisão: Se aé um número inteiro qualquer e bé um número inteiro maior do que zero, então existem dois números inteiros qe rtais que a= bq+ r, onde 0 ? r < b. Além disso, qe rsão...

- Prova De Matemática Colégio Naval 1999-2000
Essa é a última prova da contagem regressiva para o concurso do CN 2013-2014. Prova de Matemática CN 1999-2000 A seguir encontram-se os links para as outras resoluções de provas de Matemática do CN disponíveis neste blog. Prova...

- As Tabelas Verdade
A lógica clássica é governada por três princípios (entre outros) que podem ser formulados como segue: · Princípio da Identidade: Todo objeto é idêntico a si mesmo. · Princípio da Contradição: Dadas duas proposições contraditórias...

Matemática