Estruturas Discretas – INF 1631 Thibaut Vidal Departamento de Informática, Pontifı́cia Universidade Católica do Rio de Janeiro Rua Marquês de São Vicente, 225 - Gávea, Rio de Janeiro - RJ, 22451-900, Brazil [email protected] August 12, 2015 > Tipos de Demonstração 1/13 Conteúdo 1 > Tipos de Demonstração Exemplos e Contra-Exemplos Demonstração por Força Bruta Prova Direta Prova Construtiva Prova por Contradição Tipos de Demonstração 1/13 Conteúdo 1 > Tipos de Demonstração Exemplos e Contra-Exemplos Demonstração por Força Bruta Prova Direta Prova Construtiva Prova por Contradição Tipos de Demonstração 1/13 Exemplos e Contra-Exemplos Quando uma proposição trata de um conjunto finito de elementos, ou quando ela afirma a existência de um número finito de valores que satisfaçam certas condições, é possı́vel prová-la simplesmente mostrando sua validade para todos os elementos sob os quais ela é afirmada Proposição ∀n ∈ {4, 6, 8}, n pode ser expresso como a soma de números primos. Proposição ∃ n inteiro tal que n 2 + n + 5 é um número primo. > Tipos de Demonstração 2/13 Exemplos e Contra-Exemplos Como aplicação da utilização de um contra-exemplo para mostrar que uma proposição é falsa, podemos citar: Proposição Nenhum número primo é par. Proposição Todo inteiro menor que 10, é maior que 5. > Tipos de Demonstração 3/13 Demonstração por Força Bruta Provar com exemplos se torna difı́cil e muitas vezes inviável na prática. A resolução de vários problemas de interesse para a computação envolvem essa técnica de exemplos também conhecida como enumeração completa, busca exaustiva ou força bruta. Proposição Todo número par maior ou igual a 4 e menor que 20, pode ser escrito como a soma de dois primos. > Tipos de Demonstração 4/13 Demonstração por Força Bruta Proposição Todo número par maior ou igual a 4 e menor que 20, pode ser escrito como a soma de dois primos. Prova: Basta resolver para todos os casos: 4=2+2 10=7+3 16=11+5 6=3+3 12=7+5 18=13+5 8=5+3 14=7+7 > Tipos de Demonstração 5/13 Demonstração por Força Bruta Se no entanto modificarmos a proposição anterior para: Proposição Todo número par maior ou igual a 4 e menor que 100.000 pode ser escrito como a soma de 2 primos. Prova: Utilizando-se um computador para gerar todas as possibilidades, procede-se de forma análoga à anterior. > Tipos de Demonstração 6/13 Demonstração por Força Bruta Se, no entanto, quisermos provar a proposição geral: Proposição Todo número par maior ou igual a 4 pode ser escrito como a soma de 2 primos. Não conseguirı́amos usar prova exaustiva pois o conjunto é infinito. No entanto o computador pode ser útil para buscar um contra-exemplo que invalide a proposição(até hoje não encontrado). Esse problema está em aberto e é conhecido como Conjectura de Goldbach. > Tipos de Demonstração 7/13 Demonstração por Prova Direta Prova direta = encadeamento de argumentos lógicos a partir da hipótese, que podem ser: axiomas, definições ou outros teoremas(já provados), que resulta em uma implicação lógica da tese. Teorema A soma de 3 números consecutivos é múltiplo de 3. > Tipos de Demonstração 8/13 Demonstração por Prova Direta Prova direta = encadeamento de argumentos lógicos a partir da hipótese, que podem ser: axiomas, definições ou outros teoremas(já provados), que resulta em uma implicação lógica da tese. Teorema Se x é um numero par inteiro, então x 2 − 6x + 5 é impar. > Tipos de Demonstração 9/13 Demonstração por Prova Direta Prova direta = encadeamento de argumentos lógicos a partir da hipótese, que podem ser: axiomas, definições ou outros teoremas(já provados), que resulta em uma implicação lógica da tese. Teorema Considere um hexagono regular cujos vértices são v1 , v2 , . . . , v6 . Mostre que toda maneira de colorir os segmentos de retas que unem dois vértices, utilizando as cores azul ou branca, produz pelo menos um triângulo cujos lados tem a mesma cor. > Tipos de Demonstração 10/13 Demonstração por Prova Direta Prova: Próximo aula... > Tipos de Demonstração 11/13 Prova Construtiva Próximo aula... > Tipos de Demonstração 12/13 Prova por Contradição Próximo aula... > Tipos de Demonstração 13/13
Download
