Aula 6 - Técnicas de Demonstração

Prévia do material em texto

Técnicas de demonstração
Prof. Diego Brandão
Centro Federal de Educação Tecnológica Celso Suckow da Fonceca (CEFET/RJ)
Departamento Acadêmico de Informática (DEPIN)
2 de Maio de 2019
Diego Brandão (CEFET/RJ) Matemática Discreta 1 / 1
Roteiro
Diego Brandão (CEFET/RJ) Matemática Discreta 2 / 1
Terminologia básica
Um axioma é uma afirmação que é dada para ser verdade.
Uma regra de inferência é uma regra lógica usada para deduzir
uma declaração a partir de outra(s).
Um teorema é uma proposição que pode ser provada usando
definições, axiomas, outros teoremas e regras de inferência.
Uma conjectura é um teorema que ainda não foi provado (nem
refutado).
Diego Brandão (CEFET/RJ) Matemática Discreta 3 / 1
Terminologia básica
Um teorema é uma proposição do tipo
p → q
em que
p e q são proposições (possivelmente compostas);
p é denominada hipótese;
q é denominada conclusão (ou tese).
Técnicas de demonstração são usadas para comprovar a veracidade
de teoremas.
Diego Brandão (CEFET/RJ) Matemática Discreta 4 / 1
Quantificadores universal e existencial
Em qualquer técnica de demonstração, deve-se ter especial atenção
aos quantificadores envolvidos no teorema.
provar a proposição (∀x ∈ A)p(x)
isso significa provar para todo x ∈ A
mostrar para um elemento a ∈ A é um exemplo e não uma prova.
provar a proposição (∃x ∈ A)p(x)
basta provar para algum a ∈ A
aqui, um exemplo é uma prova (compare com o caso universal)
Diego Brandão (CEFET/RJ) Matemática Discreta 5 / 1
Roteiro
Diego Brandão (CEFET/RJ) Matemática Discreta 6 / 1
Demontração direta
A demonstração direta é utilizada para provar declarações do tipo
p → q, onde p e q são proposições possivelmente compostas.
p é denominada hipótese;
q é denominada conclusão;
Essa técnica pressupõe verdadeira a hipótese e, a partir desta,
prova ser verdadeira a conclusão.
Na demonstração de que p → q, a hipótese p é suposta
verdadeira, i.e., não deve ser demonstrada.
Diego Brandão (CEFET/RJ) Matemática Discreta 7 / 1
Prova direta
Exemplo
Prove que a soma de dois números pares é um número par.
Para aplicar a prova direta, devemos reescrever na forma de p → q:
se n e m são dois números pares quaisquer, então n +m é um
número par.
Prova. Qualquer par n pode ser definido como n = 2r , para algum
natural r . Suponha que n e m são dois pares quaisquer. Então
existem r , s ∈ N tais que n = 2r e m = 2s. Portanto
n +m = 2r + 2s = 2(r + s)
A soma de dois naturais r + s é natural, n+m = 2(r + s). Logo, n+m
é um número par.
Diego Brandão (CEFET/RJ) Matemática Discreta 8 / 1
Prova direta
Exemplo
Prove que a soma de dois números pares é um número par.
Para aplicar a prova direta, devemos reescrever na forma de p → q:
se n e m são dois números pares quaisquer, então n +m é um
número par.
Prova. Qualquer par n pode ser definido como n = 2r , para algum
natural r . Suponha que n e m são dois pares quaisquer. Então
existem r , s ∈ N tais que n = 2r e m = 2s. Portanto
n +m = 2r + 2s = 2(r + s)
A soma de dois naturais r + s é natural, n+m = 2(r + s). Logo, n+m
é um número par.
Diego Brandão (CEFET/RJ) Matemática Discreta 8 / 1
Prova direta
Exemplo
Prove que a soma de dois números pares é um número par.
Para aplicar a prova direta, devemos reescrever na forma de p → q:
se n e m são dois números pares quaisquer, então n +m é um
número par.
Prova. Qualquer par n pode ser definido como n = 2r , para algum
natural r . Suponha que n e m são dois pares quaisquer. Então
existem r , s ∈ N tais que n = 2r e m = 2s. Portanto
n +m = 2r + 2s = 2(r + s)
A soma de dois naturais r + s é natural, n+m = 2(r + s). Logo, n+m
é um número par.
Diego Brandão (CEFET/RJ) Matemática Discreta 8 / 1
Roteiro
Diego Brandão (CEFET/RJ) Matemática Discreta 9 / 1
Prova por contraposição
Essa técnica se baseia no resultado denominado contraposição:
p → q ⇔ ¬q → ¬p
Como exercício, construa as tabelas verdades de ambos os lados da
bicondicional acima para comprovar que a proposições
correspondentes são realmente equivalentes.
Diego Brandão (CEFET/RJ) Matemática Discreta 10 / 1
Prova por contraposição
Prova por contraposição
Por meio da técnica de demonstração por contraposição, para provar
uma proposição do tipo p → q, prova-se ¬q → ¬p por prova direta.
a partir de ¬q
obter ¬p
Diego Brandão (CEFET/RJ) Matemática Discreta 11 / 1
Prova por contraposição - exemplo
Exemplo
Prove que, para todos os inteiros m e n, se o produto de m e n é par,
então m é par ou n é par.
Vamos provar a contrapositiva da declaração fornecida: se m e n são
ambos inteiros ímpares, então mn é ímpar.
Prova. Suponha que m e n são inteiros ímpares arbitrários. Então
m = 2a+ 1 e n = 2b + 1, onde a e b são inteiros. Então
mn = (2a+ 1)(2b + 1) (substituição)
4ab + 2a+ 2b + 1
(leis associativa, distributiva e comutativa)
2(2ab + a+ b) + 1 (lei distributiva)
Posto que mn é o dobro de um inteiro mais 1, então mn é ímpar.
Diego Brandão (CEFET/RJ) Matemática Discreta 12 / 1
Prova por contraposição - exemplo
Exemplo
Prove que, para todos os inteiros m e n, se o produto de m e n é par,
então m é par ou n é par.
Vamos provar a contrapositiva da declaração fornecida:
se m e n são
ambos inteiros ímpares, então mn é ímpar.
Prova. Suponha que m e n são inteiros ímpares arbitrários. Então
m = 2a+ 1 e n = 2b + 1, onde a e b são inteiros. Então
mn = (2a+ 1)(2b + 1) (substituição)
4ab + 2a+ 2b + 1
(leis associativa, distributiva e comutativa)
2(2ab + a+ b) + 1 (lei distributiva)
Posto que mn é o dobro de um inteiro mais 1, então mn é ímpar.
Diego Brandão (CEFET/RJ) Matemática Discreta 12 / 1
Prova por contraposição - exemplo
Exemplo
Prove que, para todos os inteiros m e n, se o produto de m e n é par,
então m é par ou n é par.
Vamos provar a contrapositiva da declaração fornecida: se m e n são
ambos inteiros ímpares, então mn é ímpar.
Prova. Suponha que m e n são inteiros ímpares arbitrários. Então
m = 2a+ 1 e n = 2b + 1, onde a e b são inteiros. Então
mn = (2a+ 1)(2b + 1) (substituição)
4ab + 2a+ 2b + 1
(leis associativa, distributiva e comutativa)
2(2ab + a+ b) + 1 (lei distributiva)
Posto que mn é o dobro de um inteiro mais 1, então mn é ímpar.
Diego Brandão (CEFET/RJ) Matemática Discreta 12 / 1
Prova por contraposição - exemplo
Exemplo
Prove que, para todos os inteiros m e n, se o produto de m e n é par,
então m é par ou n é par.
Vamos provar a contrapositiva da declaração fornecida: se m e n são
ambos inteiros ímpares, então mn é ímpar.
Prova. Suponha que m e n são inteiros ímpares arbitrários. Então
m = 2a+ 1 e n = 2b + 1, onde a e b são inteiros. Então
mn = (2a+ 1)(2b + 1) (substituição)
4ab + 2a+ 2b + 1
(leis associativa, distributiva e comutativa)
2(2ab + a+ b) + 1 (lei distributiva)
Posto que mn é o dobro de um inteiro mais 1, então mn é ímpar.
Diego Brandão (CEFET/RJ) Matemática Discreta 12 / 1
Prova por contraposição - exemplo
Exemplo
Prove que, para qualquer inteiro a, se a2 é par, então a é par.
Prova. Suponha que a é um inteiro ímpar arbitrário. Então a = 2k + 1,
onde k é inteiro. Então
aa = (2k + 1)(2k + 1) (substituição)
4k2 + 2k + 2k + 1 (leis associativa, distributiva e comutativa)
2(2k2 + 2k) + 1 (lei distributiva)
Posto que a2 é o dobro de um inteiro mais 1, então a2 é ímpar.
Repare que está declaração é um caso particular da declaração
provada no exemplo anterior.
Diego Brandão (CEFET/RJ) Matemática Discreta 13 / 1
Prova por contraposição - exemplo
Exemplo
Prove que, para qualquer inteiro a, se a2 é par, então a é par.
Prova. Suponha que a é um inteiro ímpar arbitrário. Então a = 2k + 1,
onde k é inteiro. Então
aa = (2k + 1)(2k + 1) (substituição)
4k2 + 2k + 2k + 1 (leis associativa, distributiva e comutativa)
2(2k2+ 2k) + 1 (lei distributiva)
Posto que a2 é o dobro de um inteiro mais 1, então a2 é ímpar.
Repare que está declaração é um caso particular da declaração
provada no exemplo anterior.
Diego Brandão (CEFET/RJ) Matemática Discreta 13 / 1
Prova por contraposição - exemplo
Exemplo
Prove que, para qualquer inteiro a, se a2 é par, então a é par.
Prova. Suponha que a é um inteiro ímpar arbitrário. Então a = 2k + 1,
onde k é inteiro. Então
aa = (2k + 1)(2k + 1) (substituição)
4k2 + 2k + 2k + 1 (leis associativa, distributiva e comutativa)
2(2k2 + 2k) + 1 (lei distributiva)
Posto que a2 é o dobro de um inteiro mais 1, então a2 é ímpar.
Repare que está declaração é um caso particular da declaração
provada no exemplo anterior.
Diego Brandão (CEFET/RJ) Matemática Discreta 13 / 1
Prova por contraposição - exercício
Exercício
Prove (usando a técnica de contraposição) que
[n! > (n + 1)]→ (n > 2)
Diego Brandão (CEFET/RJ) Matemática Discreta 14 / 1
Roteiro
Diego Brandão (CEFET/RJ) Matemática Discreta 15 / 1
Demonstração por contradição (redução ao absurdo)
Demonstração por contradição
Para provar p → q por meio da técnica de demonstração por
contradição, os passos são os seguintes:
supor que a hipótese p é verdadeira
supor que a negação da tese ¬q é verdadeira
concluir uma contradição (em geral, q ou ¬q)
Diego Brandão (CEFET/RJ) Matemática Discreta 16 / 1
Prova por contradição - exemplo
Exemplo
Prove que, se x e y são números reais, e que 5x + 25y = 1723, então
x ou y não é inteiro.
Prova. Considere que x e y são tais que 5x + 25y = 1723, e que x e
y são inteiros. Pela propriedade distributiva, temos que
5(x + 5y) = 1723
Posto que x e y são inteiros, a implicação é que 5 divide 1723, o que
claramente não é verdade. Essa contradição prova que não é verdade
que x e y são ambos inteiros. Portanto, x ou y não é inteiro.
Diego Brandão (CEFET/RJ) Matemática Discreta 17 / 1
Prova por contradição - exemplo
Exemplo
Prove que, se x e y são números reais, e que 5x + 25y = 1723, então
x ou y não é inteiro.
Prova. Considere que x e y são tais que 5x + 25y = 1723, e que x e
y são inteiros. Pela propriedade distributiva, temos que
5(x + 5y) = 1723
Posto que x e y são inteiros, a implicação é que 5 divide 1723, o que
claramente não é verdade. Essa contradição prova que não é verdade
que x e y são ambos inteiros. Portanto, x ou y não é inteiro.
Diego Brandão (CEFET/RJ) Matemática Discreta 17 / 1
Prova por contradição - exemplo
Exemplo
Prove que
√
2 é um número irracional.
Prova. Essa prova se baseia no fato de que qualquer número racional
pode ser escrito como a/b, onde a e b são primos entre si (i.e., não
possuem fatores em comum).
Suponha que
√
2 é racional, de modo que podemos escrever
√
2 = m/n (1)
onde m e n são primos entre si. Eleve ao quadrado ambos os lados da
Eq (??) e então multiplique ambos por n2:
2n2 = m2. (2)
Diego Brandão (CEFET/RJ) Matemática Discreta 18 / 1
Prova por contradição - exemplo
Exemplo
Prove que
√
2 é um número irracional.
Prova. Essa prova se baseia no fato de que qualquer número racional
pode ser escrito como a/b, onde a e b são primos entre si (i.e., não
possuem fatores em comum).
Suponha que
√
2 é racional, de modo que podemos escrever
√
2 = m/n (1)
onde m e n são primos entre si. Eleve ao quadrado ambos os lados da
Eq (??) e então multiplique ambos por n2:
2n2 = m2. (2)
Diego Brandão (CEFET/RJ) Matemática Discreta 18 / 1
Prova por contradição - exemplo (cont.)
Exemplo (cont.)
Obviamente m2 é par, sendo assim m é par. Sendo assim, m = 2k
para algum inteiro k e a Eq. (??) se torna 2n2 = 4k2. Divida ambos os
lados por 2 para encontrar
n2 = 2k2
Pelo mesmo raciocínio, temos que n é par. Em resumo, se a Eq. (??)
for verdadeira, então tanto m quanto n são pares, uma contradição ao
fato de que m e n não compartilham fatores. Concluímos que a Eq.
(??) não pode ser verdadeira, e que
√
2 é irracional.
Diego Brandão (CEFET/RJ) Matemática Discreta 19 / 1
Roteiro
Diego Brandão (CEFET/RJ) Matemática Discreta 20 / 1
Princípio da Indução Matemática
Princípio da Indução Matemática
Uma propriedade P qualquer é válida para ∀n ≥ n0,n,n0 ∈ Z, se for
possível provar que:
1 P(n0) é válida;
2 ∀k ∈ Z tal que k ≥ n0, P(k)→ P(k + 1).
Diego Brandão (CEFET/RJ) Matemática Discreta 21 / 1
Princípio da Indução Matemática
Uma analogia: a escada infinita.
Diego Brandão (CEFET/RJ) Matemática Discreta 22 / 1
Princípio da Indução Matemática
Outra analogia: a cadeia de dominós.
Diego Brandão (CEFET/RJ) Matemática Discreta 23 / 1
Princípio da indução matemática
A indução matemática pode ser resumida na seguinte regra de
inferência.
Regra de inferência
(P(n0) ∧ ∀k(P(k)→ P(k + 1))→ ∀nP(n)
Diego Brandão (CEFET/RJ) Matemática Discreta 24 / 1
Prova por indução matemática
Prova por indução matemática (procedimento geral de aplicação):
Passo 1 (base da indução): corresponde a mostrar que P(n0) é
verdadeira. Observação: n0 é usualmente um número pequeno
(e.g., 0 ou 1), ao menos que uma faixa de valores a considerar
seja especificada.
Passo 2 (hipótese indutiva): considere que P(k) é verdadeira.
Passo 3 (passo indutivo): mostre que P(k)→ P(k + 1), para
todos os números naturais k tais que k ≥ n0.
Diego Brandão (CEFET/RJ) Matemática Discreta 25 / 1
Roteiro
Diego Brandão (CEFET/RJ) Matemática Discreta 26 / 1
Demonstração por casos
Demonstração por casos
A demonstração por casos consiste em dividir a conjectura que se
deseja provar em diversas partes (casos) com o propósito de
modularizar (simplificar) a tarefa de demonstração. Após essa
subdivisão, alguma técnica de demonstração previamente vista pode
ser aplicada a cada caso em particular.
Diego Brandão (CEFET/RJ) Matemática Discreta 27 / 1
Demonstração por casos - exemplo
Exemplo
Prove que existem números irracionais x e y tais que xy é racional.
Prova. Considere o número
√
2
√
2
. Esse número ou é racional ou é
irracional. Sendo assim, temos dois casos a analisar:
1) (
√
2
√
2
é racional). Nesse caso, a prova está completa.
2) (
√
2
√
2
é irracional). Nesse caso, faça x =
√
2
√
2
e y =
√
2. Dessa
forma,
xy = (
√
2
√
2
)
√
2 = (
√
2)2 = 2.
Em ambos os casos, existem números irracionais x e y tais que xy é
racional. CQD.
Diego Brandão (CEFET/RJ) Matemática Discreta 28 / 1
Demonstração por casos - exemplo
Exemplo
Prove que existem números irracionais x e y tais que xy é racional.
Prova. Considere o número
√
2
√
2
. Esse número ou é racional ou é
irracional. Sendo assim, temos dois casos a analisar:
1) (
√
2
√
2
é racional). Nesse caso, a prova está completa.
2) (
√
2
√
2
é irracional). Nesse caso, faça x =
√
2
√
2
e y =
√
2. Dessa
forma,
xy = (
√
2
√
2
)
√
2 = (
√
2)2 = 2.
Em ambos os casos, existem números irracionais x e y tais que xy é
racional. CQD.
Diego Brandão (CEFET/RJ) Matemática Discreta 28 / 1
Demonstração por casos - exemplo
Exemplo
Prove que, se n é um inteiro, então 3n2 + n + 14 é par.
Prova. Seja n ∈ Z . Vamos analisar dois casos: n é par e n é ímpar.
Caso 1. n é par.
Podemos escrever n = 2k , onde k ∈ Z . Então
3n2 + n + 14 = 3(2k)2 + 2k + 14
= 12k2 + 2k + 14
= 2(6k2 + k + 7)
Já que 6k2 + k + 7 é um inteiro, 3n2 + n + 14 é par se n for par.
Diego Brandão (CEFET/RJ) Matemática Discreta 29 / 1
Demonstração por casos - exemplo
Exemplo
Prove que, se n é um inteiro, então 3n2 + n + 14 é par.
Prova. Seja n ∈ Z . Vamos analisar dois casos: n é par e n é ímpar.
Caso 1. n é par.
Podemos escrever n = 2k , onde k ∈ Z . Então
3n2 + n + 14 = 3(2k)2 + 2k + 14
= 12k2 + 2k + 14
= 2(6k2+ k + 7)
Já que 6k2 + k + 7 é um inteiro, 3n2 + n + 14 é par se n for par.
Diego Brandão (CEFET/RJ) Matemática Discreta 29 / 1
Demonstração por casos - exemplo
Exemplo (cont.)
Caso 2. n é ímpar.
Podemos escrever n = 2k + 1, onde k ∈ Z. Então
3n2 + n + 14 = 3(2k + 1)2 + (2k + 1) + 14
= 3(4k2 + 4k + 1) + (2k + 1) + 14
= 12k2 + 12k + 3 + 2k + 1 + 14
= 12k2 + 14k + 18
= 2(6k2 + 7k + 9)
Já que 6k2 + 7k + 9 é um inteiro, 3n2 + n + 14 é par se n é ímpar.
Em ambos os casos 3n2 + n + 14 é par. Segue que se n é um inteiro,
então 3n2 + n + 14 é par. CQD.
Diego Brandão (CEFET/RJ) Matemática Discreta 30 / 1
Demonstração por casos - exercício
Exercício
Provar de que se n é qualquer número inteiro que não é divisível por
5, então n2 deixa resto igual a 1 ou 4 quando é dividido por 5.
Diego Brandão (CEFET/RJ) Matemática Discreta 31 / 1