Aula3 demonstracoes

Prévia do material em texto

Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Bibliografia
Fundamentos de Matemática para Computação
Demonstrações
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Bibliografia
Divisibilidade
Definição 1
Sejam a e b inteiros, com a 6= 0. Dizemos que a divide b se
existe um inteiro c tal que b = ac. Dizemos também que:
b é divisível por a;
a é um fator de b;
a é um divisor de b;
b é múltiplo de a.
A notação correspondente é a | b, quando a divide b, e a - b, em
caso contrário.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Bibliografia
Divisibilidade
Observações
1 Todo inteiro x divide 0 (zero).
2 d | b↔ (−d) | b.
3 Todo inteiro a é divisível por 1 e por a.
Exemplo 1
1 3 | 9.
2 4 | 12.
3 6 - 16.
4 3 | −15.
5 5 | 0
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Bibliografia
Definições
Definição 2
Um inteiro a é chamado par desde que haja um inteiro x tal
que a = 2x, ou seja 2 | a.
Um inteiro a é chamado ímpar desde que haja um inteiro x tal
que a = 2x+ 1.
Observação
Um inteiro é sempre par ou ímpar e nenhum inteiro é par e
ímpar ao mesmo tempo.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Bibliografia
Mais definições
Definição 3
1 Um número p é primo se p > 1 e se os únicos divisores
positivos de p são 1 e p.
2 Um número positivo a é chamado de composto se existe
um inteiro b tal que 1 < b < a e b | a.
3 O número 1 não é primo nem composto!
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Bibliografia
Terminologia
Definição 4
1 Um teorema é uma afirmação declarativa sobre
matemática, para a qual existe uma prova ou
demonstração.
2 Uma proposição é um teorema de importância secundária.
3 Um lema é um teorema cujo objetivo principal é ajudar
provar outro teorema mais importante.
4 Um corolário é um teorema que pode ser estabelecido
diretamente de outro teorema que já foi demonstrado.
5 Uma conjectura é uma sentença que inicialmente é
proposta como verdadeira.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Bibliografia
Exemplo de Conjectura
Conjectura de Goldbach
Todo inteiro par maior do que 2 é a soma de dois primos.
Alguns exemplos
4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 3 + 7 · · ·
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Bibliografia
Condicional
Reformulação - Se A, então B
A soma de dois números inteiros pares é par.
Reformulação: Se x e y são inteiros pares, então x+ y também
é par.
Exercício 1
Reescreva as sentenças na forma “Se A, então B’:
1 O produto de um inteiro ímpar e um inteiro par é par.
2 O quadrado de um inteiro ímpar é ímpar.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Prova ou demonstração
Definição 5
Uma prova ou demonstração é uma argumentação que
mostra, de maneira indiscutível, que uma afirmação é
verdadeira.
Técnicas mais comuns de demonstração:
Demonstração direta;
Demonstração por contraposição;
Demonstração por contradição ou absurdo.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Prova ou demonstração
Sentenças usadas na demonstração
axiomas: sentenças que assumimos ser verdadeiras;
as premissas do teorema;
e teoremas previamente provados.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstração por vacuidade
Afirmação verdadeira por vacuidade
É utilizada para estabelecer casos especiais de teoremas.
Sabemos que quando p é falsa a afirmação é verdadeira.
Exemplo 2
Seja a um inteiro. Se a é um quadrado (i.e. existe b ∈ Z t.q.
a = b2) e a é primo, então a é negativo.
A afirmação é verdadeira ou falsa?
Neste caso, como a hipótese é falsa, a afirmação é
verdadeira!
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstração por trivialização
Afirmação verdadeira por trivialização
É utilizada para estabelecer casos especiais de teoremas.
É utilizada em indução matemática.
Exemplo 3
Se a e b são inteiros positivos com a ≥ b, então an ≥ bn, para
todos os inteiros. Mostre que P (0) é verdadeira.
Solução
A proposição P (0) é “Se a ≥ b, então a0 ≥ b0”. Como
a0 = b0 = 1, a conclusão da condicional “Se a ≥ b, então
a0 ≥ b0” é verdadeira.
Portanto, a sentença condicional, que é P (0), é verdadeira.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstrações do tipo p→ q
Definição
Uma demonstração direta de uma sentença condidional p→ q é
construída quando o primeiro passo é assumir que p é
verdadeira; os passos subsequentes são construídos, com o
passo final mostrando que q deve ser também verdadeira.
Demonstração direta (p→ q)
Uma sequência de implicações lógicas que começa em p e
termina em q.
Uma sequência óbvia de passos que levam da hipótese à
conclusão.
Algumas vezes requer insights particulares e podem ser
bastante astuciosas.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstrações do tipo p→ q
Esquema de demonstração do Exemplo ??
Prove que a soma de dois inteiros pares é par.
Reformulação: Se x e y são inteiros pares, então x+ y é um
inteiro par.
Demonstração
Sejam x e y inteiros pares.
. . .
Portanto, x+ y é um inteiro par.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstrações do tipo p→ q
Demonstre que
Se x e y são inteiros pares, então x+ y é um inteiro par.
Demonstração:
Sejam x e y inteiros pares. Então, por definição, existem
inteiros k e l tal que x = 2k e y = 2l. Somando x com y temos:
x+ y = 2k + 2l = 2(k + l).
Como k + l é um número inteiro, concluímos que x+ y é um
inteiro par.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstrações DiretasDemonstre que
Se n é um inteiro ímpar, então n2 é ímpar.
Demonstração:
Suponha a hipótese verdadeira, ou seja, suponha que n é ímpar.
Então, temos que existe um inteiro k tal que n = 2k + 1.
Queremos mostrar que n2 é ímpar. Observe que,
n = 2k + 1⇒ n2 = (2k + 1)2. Então temos que
n2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1. Como 2k2 + 2k é um
número inteiro, concluímos que n2 é ímpar.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstrações Diretas
Demonstre que
Se um inteiro é divisível por 6, então duas vezes esse inteiro é
divisível por 4.
Reformulação
Seja a um inteiro. Se 6|a então 4|2a.
Demonstração:
Suponha a hipótese verdadeira, ou seja, suponha que 6|a.
Então, temos que existe um inteiro k tal que 6k = a. Queremos
mostrar que 4|2a. Observe que,
2a = 2(6k) = 12k = 4(3k).
Como 3k é um inteiro, temos que 2a é múltiplo de 4. Portanto,
4|2a.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstrações do tipo p→ q
Demonstração por contraposição (¬q → ¬p)
Prova direta da contrapositiva de sua afirmação.
Exemplo 4
Sejam a, b inteiros. Se ab é ímpar, então a e b são ímpares.
Demonstração:
Suponha que a ou b é par.
. . .
Logo, ab é par. Portanto, podemos concluir que se ab é ímpar,
então a e b são ímpares.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstrações do tipo p→ q
Demonstre que:
Sejam a, b inteiros. Se ab é ímpar, então a e b são ímpares.
Demonstração:
Suponha que a ou b é par. Primeiramente, assuma que a é par.
Então, existe um inteiro k tal que a = 2k.
Caso 1: b é par. Neste caso, existe um inteiro l tal que b = 2l.
Multiplicando a por b temos que:
ab = (2k)(2l) = 4(4kl) = 2(2kl).
Como 2kl é um inteiro, concluímos que ab é par.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstrações do tipo p→ q
Demonstre que:
Sejam a, b inteiros. Se ab é ímpar, então a e b são ímpares.
Demonstração (cont):
Caso 2: b é ímpar. Neste caso, existe um inteiro m tal que
b = 2m+ 1. Multiplicando a por b temos que:
ab = (2k)(2m+ 1) = 4km+ 2k = 2(2km+ k).
Como 2km+ k é um inteiro, concluímos que ab é par.
Logo, nos dois casos ab é par.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstrações do tipo p→ q
Demonstre que:
Sejam a, b inteiros. Se ab é ímpar, então a e b são ímpares.
Demonstração (cont):
Agora, suponha que a é ímpar e b é par. Então, existem inteiros
x e y tal que a = 2x+ 1 e b = 2y. Novamente, multiplicando a
por b temos que:
ab = (2x+ 1)2y = 4xy + 2y = 2(2xy + y).
Como 2xy + y é um inteiro, concluímos que ab é par.
Portanto, podemos concluir que se ab é ímpar, então a e b são
ímpares.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstrações do tipo p→ q
Demonstre por contraposição que
Se n é um inteiro e 3n+ 2 é ímpar, então n é ímpar.
Demonstração:
Assuma que n é par. Então n = 2k, k ∈ Z. Substituindo 2k em
n temos que,
3n+ 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1)
. Como 3k + 1 é um inteiro, temos que 3n+ 2 é potência de 2.
Logo 3n+ 2 não é ímpar.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstrações do tipo p→ q
Demonstração por contradição ou absurdo (¬(p ∧ ¬q))
Provar que “Se p, então q”:
Supomos as condições em p.
Por contradição, supomos não q.
Argumentamos até chegar a uma contradição.
Exemplo 5
O produto de inteiros ímpares não é par.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstrações do tipo p→ q
Demonstre por contraposição que
O produto de inteiros ímpares não é par.
Reformulação
Se a e b são inteiros ímpares então ab é ímpar.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstrações do tipo p→ q
Reformulação
Se a e b são inteiros ímpares então ab é ímpar.
Demonstração:
Assuma que a e b são ímpares. Então, existem inteiros k e l tal
que a = 2k + 1 e b = 2l + 1. Por contradição, assuma que ab é
par. Então ab = 2m, com m ∈ Z. Substituindo a e b em
ab = 2m temos
ab = (2k + 1)(2l + 1) = 2m⇒
4kl + 2k + 2l + 1 = 2m⇒
4kl + 2k + 2l − 2m = −1⇒
2(2kl + k + l −m) = −1⇒
2kl + k + l −m = −1/2.
Note que 2kl + k + l −m é um inteiro (pois k, l e m o são)
mas −1/2 não é inteiro. Uma contradição. Logo, ab é ímpar.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstrações do tipo p→ q
Demonstre por contradição que:
Se x é um inteiro, então x não pode ser simultaneamente par e
ímpar.
Demonstração
Seja x um inteiro. Suponha, por contradição, que x seja ao
mesmo tempo par e ímpar.
Como x é par, existe um inteiro k tal que x = 2k.
Como x também é ímpar, existe um inteiro w tal que
x = 2w + 1.
Observe que x = 2k = 2w + 1. Dividindo por 2 temos que
k = w+1/2, o que implica que (k−w) = 1/2. Note que k−w
é um inteiro (pois k e w o são) mas 1/2 não é inteiro. Uma
contradição. Portanto, x não é ao mesmo tempo par e ímpar.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstrações do tipo p→ q
Demonstre por contradição que:
Se 3n+ 2 é um inteiro ímpar, então n é ímpar.
Demonstração
Assuma que 3n+ 2 é ímpar e que n não é ímpar. Como n não
é ímpar, então é par e existe um inteiro k tal que n = 2k.
Observe que
3n+ 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1).
Logo 3n+ 2 é potência de 2 e é par. Uma contradição (no fato
de supor que n não é ímpar). Portanto, se 3n+2 é ímpar então
n é ímpar.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Se e somente se
A se e somente se B
Para provar uma afirmação da forma “A se e somente se B”:
(⇒) Prove que “Se A, então B”.
(⇐) Prove que “Se B, entãoA”.
Exemplo 6
Seja n é um inteiro positivo. Então n é par se e somente se,
7n+ 4 for par. Demonstração.:
Seja x um inteiro.
(⇒) Suponha que n é par. . . . Portanto, 7n+ 4 é par.
(⇐) Suponha que 7n+ 4 é par. . . . Portanto, n é par.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Se e somente se
Demonstre que
Seja n é um inteiro positivo. Então n é par se e somente se,
7n+ 4 for par.
Demonstração:
(⇒) Assuma que n é par. Então existe um inteiro k tal que
n = 2k. Substituindo 2k em n temos que,
7n+ 4 = 7(2k) + 4 = 14k + 4 = 2(7k + 2). Como 7k + 2
é um número inteiro e 7n+ 4 é potência de 2, logo 7n+ 4
é par.
(⇐) Vamos provar por contraposição. Suponha que n é ímpar.
Então existe um inteiro l tal que n = 2l + 1. Substituindo
2l + 1 em n temos que, 7(2l + 1) + 4 = 14l + 7 + 4 =
14l+ 11 = 14l+ 10+ 1 = (7l+ 5) + 1. Como 7l+ 5 é um
número inteiro, logo 7n+ 4 é ímpar.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstrações
Prove ou Refute a afirmação
A soma de quaisquer três inteiros consecutivos é par.
Contraexemplo
Tome os números consecutivos: 2, 3, 4. Veja que a soma
2 + 3 + 4 = 9 não é um inteiro par.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstrações
Prove ou Refute a afirmação
O produto de quaisquer três inteiros consecutivos é par.
Prova
Tome três inteiros consecutivos. Se são consecutivos ou dois
deles são pares ou o contrário, e temos dois casos:
Caso1: temos um par mutiplicado por um ímpar e
multiplicado por outro par. Então seja x um inteiro par.
Logo existe um inteiro k tal que x = 2k. Temos o seguinte
produto:
x∗(x+1)∗(x+2) = 2k+(2k+1)∗(2k+2) = · · · = 2(4k3+6k2+2k).
Como (4k3 + 6k2 + 2k) é um inteiro, temos que
x ∗ (x+ 1) ∗ (x+ 2) é par.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Demonstrações
Prove ou Refute a afirmação
O produto de quaisquer três inteiros consecutivos é par.
Prova
Caso 2: temos um ímpar mutiplicado por um par e
multiplicado por outro ímpar. Então seja x um inteiro
ímpar. Logo existe um inteiro m tal que x = 2m+ 1.
Temos o seguinte produto:
(2m+1)∗(2m+2)∗(2m+3) = · · · = 2(4m3+12m2+11m+3).
Como (4m3 + 12m2 + 11m+ 3) é um inteiro, temos que
x ∗ (x+ 1) ∗ (x+ 2) é par.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Contraexemplo
Definição 6
Um contraexemplo é uma maneira de refutar uma afirmação
do tipo “Se A, então B”. É uma instância em que A é
verdadeira, mas B é falsa.
Exemplo 7
Seja a afirmação: “Se x é primo, então x é ímpar”.
Contraexemplo: 2 é um inteiro que é primo, mas não é ímpar.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Contraexemplo
Afirmação
Sejam a e b inteiros. Se a|b e b|a, então a = b.
contraexemplo
Precisamos achar inteiros a e b, tais que, de um lado,
verifiquem a|b e b|a, mas, do outro, não verifiquem a = b.
Tomemos a = 5 e b = −5. Observe que 5| − 5 pois
5(−1) = −5, e −5|5 pois −5(−1) = 5, mas 5 6= −5.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Vacuidade
Trivialização
Direta
Contraposição
Contradição
Se e somente
se
Contraexemplo
Bibliografia
Contraexemplo
Refute a afirmação
Todo inteiro positivo é a soma dos quadrados de dois inteiros.
Contraexemplo
Tome o número 3. Os quadrados que não excedem 3 é 02 = 0 e
12 = 1. Não há como obter 3 da soma desses dois quadrados,
com apenas dois termos. Portanto, mostramos que a afirmação
é falsa.
Fundamentos
de
Matemática
para
Computação
Divisibilidade
Par e ímpar
Primo
Terminologia
Reformulação
Demonstração
Bibliografia
Referências Bibliográficas
Referências
Rosen, K. H.,
Matemática Discreta e suas aplicações.
6a. edição, Editora McGraw Hill, 2009.
Gersting, J. L.
Fundamentos Matemáticos para a Ciência da Computação.
5a. edição, Editora LTC, 2004.
Scheinerman, Edward R.
Matemática Discreta, Uma introdução.
Thomson Pioneira, 2003.
	Divisibilidade
	Par e ímpar
	Primo
	Terminologia
	Reformulação
	Demonstração
	Vacuidade
	Trivialização
	Direta
	Contraposição
	Contradição
	Se e somente se
	Contraexemplo
	Bibliografia