CADASTRE-SE
Temos Uma versão desta Revista Especificamente para SmartPhone
Mais Enxuta: Somente Vídeo Aulas e EVENTOS!
Music Player
l
Ensino&Informação
PESQUISA OPERACIONAL
Disciplina: Teoria dos Grafos
(Algumas Estratégias para demonstração)
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:
- Sm é verdade;
- 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:
- S1 =1=1²;
- 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.
Texto de autoria do Prof. Antônio Carlos Mariani .
Departamento de Informática e Estatística - UFSC.
Em respeito aos direitos autorais, este texto foi revisado e mantido na íntegra pela
A partir de 11 Set de 2020
Você é o Visitante de Número