Técnicas de Demonstração Matemática

Prévia do material em texto

Demonstrações
Terminologia
Métodos
Técnicas de Demonstração
� Uma demonstração é um argumento válido 
que estabelece a verdade de uma sentença 
matemática.
Técnicas de Demonstração
� Demonstrações servem para:
� Verificar se uma determinada implementação 
está correta.
� Estabelecer se sistemas de operações são 
seguros
� Mostrar se sistemas de especificações são 
consistentes
Técnicas de Demonstração
� Uma demonstração é um argumento válido que 
estabelece a verdade de um teorema.
� Teorema: é uma sentença que se pode demonstrar 
que é verdadeira.
� Corolário: é um teorema que pode ser estabelecido 
diretamente de um teorema que já foi demonstrado.
� Lema: teoremas menos importantes que nos ajuda 
em outras demonstrações.
� Conjectura: é uma sentença que inicialmente é 
proposta como verdadeira, usualmente com base 
em alguma evidência parcial.
Técnicas de Demonstração
� Um teorema é uma proposição do tipo:
p � q
� a qual, prova-se, é verdadeira sempre que:
p q
“Se x>y, em que x e y são números reais 
positivos, então x2 > y2”
“Para todos os números reais positivos x e y, 
se x>y então x2 > y2”
Técnicas de Demonstração
� A � (B U C) = (A � B) U (A � C)
� Se A, B e C são conjuntos quaisquer, então 
A � (B U C) = (A � B) U (A � C)
Hipótese
Tese
Técnicas de Demonstração
� Para teoremas do tipo p � q
� Prova Direta
� Prova por Contraposição
� Prova por Redução ao Absurdo ou simplesmente 
Prova por Absurdo
� Prova por Indução
Prova Direta
� Pressupõe verdadeira a hipótese e, a partir 
desta, prova ser verdadeira a tese.
� Hipótese verdadeira e tese falsa nunca deve 
ocorrer
Prova Direta
1. Assumir que a hipótese é verdadeira.
2. Mostrar que a tese também é verdadeiro 
usando:
1. Lemas, definições e teoremas
2. Regras de inferência
� Exemplo: 
� Se A, B e C são conjuntos quaisquer então A �
(B U C) = (A � B) U (A � C)
Prova Direta
� Lembrando:
� Por definição X = Y se e somente se 
X Y e Y X
� Por definição, X Y se e somente se todos os 
elementos de X também são elementos de Y
Prova Direta
� Teorema: Se A, B e C são conjuntos 
quaisquer então A � (B U C) = (A � B) U (A 
� C)
� Temos que provar que 
� A � (B U C) (A � B) U (A � C)
� (A � B) U (A � C) A � (B U C) 
� Por definição X = Y se e somente se 
X Y e Y X
Prova Direta
� A � (B U C) (A � B) U (A � C)
Como provar?
� Por definição, X Y se e somente se todos os 
elementos de X também são elementos de Y
Prova Direta
� A � (B U C) (A � B) U (A � C)
� Suponha x ∈ A � (B U C).
x ∈ A � (B U C) definição de intersecção
x ∈ A e x ∈ (B U C) => definição de união
x ∈ A e ( x ∈ B ou x ∈ C) => distributividade sobre e/ou
(x ∈ A e x ∈ B) ou (x ∈ A e x ∈ B) => definição intersecção
x ∈ (A � B) ou x ∈ (A � C)=> definição de união
x ∈ (A � B) U (A � C)
Prova Direta
� A � (B U C) (A � B) U (A � C)
x ∈ A � (B U C) definição de intersecção
x ∈ A e x ∈ (B U C) definição de união
x ∈ A e ( x ∈ B ou x ∈ C) => distributividade sobre e/ou
(x ∈ A e x ∈ B) ou (x ∈ A e x ∈ B) => definição intersecção
x ∈ (A � B) ou x ∈ (A � C)=> definição de união
x ∈ (A � B) U (A � C)
Prova Direta
� A � (B U C) (A � B) U (A � C)
x ∈ A � (B U C) definição de intersecção
x ∈ A e x ∈ (B U C) definição de união
x ∈ A e ( x ∈ B ou x ∈ C) distributividade sobre e/ou
(x ∈ A e x ∈ B) ou (x ∈ A e x ∈ B) => definição intersecção
x ∈ (A � B) ou x ∈ (A � C)=> definição de união
x ∈ (A � B) U (A � C)
Prova Direta
� A � (B U C) (A � B) U (A � C)
x ∈ A � (B U C) definição de intersecção
x ∈ A e x ∈ (B U C) definição de união
x ∈ A e ( x ∈ B ou x ∈ C) distributividade sobre e/ou
(x ∈ A e x ∈ B) ou (x ∈ A e x ∈ C) definição intersecção
x ∈ (A � B) ou x ∈ (A � C)=> definição de união
x ∈ (A � B) U (A � C)
Prova Direta
� A � (B U C) (A � B) U (A � C)
x ∈ A � (B U C) definição de intersecção
x ∈ A e x ∈ (B U C) definição de união
x ∈ A e ( x ∈ B ou x ∈ C) distributividade sobre e/ou
(x ∈ A e x ∈ B) ou (x ∈ A e x ∈ C) definição intersecção
x ∈ (A � B) ou x ∈ (A � C) definição de união
x ∈ (A � B) U (A � C)
Prova Direta
� A � (B U C) (A � B) U (A � C)
x ∈ A � (B U C) definição de intersecção
x ∈ A e x ∈ (B U C) definição de união
x ∈ A e ( x ∈ B ou x ∈ C) distributividade sobre e/ou
(x ∈ A e x ∈ B) ou (x ∈ A e x ∈ C) definição intersecção
x ∈ (A � B) ou x ∈ (A � C) definição de união
x ∈ (A � B) U (A � C)
CQD
Relembrando o teorema
� Teorema: Se A, B e C são conjuntos 
quaisquer então A � (B U C) = (A � B) U (A 
� C)
� Temos que provar que 
� A � (B U C) (A � B) U (A � C)
� (A � B) U (A � C) A � (B U C) 
� Por definição X = Y se e somente se 
X Y e Y X
OK
Prova Direta
� (A � B) U (A � C) A � (B U C) 
� Suponha x ∈ (A � B) U (A � C)
Prova Direta
� (A � B) U (A � C) A � (B U C) 
x ∈ (A � B) U (A � C) definição de união
x ∈ (A � B) ou x ∈ (A � C) definição de intersecção
( x ∈ A e x ∈ B) ou ( x ∈ A e x ∈ C) distributividade sobre e/ou
x ∈ A e (x ∈ B ou x ∈ C) definição união
x ∈ A e x ∈ (B U C) definição de intersecção
x ∈ A � (B U C)
Prova Direta
� (A � B) U (A � C) A � (B U C) 
x ∈ (A � B) U (A � C) definição de união
x ∈ (A � B) ou x ∈ (A � C) definição de intersecção
( x ∈ A e x ∈ B) ou ( x ∈ A e x ∈ C) distributividade sobre e/ou
x ∈ A e (x ∈ B ou x ∈ C) definição união
x ∈ A e x ∈ (B U C) definição de intersecção
x ∈ A � (B U C)
Prova Direta
� (A � B) U (A � C) A � (B U C) 
x ∈ (A � B) U (A � C) definição de união
x ∈ (A � B) ou x ∈ (A � C) definição de intersecção
( x ∈ A e x ∈ B) ou ( x ∈ A e x ∈ C) distributividade sobre e/ou
x ∈ A e (x ∈ B ou x ∈ C) definição união
x ∈ A e x ∈ (B U C) definição de intersecção
x ∈ A � (B U C)
Prova Direta
� (A � B) U (A � C) A � (B U C) 
x ∈ (A � B) U (A � C) definição de união
x ∈ (A � B) ou x ∈ (A � C) definição de intersecção
( x ∈ A e x ∈ B) ou ( x ∈ A e x ∈ C) distributividade sobre e/ou
x ∈ A e (x ∈ B ou x ∈ C) definição união
x ∈ A e x ∈ (B U C) definição de intersecção
x ∈ A � (B U C)
Prova Direta
� (A � B) U (A � C) A � (B U C) 
x ∈ (A � B) U (A � C) definição de união
x ∈ (A � B) ou x ∈ (A � C) definição de intersecção
( x ∈ A e x ∈ B) ou ( x ∈ A e x ∈ C) distributividade sobre e/ou
x ∈ A e (x ∈ B ou x ∈ C) definição união
x ∈ A e x ∈ (B U C) definição de intersecção
x ∈ A � (B U C)
Prova Direta
� (A � B) U (A � C) A � (B U C) 
x ∈ (A � B) U (A � C) definição de união
x ∈ (A � B) ou x ∈ (A � C) definição de intersecção
( x ∈ A e x ∈ B) ou ( x ∈ A e x ∈ C) distributividade sobre e/ou
x ∈ A e (x ∈ B ou x ∈ C) definição união
x ∈ A e x ∈ (B U C) definição de intersecção
x ∈ A � (B U C)
Prova por Contraposição
� p � q ≡ ~q � ~p
� Exemplo:
� Para todos os números Naturais n, se n! > (n+1) 
então n>2
Prova por Contraposição
� p � q ≡ ~q � ~p
� Exemplo:
� Para todos os números Naturais n, se n! > (n+1) 
então n>2
� Demonstrar o equivalente:
� n! > (n+1) � n>2
� n � 2 � n! � n+1
Prova por Contraposição
� p � q ≡ ~q � ~p
� Exemplo:
� Para todos os números Naturais n, se n! > (n+1) 
então n>2
� Demonstrar o equivalente:
� n! > (n+1) � n>2
� n � 2 � n! � n+1
� Basta testar os caso n=0, n=1 e n=2
Prova por Redução ao 
Absurdo
� Quando p � q consiste em supor a hipótese 
p, supor a negação da tese ~q e concluir por 
contradição.� Prova por contra exemplo ou por contradição
Prova por Absurdo
� Se 3n+2 é impar, então n é impar.
3n+2 é impar � n é impar
p � q
Prova por Absurdo
� Se 3n+2 é impar, então n é impar.
3n+2 é impar � n é impar
1. Assumir que p e ~q são verdadeiras
3n+2 é impar
n é par
Prova por Absurdo
� Se 3n+2 é impar, então n é impar.
1. 3n+2 é impar e n é par (p�~q)
Por definição, se n é par então existe um 
inteiro k tal que n=2k.
Prova por Absurdo
� Se 3n+2 é impar, então n é impar.
1. 3n+2 é impar e n é par
Por definição, se n é par então existe um 
inteiro k tal que n=2k.
Isso implica que!!!!
Prova por Absurdo
� Se 3n+2 é impar, então n é impar.
1. 3n+2 é impar e n é par
Por definição, se n é par então existe um 
inteiro k tal que n=2k.
3n+2 = 3(2k)+2
Prova por Absurdo
� Se 3n+2 é impar, então n é impar.
1. 3n+2 é impar e n é par
3n+2 = 3(2k)+2
= 6k + 2
= 2 (3k+1)
= 2 t onde t=(3k+1)
logo 3n+2 é par
Prova por Absurdo
� Se 3n+2 é impar, então n é impar.
1. 3n+2 é impar e n é par
3n+2 = 3(2k)+2 = 6k + 2 = 2 (3k+1)
= 2 t onde t=(3k+1)
logo 3n+2 é par
2. Encontramos que ~p é verdadeiro
Prova por Absurdo
� Se 3n+2 é impar, então n é impar.
1. 3n+2 é impar e n é par
3n+2 = 3(2k)+2 = 6k + 2 = 2 (3k+1)
= 2 t onde t=(3k+1)
logo 3n+2 é par
2. Encontramos que ~p é verdadeiro
3. Em 1. assumi que p é verdadeiro, 
contradição p ^ ~p
Prova por Absurdo
� Se 3n+2 é impar, então n é impar.
1. 3n+2 é impar e n é par
3n+2 = 3(2k)+2 = 6k + 2 = 2 (3k+1)
= 2 t onde t=(3k+1)
logo 3n+2 é par
2. Encontramos que ~p é verdadeiro
3. Contradição p ^ ~p. Logo ~q é falso e n é
impar.
Indução
� O princípio da indução matemática é um 
técnica para lidar com tipos de dados que 
têm uma relação de boa ordem, isto é, uma 
relação onde todo subconjunto não vazio do 
tipo de dado tem um elemento mínimo 
segundo essa relação de ordem.
Indução
� Base da indução: a proposição p(m)
� Hipótese de indução: a proposição p(k)
� Passo de indução: a implicação p(k) => 
p(k+1)
Prova Indutiva
� Teorema:
� Para qualquer n ∈ N, vale que n! = (n2+n)/2
Prova Indutiva
� Teorema:
� Para qualquer n ∈ N, vale que Σi, 0 � i � n = 
(n2+n)/2
� Prova
� Base de Indução
Seja k = 0. 
0 = (02+0)/2 
0 = 0/2 
Portanto, p(0) é verdadeira.
Prova Indutiva
� Hipótese de Indução: 
Suponha que, para algum k ∈ N, 
Σi, 0 � i � k = (k2+k)/2 é verdadeira.
Prova Indutiva
� Passo da Indução:
� Provar para p(k+1) ou seja 
Σi, 0 � i � k+1) = ((k+1)2+(k+1))/2 
1+2+...+k+ (k+1) = ((k+1)2+k+1)/2 
Prova Indutiva
Σi, 0 � i � k+1) =
= 1+2+...+k+(k+1) 
= (1+2+...+k)+(k+1) pela hipótese indutiva
= (k2+k)/2+(k+1)
= (k2+k)/2+(2k+2)/2
= (k2+k+2k+2)/2
= ((k2+2k+1)+(k+1))/2
= ((k+1)2+(k+1))/2
Logo: p(k+1):(k+1)! = ((k+1)2+k+1)/2 é verdadeira.
Erros nas Demonstrações
� Os erros mais comuns são erros em 
aritmética e álgebra básica.
1 = 2
� Seja a,b dois inteiros positivos
Passo Razão
1. a=b dado
Multiplicar ambos os membros por a
1 = 2
� Seja a,b dois inteiros positivos
Passo Razão
1. a=b dado
2. a2 = ab x a
Subtrair b2 de ambos os lados
1 = 2
� Seja a,b dois inteiros positivos
Passo Razão
1. a=b dado
2. a2 = ab x a
3. a2 - b2 = ab - b2 - b2
Fatorar ambos os lados
1 = 2
� Seja a,b dois inteiros positivos
Passo Razão
1. a=b dado
2. a2 = ab x a
3. a2 - b2 = ab - b2 - b2
4. (a-b)(a+b) = b(a-b) fatorar
dividir ambos os lados por (a-b)
1 = 2
� Seja a,b dois inteiros positivos
Passo Razão
1. a=b dado
2. a2 = ab x a
3. a2 - b2 = ab - b2 - b2
4. (a-b)(a+b) = b(a-b) fatorar
5. a+b = b /(a-b)
Substituir a por b
1 = 2
� Seja a,b dois inteiros positivos
Passo Razão
1. a=b dado
2. a2 = ab x a
3. a2 - b2 = ab - b2 - b2
4. (a-b)(a+b) = b(a-b) fatorar
5. a+b = b /(a-b)
6. 2b = b a=b
Dividir por b
1 = 2
� Seja a,b dois inteiros positivos
Passo Razão
1. a=b dado
2. a2 = ab x a
3. a2 - b2 = ab - b2 - b2
4. (a-b)(a+b) = b(a-b) fatorar
5. a+b = b /(a-b)
6. 2b = b a=b
7. 2 = 1 /b
1 = 2
� Seja a,b dois inteiros positivos
Passo Razão
1. a=b dado
2. a2 = ab x a
3. a2 - b2 = ab - b2 - b2
4. (a-b)(a+b) = b(a-b) fatorar
5. a+b = b /(a-b)
6. 2b = b a=b
7. 2 = 1 /b
1 = 2
� Seja a,b dois inteiros positivos
Passo Razão
1. a=b dado
2. a2 = ab x a
3. a2 - b2 = ab - b2 - b2
4. (a-b)(a+b) = b(a-b) fatorar
5. a+b = b /(a-b)
6. 2b = b a=b
7. 2 = 1 /b
(a-b)=0 sendo 
assim não 
podemos fazer 
a divisão