Estruturas Discretas – INF 1631
Thibaut Vidal
Departamento de Informática, Pontifı́cia Universidade Católica do Rio de Janeiro
Rua Marquês de São Vicente, 225 - Gávea, Rio de Janeiro - RJ, 22451-900, Brazil
[email protected]
August 12, 2015
>
Tipos de Demonstração
1/13
Conteúdo
1
>
Tipos de Demonstração
Exemplos e Contra-Exemplos
Demonstração por Força Bruta
Prova Direta
Prova Construtiva
Prova por Contradição
Tipos de Demonstração
1/13
Conteúdo
1
>
Tipos de Demonstração
Exemplos e Contra-Exemplos
Demonstração por Força Bruta
Prova Direta
Prova Construtiva
Prova por Contradição
Tipos de Demonstração
1/13
Exemplos e Contra-Exemplos
Quando uma proposição trata de um conjunto finito de elementos, ou
quando ela afirma a existência de um número finito de valores que
satisfaçam certas condições, é possı́vel prová-la simplesmente
mostrando sua validade para todos os elementos sob os quais ela é
afirmada
Proposição
∀n ∈ {4, 6, 8}, n pode ser expresso como a soma de números primos.
Proposição
∃ n inteiro tal que n 2 + n + 5 é um número primo.
>
Tipos de Demonstração
2/13
Exemplos e Contra-Exemplos
Como aplicação da utilização de um contra-exemplo para mostrar que
uma proposição é falsa, podemos citar:
Proposição
Nenhum número primo é par.
Proposição
Todo inteiro menor que 10, é maior que 5.
>
Tipos de Demonstração
3/13
Demonstração por Força Bruta
Provar com exemplos se torna difı́cil e muitas vezes inviável na
prática. A resolução de vários problemas de interesse para a
computação envolvem essa técnica de exemplos também conhecida
como enumeração completa, busca exaustiva ou força bruta.
Proposição
Todo número par maior ou igual a 4 e menor que 20, pode ser escrito
como a soma de dois primos.
>
Tipos de Demonstração
4/13
Demonstração por Força Bruta
Proposição
Todo nú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 Demonstração
5/13
Demonstração por Força Bruta
Se no entanto modificarmos a proposição anterior para:
Proposição
Todo nú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 análoga à anterior.
>
Tipos de Demonstração
6/13
Demonstração por Força Bruta
Se, no entanto, quisermos provar a proposição geral:
Proposição
Todo número par maior ou igual a 4 pode ser escrito como a soma de
2 primos.
Não conseguirı́amos usar prova exaustiva pois o conjunto é infinito.
No entanto o computador pode ser útil para buscar um
contra-exemplo que invalide a proposição(até hoje não encontrado).
Esse problema está em aberto e é conhecido como Conjectura de
Goldbach.
>
Tipos de Demonstração
7/13
Demonstração por Prova Direta
Prova direta = encadeamento de argumentos lógicos a partir da
hipótese, que podem ser: axiomas, definições ou outros teoremas(já
provados), que resulta em uma implicação lógica da tese.
Teorema
A soma de 3 números consecutivos é múltiplo de 3.
>
Tipos de Demonstração
8/13
Demonstração por Prova Direta
Prova direta = encadeamento de argumentos lógicos a partir da
hipótese, que podem ser: axiomas, definições ou outros teoremas(já
provados), que resulta em uma implicação lógica da tese.
Teorema
Se x é um numero par inteiro, então x 2 − 6x + 5 é impar.
>
Tipos de Demonstração
9/13
Demonstração por Prova Direta
Prova direta = encadeamento de argumentos lógicos a partir da
hipótese, que podem ser: axiomas, definições ou outros teoremas(já
provados), que resulta em uma implicação lógica da tese.
Teorema
Considere um hexagono regular cujos vértices são v1 , v2 , . . . , v6 .
Mostre que toda maneira de colorir os segmentos de retas que unem
dois vértices, utilizando as cores azul ou branca, produz pelo menos
um triângulo cujos lados tem a mesma cor.
>
Tipos de Demonstração
10/13
Demonstração por Prova Direta
Prova: Próximo aula...
>
Tipos de Demonstração
11/13
Prova Construtiva
Próximo aula...
>
Tipos de Demonstração
12/13
Prova por Contradição
Próximo aula...
>
Tipos de Demonstração
13/13