View
216
Download
1
Category
Preview:
Citation preview
Introducao aos Metodos de Prova
Renata de Freitas e Petrucio VianaIME-UFF, Niteroi/RJ
II Coloquio de Matematica da Regiao SulUEL, Londrina/PR
24 a 28 de abril 2012
Sumario
• Provas servem, principalmente, para convencer os outros.
I Enunciados.
I Metodos de prova.
I Metodo da Suposicao.
I Metodo da Contraposicao.
I Metodo da Reducao ao Absurdo.
I Metodo da Generalizacao.
I Propriedades das provas.
Enunciados
Um enunciado e uma expressao da linguagem matematica quepode ser classificada como verdadeira ou falsa, de maneiraexclusiva, em um dado contexto.
(a) 2 e par.
(b) O conjunto dos numeros naturais e o conjunto dosquadrados de numeros naturais possuem a mesmaquantidade de elementos.
(c) Se n e par, entao n2 e par.
Provas e metodos de prova
Uma prova e uma maneira de certificar (ou justificar oucompreender) a veracidade (ou a falsidade) de um enunciado.
Um metodo de prova e uma maneira de certificar um enunciado,fazendo outra coisa.
Esta outra coisa pode ser — e usualmente e — uma prova de umoutro enunciado.
Metodo probabilıstico
Descoberto por T. Szele, em 1943, e desenvolvido e divulgado porP. Erdos e seus colaboradores.
Metodo probabilıstico
Para provar um enunciado da forma
∃x ∈ U, tal que ϕ(x),
faca o seguinte:
– Defina uma distribuicao de probabilidades adequada noespaco U;
– Prove que a probabilidade de um objeto qualquer u ∈ Usatisfazer ϕ(x) e positiva.
– Conclua que ∃x ∈ U, tal que ϕ(x) foi provada.
Exemplo
O oceano cobre mais que a metade da superfıcie da Terra.
Proposicao Existem dois pontos antipodais na superfıcie daTerra que sao cobertos pela agua.
Prova pelo metodo probabilıstico:
Seja X um ponto aleatorio na superfıcie da Terra.
Considere os eventos:
A : X e coberto pela agua
B : O antipodal a X e coberto pela agua
Temos que P(A) > 12 e P(B) > 1
2 .
Assim, P(A ∩ B) = P(A) + P(B)︸ ︷︷ ︸>1
−P(A ∪ B)︸ ︷︷ ︸≤1
e nao negativa.
Em resumo
O metodo probabilıstico nos diz que para provar que
∃x ∈ U, tal que ϕ(x)
e verdadeiro, basta provar que
P({x ∈ U : ϕ(x)}) 6= 0.
Um metodo de prova e uma “receita” que diz que, para provar umenunciado, basta provar um outro enunciado, possivelmente maissimples.
Metodos de prova
Vamos, agora, discutir alguns dos principais metodos de provas.
Metodo Direto ou Metodo da Suposicao
Para provar um enunciado da forma
se α, entao β
a partir dos enunciados ϕ1, ϕ2, . . . , ϕn, basta:
I Supor α.
I Provar β a partir de ϕ1, ϕ2, . . . , ϕn e α.
Exemplo 1
Proposicao Se n e par, entao n2 e par.
Prova (pelo metodo da suposicao):
Suponha que n e par.
Daı, n = 2k, onde k ∈ N.
Daı, n2 = (2k)2 = 22k2 = 2 · 2 · k2 = 2(2k2), onde 2k2 ∈ N.
Logo, n2 e par.
Exemplo 2
Proposicao Se n2 e par, entao n e par.
Prova (pelo metodo da suposicao):
Suponha que n2 e par.
Daı, n2 = 2k, onde k ∈ N.
Daı, 2 | n2.
(Se um numero primo divide um produto,ele divide algum dos fatores.)
Daı, 2 | n.
Logo, n2 e par.
Observacao
Provas utilizam conhecimento previo!
Exercıcios
Faca provas diretas.
(1) Se n e ımpar, entao n2 e ımpar.
(2) Se n2 e ımpar, entao n e ımpar.
Em resumo
O Metodo da Suposicao:
I agrega conhecimento previo e
I troca o enunciado a ser prova por outro mais simples.
""FFFF
FFFF
FFF
��...
....
||xxxx
xxxx
xxx
ϕ1 ϕ2 · · · ϕn
se α entao βGF ED@A BC=⇒&&LLLLLLLLLLLLL
��<<<
<<<<
<<
������
����
�
yysssssssssssssϕ1 ϕ2 · · · ϕn α
β?> =<89 :;
Ele e um verdadeiro metodo de prova!!!
Metodo da contraposicao
Para provar se α, entao β a partir de ϕ1, . . . , ϕn, basta:
I Supor nao β.
I Provar nao α a partir de ϕ1, . . . , ϕn e nao β.
Ou seja, para provar se α, entao β, bastaaplicar o metodo direto em se nao β, entao nao α.
Exemplo 1
Voltemos ao exercıcio (2).
Proposicao Se n2 e ımpar, entao n e ımpar.
Segundo o Metodo da Contraposicao, para provar
se n2 e ımpar, entao n e ımpar,
basta usar o Metodo da Suposicao para provar
se n nao e ımpar, entao n2 nao e ımpar.
Mas este enunciado e equivalente a
se n e par, entao n2 e par,
que ja foi provado.
Exemplo 2
Proposicao Se a e irracional, entao√
a e irracional.
Segundo o Metodo da Contraposicao, para provar
se a e irracional, entao√
a e irracional,
basta usar o Metodo da Suposicao para provar
se√
a e racional, entao a e racional.
Prova (pelo metodo da contraposicao):
Suponha que√
a e racional.
Daı,√
a =m
n, onde m, n ∈ N e n 6= 0.
Daı, a = (√
a)2 =(m
n
)2=
m2
n2, onde m2, n2 ∈ N e n2 6= 0.
Logo, a e racional.
Para usar este metodo, e preciso saber negar um enunciado.
Exemplo
Proposicao Se x + y = 10, entao x 6= 3 e y 6= 8.
Prova:
Suponha que x = 3 e y = 8.
Daı, x + y = 11.
Logo, x + y 6= 10.
Qual e o erro nesta prova?
Em resumo
O Metodo da Contraposicao:
I agrega conhecimento previo e
I troca o enunciado a ser provado por outro mais simples.
""FFFF
FFFF
FFF
��...
....
||xxxx
xxxx
xxx
ϕ1 ϕ2 · · · ϕn
se α entao βGF ED@A BC=⇒
&&LLLLLLLLLLLLL
��<<<
<<<<
<<
������
����
�
yysssssssssssssϕ1 ϕ2 · · · ϕn nao β
nao α?> =<89 :;
Metodo da Reducao ao Absurdo
Para provar um enunciado αa partir dos enunciados ϕ1, ϕ2, . . . , ϕn, basta:
I Supor nao α.
I Provar uma contradicao a partir de ϕ1, . . . , ϕn e nao α.
Exemplo 1
Proposicao Se n2 e par, entao n e par.
Prova (pelos metodos da suposicao e da reducao ao absurdo):
Suponha que n2 e par.(para provar que n e par).
Suponha que n nao e par(para provar uma contradicao, a partir de n2 e par).
Daı, n e ımpar, ou seja, n = 2k + 1, onde k ∈ N.
Daı, n2 = 4k2 +4k +1 = 2(2k2 +2k)+1, ou seja, n2 e ımpar,uma contradicao com n2 e par.
Logo, n e par.
Exemplo 2
Proposicao√
2 e um numero irracional.
Prova (pelo metodo da reducao ao absurdo):
Suponha que√
2 e racional.
Daı,√
2 =a
b, onde a, b ∈ N, b 6= 0 e mdc(a, b) = 1.
Daı, 2b2 = a2.
Daı, a e par.
Ou seja, a = 2k, onde k ∈ N.
Daı, 2b2 = 22k2 = 2(2k2) e, assim, b2 = 2k2.
Daı, b e par.
Logo, mdc(a, b) ≥ 2, uma contradicaocom mdc(a, b) = 1.
Em resumo
O Metodo da Reducao ao Absurdo:
I agrega conhecimento previo, mas
I nao direciona a prova.
""FFFF
FFFF
FFF
��...
....
||xxxx
xxxx
xxx
ϕ1 ϕ2 · · · ϕn
α?> =<89 :;=⇒&&LLLLLLLLLLLLL
��<<<
<<<<
<<
������
����
�
yysssssssssssssϕ1 ϕ2 · · · ϕn nao α
contradicaoGF ED@A BC
E facil se perder usando este metodo!!!
Exemplo
Proposicao Existe uma quantidade infinita denumeros primos.
Prova (pelo metodo da reducao ao absurdo):
Suponha que existe uma quantidade finita de numeros primos.
Sejam p1, p2, . . . , pn todos os numeros primos.
Considere m = p1 · p2 · · · · · pn + 1.
Temos que p1 6 |m, p2 6 |m, . . . , pn 6 |m.
Mas, pelo Teorema Fundamental da Aritmetica,m tem um fator primo.
Assim, existe um primo p diferente de p1, p2, . . . , pn, umacontradicao.
Exercıcios
Faca uma prova direta.
Para todo n ∈ N,se p1, p2, . . . , pn sao numeros primos,entao existe p que e primo e e diferente de p1, p2, . . . , pn.
Metodo de Generalizacao
Para provar um enunciado da forma
para todo x ∈ A, α(x)
a partir dos enunciados ϕ1, ϕ2, . . . , ϕn, basta:
I Considerar x como um elemento qualquer de A.
I Provar α(x) a partir de ϕ1, . . . , ϕn usandoapenas propriedades de x que x compartilha com todos oselementos de A.
Exemplo
Proposicao Para todo x ∈ N, se n e par, entao nx e par.
Ja fizemos uma prova para o caso em que x = 2 ∈ N:
Seja 2 ∈ N.
Suponha que n e par.
Daı, n = 2k, onde k ∈ N.
Daı, n2 = (2k)2 = 22k2 = 2(2k2), onde 2k2 ∈ N.
Logo, n2 e par.
Mas as propriedades do 2 que usamos e compartilhada pelo 2 comtodos os numeros naturais.
Seja x ∈ N.
Suponha que n e par.
Daı, n = 2k, onde k ∈ N.
Daı, nx = (2k)x = 2xkx = 2(2x−1kx), onde 2x−1kx ∈ N.
Logo, nx e par.
Exemplo
Proposicao Se x e primo, entao√
x e um numero irracional.
Ja fizemos uma prova para o caso em que x = 2 ∈ N:
Suponha que√
2 e racional.
Daı,√
2 =a
b, onde a, b ∈ N, b 6= 0 e mdc(a, b) = 1.
Daı, 2b2 = a2.
Daı, 2 | a2 e, assim, 2 | a.
Ou seja, a = 2k, onde k ∈ N.
Daı, 2b2 = 2(2k2) e, assim, b2 = 2k2.
Daı, 2 | b2 e, assim, 2 | b.
Logo, mdc(a, b) ≥ 2, uma contradicao.
Mas as propriedades do 2 que usamos e compartilhada pelo 2 comtodos os numeros primos.
Seja x um numero primo.
Suponha que√
x e racional.
Daı,√
x =a
b, onde a, b ∈ N, b 6= 0 e mdc(a, b) = 1.
Daı, xb2 = a2.
Daı, x | a2 e, assim, x | a.
Ou seja, a = xk, onde k ∈ N.
Daı, xb2 = x(xk2) e, assim, b2 = xk2.
Daı, x | b2 e, assim, x | b.
Logo, mdc(a, b) ≥ x , uma contradicao.
Em resumo
O Metodo de Generalizacao:
I especifica o tipo de conhecimento previo que pode ser usadona prova: somente propriedades que sao genericas em A, ouseja, que valem para todos os elementos de A.
I troca o enunciado a ser provado por outro mais simples.
((QQQQQQQQQ
��:::
::
vvmmmmmmmmmϕ1 ϕ2 · · · ϕn
Para todo x ∈ A, α(x)GF ED@A BC=⇒((QQQQQQQQQ
��:::
::
vvmmmmmmmmmϕ1 ϕ2 · · · ϕn
α(x)GF ED@A BC
genericas em A
Nao e facil usar este metodo!!!
Ate amanha!
http://www.uff.br/grupodelogica
Recommended