Md TecnicasDemonstracao

Técnicas de demonstração

Prof. Eduardo Bezerra

Centro Federal de Educação Tecnológica Celso Suckow da Fonceca (CEFET/RJ)Departamento Acadêmico de Informática (DEPIN)

6 de Outubro de 2013

Eduardo Bezerra (CEFET/RJ) Matemática Discreta 1 / 21

Roteiro

1 Introdução

2 Demonstração direta

3 Demonstração por contraposição

4 Demonstração por contradição (redução ao absurdo)

5 Demonstração por indução matemática


Teorema

Um teorema é uma proposição do tipo

p → q

em quep é denominada hipótese;q é denominada tese.

Técnicas de demonstração são usadas para comprovar a veracidadede teoremas.


Quantificadores universal e existencial

Em qualquer técnica de demonstração, deve-se ter especial atençãoaos quantificadores envolvidos no teorema.

provar a proposição (∀x ∈ A)p(x)isso significa provar para todo x ∈ Amostrar 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 ∈ Aaqui, um exemplo é uma prova (compare com o caso universal)


Roteiro

1 Introdução






Prova direta

Na demonstração de que p → q:hipótese p é suposta verdadeiranão deve ser demonstrada


Prova direta

Pressupõe verdadeira a hipótese e, a partir desta, prova serverdadeira a tese.


Prova direta - exemplo

Afirmação: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 é umnúmero par


Prova direta - exemplo (cont.)

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 ∈ Ntais 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.


Roteiro

1 Introdução






Prova por contraposição

Baseia-se no resultado denominado contraposição:

p → q ⇔ ¬q → ¬p

Como exercício, construa as tabelas verdades de ambos os lados dabicondicional acima para comprovar que a proposiçõescorrespondentes são realmente equivalentes.


Prova por contraposição

Para provar p → q, prova-se ¬q → ¬p (por prova direta)

a partir de ¬qobter ¬p


Prova por contraposição - exemplo

Prove (usando a técnica de contraposição) que

n! > (n + 1)→ n > 2


Roteiro

1 Introdução






Demonstração por contradição (redução ao absurdo)

Para provar p → q:

supor que a hipótese p é verdadeirasupor que a negação da tese ¬q é verdadeiraconcluir uma contradição (em geral, q ou ¬q)


Roteiro

1 Introdução






Princípio da Indução Matemática

Princípio da Indução MatemáticaUma propriedade P qualquer é válida para ∀n ≥ n0,n,n0 ∈ Z, se forpossível provar que:

1 P(n0) é válida;2 ∀k ∈ Z tal que k ≥ n0, P(k)→ P(k + 1).



Uma analogia: a escada infinita.



Outra analogia: a cadeia de dominós.


Princípio da indução matemática

A indução matemática pode ser resumida na seguinte regra deinferência.

Regra de inferência

(P(n0) ∧ ∀k(P(k)→ P(k + 1))→ ∀n P(n)


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 considerarseja especificada.Passo 2: (hipótese indutiva): considere que P(k) é verdadeira.Passo 3: (passo indutivo): mostre que P(k)→ P(k + 1), paratodos os números naturais k tais que k ≥ n0.


Documents

Md TecnicasDemonstracao