29/10/2013
2
Proposição
• Sentença declarativa exclusivamente verdadeira ou falsa
• Alguns mamíferos pôe ovos
• Alguns mamíferos têm pena
• A aceleração de um corpo rígido é proporcional à força aplicada
• A soma dos ângulos de um triângulo é igual a 180 graus
• Para todo inteiro não negativo 𝑛, 𝑛2 + 𝑛 + 41 é primo
• Para todo inteiro 𝑛, se 𝑛 > 2 então não existem inteiros positivos
𝑎, 𝑏, 𝑐 tais que 𝑎𝑛 + 𝑏 𝑛 = 𝑐 𝑛
• Para todo inteiro par 𝑛 > 2, existem dois primos 𝑎 e 𝑏 tais que
𝑎 +𝑏 = 𝑛
PROVAS MATEMÁTICAS
Matemática Discreta
Prof. João Paulo Lima
Universidade Federal Rural de Pernambuco
Departamento de Estatística e Informática
Copyright © 2006 by The McGraw-Hill Companies, Inc. All rights reserved.
3
4
Axioma
Conjectura
• Postulado
• Proposição que não foi
• Proposição assumida como verdadeira sem prova
• 2ª lei de Newton: a aceleração de um corpo rígido é proporcional à
força aplicada
• Axioma de Euclides: a soma dos ângulos de um triângulo é igual a
180 graus
provada ou refutada
• Conjectura de Goldbach:
para todo inteiro par 𝑛 > 2,
existem dois primos 𝑎 e 𝑏
tais que 𝑎 + 𝑏 = 𝑛
5
6
Teorema
Lema e Corolário
• Proposição garantida por prova
• Para todo inteiro 𝑛, se 𝑛2 é par então 𝑛 é par
• Menor importância que teorema
2 é irracional
• Teorema de Pitágoras: em qualquer triângulo retângulo, o
quadrado do comprimento da hipotenusa é igual à soma dos
quadrados dos comprimentos dos catetos (𝑎2 + 𝑏 2 = 𝑐 2 )
• Último teorema de Fermat: para todo inteiro 𝑛, se 𝑛 > 2 então não
existem inteiros positivos 𝑎, 𝑏, 𝑐 tais que 𝑎𝑛 + 𝑏 𝑛 = 𝑐 𝑛
•
• Lema
• Pré-teorema
• Proposição provada usada como trampolim para provar teorema
• Corolário
• Pós-teorema
• Proposição que decorre imediatamente de um teorema
1
29/10/2013
7
8
Mundo
Modelos de uma proposição
• Toda proposição de interesse é verdadeira ou falsa em
• 𝑀(𝑎): conjunto dos mundos em que uma proposição 𝑎 é
relação a um mundo
verdadeira
• 2ª lei de Newton: verdadeira no mundo macroscópico (mecânica
clássica), falsa no mundo microscópico (mecânica quântica)
• Axioma de Euclides: verdadeiro apenas na geometria planar
9
10
Consequência Lógica
Prova
• 𝑏 é consequência lógica de 𝑎 se 𝑏 é verdadeira em todos
• Meio de mostrar que um teorema é consequência lógica
os possíveis mundos em que 𝑎 é verdadeira
• 𝑎 ⊨ 𝑏 se e somente se 𝑀(𝑎) ⊆ 𝑀(𝑏)
de um conjunto de axiomas
• Provas dos teoremas da mecânica clássica
• Provas dos teoremas da geometria Euclideana
𝑎⊭𝑏
𝑎′ ⊨ 𝑏
𝑎⊨𝑏
11
12
Prova por Casos
Prova por Casos
• Testar todos os possíveis casos
• Dado:
• se Dewey não for eleito, então vou comer meu chapéu
• Dewey não foi eleito
• Dado: rosas são vermelhas e violetas são azuis
• Prove: rosas são vermelhas
• Prove: vou comer meu chapéu
Rosas são vermelhas
Violetas são azuis
Rosas são vermelhas e
violetas são azuis
F
F
F
Dewey não foi eleito
Vou comer meu chapéu
Se Dewey não for
eleito, então vou comer
meu chapéu
F
V
F
F
F
V
V
F
F
F
V
V
V
V
V
V
F
F
V
V
V
2
29/10/2013
13
Prova por Casos
• Ex: prove que 𝑛 + 1
•
•
•
•
com 𝑛
𝑛 = 1,
𝑛 = 2,
𝑛 = 3,
𝑛 = 4,
≤4
1+1
2+1
3+1
4+1
3
3
3
3
3
Prova Direta
𝑛
≥ 3 se 𝑛 é um inteiro positivo
≥ 31 , 23
≥ 32 , 33
≥ 33 , 43
≥ 34 , 53
14
• Prova por aplicação de regras de inferência
• Regra de inferência
• Função que recebe hipóteses (premissas), as analisa e retorna
conclusões
≥ 31 , 8 ≥ 3
≥ 32 , 27 ≥ 9
≥ 33 , 64 ≥ 27
≥ 34 , 125 ≥ 81
• Eliminação da conjunção:
• Modus ponens:
𝑝 ∧𝑞
𝑝
𝑝, 𝑝 → 𝑞
𝑞
15
Prova Direta
16
Prova Direta
• Ex: dê uma prova direta do teorema “se 𝑛 é um inteiro
• Regras de inferência podem ser encadeadas
ímpar, então 𝑛2 é ímpar”
• Premissas:
𝑎∧𝑏
𝑏, 𝑏 → 𝑐
𝑐
• 𝑛 é um inteiro ímpar
• Se 𝑛 é par, então existe um inteiro 𝑘 tal que 𝑛 = 2𝑘
• Se 𝑛 é ímpar, então existe um inteiro 𝑘 tal que 𝑛 = 2𝑘 + 1
• Como 𝑛 é ímpar, então 𝑛 = 2𝑘 + 1
• 𝑛2 = 2𝑘 + 1 2
• 𝑛2 = 4𝑘 2 + 4𝑘 + 1
• 𝑛2 = 2(2𝑘 2 + 2𝑘) + 1
• Logo, 𝑛2 é ímpar
17
18
Prova por Contrapositiva
Não-Prova
• Teorema: para todo inteiro 𝑛, se 𝑛2 é par então 𝑛 é par
• Prova de que 1 = −1
• Prova: provar a contrapositiva
•1 =
• Se 𝑛 é ímpar então 𝑛2 é ímpar
• 1. Se 𝑛 é ímpar, então 𝑛 = 2𝑎 + 1 para algum inteiro 𝑎
(por definição)
• 2. 𝑛2 = 2𝑎 + 1 2 = 4𝑎 2 + 4𝑎 + 1 = 2 2𝑎 2 + 2𝑎 + 1
2
1 = −1 −1 = −1 −1 = −1 = −1
• Onde está o erro?
•
•
−1 −1 ≠ −1 −1
𝑥𝑦 = 𝑥 𝑦 nem sempre é verdade
• 3. Como 𝑎 é inteiro, 2𝑎 2 + 2𝑎 é inteiro
• 4. De acordo com (1), 𝑛2 é ímpar
3
29/10/2013
19
20
Não-Prova
Prova de Existência
• Outros erros clássicos:
• 𝑎𝑥 = 𝑏𝑥, logo 𝑎 = 𝑏
• Teorema: existem números irracionais 𝑥 e 𝑦 tais que 𝑥 𝑦 é
racional
• Não vale para 𝑥 = 0
• Prova: considere 𝑥 =
• 𝑎𝑥 < 𝑏𝑥, logo 𝑎 < 𝑏
• Não vale para 𝑥 ≤ 0
•
2
2
2e𝑦= 2
é racional ou irracional?
21
Prova de Existência
• Se
• Se
• 𝑥𝑦
2
2
=
2
2
Prova por Contradição
• Prova por redução ao absurdo
for racional: então o teorema está provado
for irracional: considere 𝑥 = 2
2
2
2
= 2
2 2
22
2
• Negação do teorema leva a uma contradição
e𝑦= 2
• Teorema:
2 é irracional
• Prova: assumir que
2
= 2 =2
2 é racional e chegar a um absurdo
• Logo, o teorema está provado
23
Prova por Contradição
24
Prova por Contradição
• Se
• Mas se 𝑎 é par e 𝑏 é par, então 𝑎 e 𝑏 não são primos
•
• Logo,
•
•
•
•
•
•
•
2 é racional, então 2 = 𝑎 𝑏, 𝑎 e 𝑏 inteiros primos
entre si
2 = 𝑎2 𝑏 2
𝑎2 = 2𝑏 2
𝑎2 é par, logo 𝑎 é par
Se 𝑎 é par, então 𝑎 = 2𝑐
𝑎2 = 4𝑐2
2𝑏 2 = 4𝑐2
𝑏 2 = 2𝑐2
𝑏 2 é par, logo 𝑏 é par
entre si (contradição)
2 é irracional
4
29/10/2013
25
26
Prova por Contraexemplo
Prova por Indução
• Ex: prove que a seguinte proposição é falsa: ∀𝑛, 𝑛 ≥ 0,
• Será vista em aulas futuras
𝑛2 + 𝑛 + 41 é primo
• 𝑛 = 40 → 𝑛2 + 𝑛 + 41 = 402 + 40 + 41 = 1681 = 412
5