Minicurso – Aula 7:
Técnicas de Demonstração
Matemática
Anliy Natsuyo Nashimoto Sargeant
Curso de Verão 2009
DEX - UFLA
Negação
• Antes de apresentar as demais técnicas de
demonstração, precisamos aprender a
escrever a negação de uma proposição.
• Exemplo:
A: Não existe inteiro x tal que x²+x-11=0.
A negação da proposição A é:
Não A: Existe um inteiro x tal que x²+x-11=0.
Negação
• Regras para negar uma proposição que contêm
“e” ou “ou”.
Não[A e B] transforma-se em [Não A] ou [Não B]
Não[A ou B] transforma-se em [Não A] e [Não B]
• Por exemplo:
Não[(x≥3)e(y<5)] transforma-se em[(x<3) ou (y≥5)],
Não[(x≥3)ou(y<5)] transforma-se em[(x<3) e (y≥5)].
Negação
• A situação mais desafiadora é quando a
proposição contém quantificadores.
• Por exemplo, se a proposição aparecer na
forma padrão:
B: Para todo “objeto” com uma “certa
propriedade”, “algo acontece”.
Não B: Não é caso que para todo “objeto” com
uma “certa propriedade”, “algo acontece”.
Negação
Não B: Não é caso que para todo “objeto” com
uma “certa propriedade”, “algo acontece”.
• Que na realidade significa que:
Não B: Existe um “objeto” com uma “certa
propriedade” para o qual o algo não acontece.
Negação
• Similarmente, quando a proposição contém o
quantificador “existe” na forma padrão
B: Existe um “objeto” com uma “certa
propriedade” tal que “algo acontece”.
Negação
• O negação de B é
Não B: Não é o caso que existe um “objeto” com
uma “certa propriedade” tal que “algo
acontece”.
• Em outra palavras,
Não B: Para todo “objeto” com uma “certa
propriedade” o algo não acontece.
Negação
• Vamos dar exemplos para ilustrar a idéia.
• Exemplo1: Para todo número real x ≥ 2, x²+x6≥0.
Etapa 1: NÃO [para todo número real x ≥ 2, x²+x6≥0.]
Etapa 2: Existe um número real x ≥ 2, NÃO[x²+x6≥0.]
Etapa 3: Existe um número real x ≥ 2, x²+x-6<0.
Negação
• Exemplo2: Existe um número real x ≥ 2, x²+x6≥0.
Etapa 1: NÃO [existe um número real x ≥ 2,
x²+x-6≥0.]
Etapa 2: Para todo número real x ≥ 2,
NÃO[x²+x-6≥0.]
Etapa 3: Para todo número real x ≥ 2, x²+x-6<0.
Negação
• Exemplo 3: Para todo número real x entre -1 e
1, existe um número real y entre -1 e 1 tal que
x²+y²≤1.
Etapa 1:NÃO [Para todo número real x entre -1 e
1, existe um número real y entre -1 e 1 tal que
x²+y²≤1.]
Negação
Etapa 2:Existe um número real x entre -1 e 1,
NÃO[existe um número real y entre -1 e 1 tal
que x²+y²≤1].
Etapa 2.1:Existe um número real x entre -1 e 1
tal que para todo número real y entre -1 e 1,
NÃO[ x²+y²≤1].
Etapa 3: Existe um número real x entre -1 e 1 tal
que para todo número real y entre -1 e 1,
x²+y²>1.
Contra-exemplo
• Os exemplos de proposições que vimos até
agora eram verdadeiras e portanto
conseguimos prová-las.
• Mas, a verdade de algumas proposições
matemáticas não são muito claras. Por
Exemplo,
B: Para todo inteiro n≥2,n²≥2ⁿ.
Contra-exemplo
B: Para todo inteiro n≥2,n²≥2ⁿ.
• Nós podemos verificar facilmente que B é
verdadeira para n=2,3 e 4.
• Mas se tentarmos provar a proposição
utilizando o método por escolha, vamos falhar,
pois a proposição é falsa.
• Em geral, como podemos provar que uma
proposição é falsa?
Contra-exemplo
• Por exemplo, como podemos provar que B é
falsa?
B: Para todo inteiro n≥2,n²≥2ⁿ.
• Provando que NÃO B é verdadeira.
NÃO B: Existe um inteiro n≥2, n²<2ⁿ.
• Podemos utilizar aqui o método por
construção, pois apareceu “existe” em NÃO B.
Contra-exemplo
NÃO B: Existe um inteiro n≥2, n²<2ⁿ.
• Neste caso, podemos construir n=5, que
atende aos nossos propósitos pois n=5≥2 e
n²=25<32=2ⁿ.
Contra-exemplo
• Em resumo, quando a sentença B contém a
palavra-chave “para todo”:
B: Para todo objeto com certa propriedade, algo
acontece,
• a proposição NÃO B conterá a palavra-chave
“existe”:
NÃO B: Existe um objeto com a certa
propriedade tal que o algo não acontece.
Contra-exemplo
• E, para mostrar que NÃO B é verdadeira,
podemos usar o método por construção e
construir um objeto com a certa propriedade
e para o qual o algo não acontece. Esse objeto
para o qual B não é verdadeira é referido com
um contra-exemplo para a sentença B.
Contra-exemplo
• Uma outra situação de produzir um contraexemplo surge quando tentamos provar que a
sentença da forma “A implica B” é falsa.
• Vamos para um exemplo, mas antes disso:
• Dizemos que um inteiro m divide um inteiro n,
escrevemos m|n se, e somente se, existe um
inteiro k tal que n=km.
Contra-exemplo
• Agora consideramos o seguinte exemplo:
S: Se a,b,e c são inteiros tais que a|(bc), então
a|b e a|c.
• Depois de inúmeras tentativas mal sucedidas
em provar que S é verdadeira, você começa a
suspeitar que S é falsa.
• Uma sentença da forma “A implica B” é falsa
quando A é verdadeira e B é falsa.
Contra-exemplo
A
B
A implica B
V
V
V
V
F
F
F
V
V
F
F
V
• ALlL
• Se A, então B.
Contra-exemplo
• Lembramos que não estamos fazendo
distinção entre “Se A, então B” e “A implica
B”.
• Pela tabela-verdade vimos que a sentença da
forma “A implica B” é falsa quando A é
verdadeira e B é falsa.
Contra-exemplo
• Portanto, para provar que S é falsa precisamos
mostrar que:
A: a,b e c são inteiros tais que a|(bc) e
NÃO B: NÃO [a|b e a|c]; que é ou a não divide b
ou a não divide c.
Contra-exemplo
• Em outras palavras, para mostrar que S é falsa,
precisamos produzir inteiros a,b e c tais que
a|(bc) e ou a não divide b ou a não divide c.
• Por exemplo, a=2, b=4 e c=5 satisfazem
a|(bc), pois 2|20 e a=2 não divide c=5.
• Portanto, a=2, b=4 e c=5 formam um contraexemplo para a sentença S.
Método por Contradição
• Voltemos a falar de técnicas de demonstração.
• Com as técnicas que vimos até agora você
pode se incapaz de completar uma prova por
uma razão ou outra.
• Então, vamos apresentar aqui mais uma
técnica chamada método por contradição.
• Este método é usado quando a conclusão de
uma proposição contém uma apropriada
palavra-chave.
Método por Contradição
• Por que precisamos de um outra técnica?
• Veremos no seguinte exemplo:
Proposição1: Se n é um inteiro e n² é par, então
n é par.
• Análise da tentativa de provar:
O método regressivo fornece a seguinte
pergunta-chave: “Como posso provar que um
inteiro (no caso, n) é par?”
Método por Contradição
• Uma resposta é mostrando que:
B1: Existe um inteiro k tal que n=2k.
• O aparecimento do quantificador “existe” no
processo regressivo sugere-nos que utilizemos
o método por construção.
• Trabalhando progressivamente da hipótese
que n² é par, podemos afirmar que:
A1: Existe um inteiro, digamos m, tal que n²=2m.
Método por Contradição
• O objetivo é produzir um inteiro k tal que
n=2k, então é natural extrairmos a raiz
quadrada (positiva) de ambos os lados de A1 e
obtemos
A2: n = 2m .
• Mas, como podemos reescrever 2m de
forma que pareça com 2k?
• Aqui o método progressivo-regressivo parece
falhar.
Método por Contradição
• Felizmente, existem outras técnicas que você
pode usar antes de desistir.
• Hoje falaremos do método por contradição.
• A idéia da prova por contradição é assumir
que A é verdadeira e B é falsa e ver porque
isso não pode acontecer.
• Você deve usar as informações para chegar a
contradizer algo que você sabe absolutamente
que é verdadeira.
Método por Contradição
• Agora, você deve estar se perguntado:
“Qual contradição deveria chegar? ”
• Está é uma pergunta complicada de responder
pois não há uma regra geral. Cada problema
irá gerar a sua própria contradição.
• Então, você precisa de criatividade, insight,
persistência e as vezes sorte para produzir
uma contradição.
Método por Contradição
• No método progressivo-regressivo você assume
que somente A é verdadeira, enquanto que no
método por contradição você assume que ambos
A e NÃO B são verdadeiro. Então, você tem duas
proposições para trabalhar progressivamente no
método por contradição ao invés de uma.
• Por outro lado, você não sabe exatamente a qual
contradição chegar e portanto não pode
trabalhar regressivamente.
Método por Contradição
• Quando devo usar o método por contradição?
• Utilize o método de contradição quando NÃO
B fornecer uma informação útil
• ou quando a sentença B contiver a palavrachave “não”. Isto porque o NÃO B irá eliminar
o não.
• Vamos para um exemplo.
Método por Contradição
Proposição2: Se r é um número real tal que
r²=2, então r é irracional.
Análise da prova: Podemos reescrever a
conclusão da proposição como “r não é
racional”. Dessa forma aparece o a palavrachave “não”e agora sugere que utilizemos o
método por contradição. Então assumimos
que A e NÃO B são ambos verdadeiras.
Método por Contradição
A: r²=2 e
A1 (NÃO B): r é um número racional.
• Devemos chegar em alguma contradição
usando estas informações.
• Usando a definição de número racional temos
A2: Existem inteiros p e q com q≠0 tal que r=p/q.
• Ainda não sabemos onde a contradição irá
surgir.
Método por Contradição
• Um observação crucial irá nos ajudar.
Podemos assumir que
A3: p e q não possuem divisor comum (isto é,
não existe um inteiro que divida ambos p e q).
• Agora podemos chegar a uma contradição
mostrando que 2 é um divisor comum de p e
q.
Método por Contradição
• Trabalhando progressivamente, elevando ao
quadrado ambos os lados de A2, segue que
A4: r²=p²/q².
• Usando A sabemos que r²=2, então
A5: 2=p²/q².
• O resto da prova é basicamente reescrever A5
até chegar a contradição de que ambos p e q
são inteiros pares.
Método por Contradição
Proposição
Razão
A6: 2q²=p²
Multiplicando ambos os lados de A5 por q²
A7: p² é par
De A6 porque p² é 2 vezes um inteiro (q²)
A8: p é par
Proposição 1 (dessa aula)
A9: p =2k, para algum inteiro k
Definição de inteiro par
A10: 2q²=p²=(2k)²=4k²
Substituindo A9 em A6
A11: q²=2k²
Divide ambos os lados de A10 por 2
A12: q² é par
De A11.
A13: q é par
Proposição 1 (dessa aula)
Então, ambos p e q são pares (A8 e A13), e isto
contradiz A3, assim a prova está completa.
Método por Contradição
• Prova da Proposição 2: Assumimos, por
contradição, que r é um número racional da
forma p/q (onde p e q são inteiros com q≠0) e
r²=2. Além disso, podemos assumir que p e q
não possuem divisor comum, pois se
possuem, este número pode ser cancelado de
ambos numerador p e numerador q. Sabendose que r²=2 e r=p/q, segue que 2=p²/q², ou
equivalentemente 2q²=p².
Método por Contradição
Note que p² é par e portanto p é par. Assim,
existe um inteiro k tal que p =2k. Substituindo
esse valor de p obtemos 2q²=p²=(2k)²=4k², ou
equivalentemente q²=2k². Disto segue que q²,
e portanto q, são pares. Portanto, mostramos
que ambos p e q são pares e têm divisor
comum 2. Isto contradiz a nossa afirmação de
que p e q não possuem divisor comum.