Teoria da Computação: Provas e Estratégias Matemáticas

Teoria da Computação Licenciatura em Computação Prof Ângelo Magno Estratégias de Provas Prova por Contradição Redução por absurdo Prova matemática indireta Assumese como verdade o contrário do que se quer provar e então chegase a uma contradição Prova por Contradição Exemplo 1 Seja x um número inteiro Se x é par então y x 5 é impar Provar por contradição Prova 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 Prova por Contradição Exemplo 2 Provar por contradição que existem infinitos números primos Prova por Contradição Exemplo 2 Suponha por absurdo que existem n uma quantidade finita números primos denotados por p1 p2 pn pn seria a último número primo Considere o número x p1 p2 pn 1 O número x não é divisível por nenhum dos números p1 p2 pn o resto da divisão é sempre 1 Logo x é primo Isto é um absurdo pois contradiz a hipótese inicial de que existem apenas n números primos A hipótese inicial está errada e portanto existem infinitos números primos Prova por Indução Indução matemática Baseada numa propriedade do conjunto dos números inteiros positivos a de ser bem ordenado Parte de particular para o geral Prova por Indução Considere X um conjunto tendo como base X0 Seja X0 X1 Xn a sequência de conjuntos gerados por um processo recursivo e P uma propriedade Mostrar que P é válido para X0 Se P é válido para Xn e também é para Xn 1 Prova por Indução Efeito dominó O primeiro dominó cairá Sempre que um dominó cair seu próximo vizinho também cairá Prova por Indução Em resumo Passo base mostrar que o enunciado vale para n 1 Passo indutivo mostrar que se o enunciado vale para nk então o mesmo enunciado vale para nk1 Prova por Indução Exemplo 1 Provar que Base P1 é verdadeiro Hipótese P é verdadeira para 0 1 2 3 k ou seja Passo Indutivo Prova por Indução Exemplo 2 soma dos primeiros termos da sequência Sn 1 3 5 2n 1 n Base S1 1 1 Hipótese Sk 1 3 5 2k 1 k é verdade Indução Sk1 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 Sk1 é verdade Referências Song Mark Alan FTC notas de aula Mariani Antonio C UFSC Provas de Teoremas Wikipédia