A maior rede de estudos do Brasil

Grátis
109 pág.
Lógica e Demonstraçoes

Pré-visualização | Página 47 de 50

convencida	 de	 que	 uma	
demonstração	relativamente	simples	poderia	ser	encontrada.	(Demonstrações	para	casos	especiais	
foram	encontradas,	como	a	demonstração	do	caso	n =	3	por	Euler,	e	a	demonstração	do	caso	n =	4,	
do	próprio	Fermat.)	Através	dos	anos,	muitos	matemáticos	de	renome	pensaram	que	tinham	de-
monstrado	esse	teorema.	No	século	XIX,	uma	dessas	tentativas	falhas	levou	ao	desenvolvimento	de	
parte	da	teoria	dos	números,	chamada	de	teoria	algébrica	dos	números.	Uma	demonstração	correta	
necessitou de centenas de páginas de matemática avançada e não tinha sido encontrada até a década 
de	1990,	quando	Andrew	Wiles	usou	idéias	desenvolvidas	recentemente	de	uma	área	sofisticada	da	
teoria	dos	números,	chamada	de	teoria	das	curvas	elípticas,	para	demonstrar	o	último	teorema	de	
Fermat.	A	pesquisa	de	Wiles	para	encontrar	a	demonstração	do	último	teorema	de	Fermat,	usando	
esta	matemática	poderosa,	foi	descrita	na	série	Nova da televisão pública norte-americana e durou 
10	anos!	(O	leitor	interessado	pode	consultar	[Ro05]	para	mais	informações	sobre	o	Último	Teore-
ma	de	Fermat	e	para	referências	adicionais	sobre	esse	problema	e	sua	resolução.)	
Vamos	agora	mostrar	um	problema	aberto	simples	de	descrever,	mas	que	parece	difícil	de	
resolver.
EXEMPLO 23 A Conjectura 3x +1 Seja T a transformação que leva um número par x para x/2 e um número 
ímpar x para 3x +	1.	Uma	conjectura	famosa,	conhecida	como	a	conjectura 3x +1,	diz	que	para	
todos os números inteiros positivos x,	quando	aplicamos	repetidamente	a	transformação T,	va-
mos	encontrar	em	algum	ponto	o	inteiro	1.	Por	exemplo,	começando	com x =	13,	encontramos	T 
(13)	= 3 ⋅ 13 + 1 =	40,	T (40)	= 40/ 2 =	20,	T (20)	= 20/ 2 =	10,	T (10)	= 10/ 2 =	5,	T (5)	= 3 ⋅ 5 
+ 1 =	16,	T (16)	=	8,	T (8)	=	4,	T (4)	= 2 e T (2)	=	1.	A	conjectura	3x +	1	foi	verificada	para	
todos	os	números	inteiros	até	5,6	·	1013.
FIGURA 7 Colorindo os Quadrados de um Tabuleiro 
Standard com Três Cores.
Links
Links
1-101 1.7 Métodos de Demonstração e Estratégia 101
102	 	1	/	Os	Fundamentos:	Lógica	e	Demonstrações	 1-102
A	conjectura	3x + 1 tem uma história interessante e tem atraído a atenção dos matemáticos 
desde	a	década	de	1950.	A	conjectura	apareceu	muitas	vezes	e	com	muitos	nomes	diferentes,	in-
cluindo	o	problema	Collatz,	o	algoritmo	de	Hasse,	o	problema	de	Ulam,	o	problema	de	Siracusa	e	
o	problema	de	Kakutani.	Muitos	matemáticos	desviaram-se	de	seus	trabalhos	para	gastar	tempo	
dedicando-se inteiramente a essa conjectura. Isso levou à piada de que esse problema era parte de 
uma conspiração para diminuir o ritmo de desenvolvimento da pesquisa matemática norte-ameri-
cana.	Veja	o	artigo	de	Jeffrey	Lagarias	[La85]	para	uma	discussão	fascinante	sobre	esse	problema	
e os resultados que já foram encontrados pelos matemáticos que se dedicaram a ele. ◄
No	Capítulo	3,	vamos	descrever	questões	abertas	adicionais	sobre	números	primos.	Estudan-
tes	 já	familiarizados	com	as	noções	básicas	sobre	primos	podem	querer	explorar	a	Seção	3.4,	
onde estas questões abertas são discutidas. Vamos mencionar outras questões abertas importantes 
por todo o livro.
Métodos de Demonstrações Adicionais
Neste capítulo introduzimos os métodos básicos usados em demonstrações. Também descreve-
mos como usar esses métodos para demonstrar uma variedade de resultados. Vamos usar esses 
métodos	de	demonstração	nos	capítulos	2	e	3	para	demonstrar	resultados	sobre	conjuntos,	fun-
ções,	algoritmos	e	teoria	dos	números.	Passando	por	esses	teoremas,	vamos	demonstrar	um	fa-
moso meta-teorema que diz que existe um problema que não pode ser resolvido usando qualquer 
procedimento.	No	entanto,	existem	muitos	métodos	de	demonstração	importantes	ao	lado	desses	
que	já	cobrimos.	Vamos	introduzir	alguns	desses	métodos	mais	adiante	neste	livro.	Em	particular,	
na	Seção	4.1,	vamos	discutir	indução	matemática,	que	é	um	método	extremamente	usado	para	
demonstrar sentenças da forma ∀nP (n),	em	que	o	domínio	consiste	em	todos	os	inteiros	positi-
vos.	Na	Seção	4.3,	vamos	introduzir	 indução	estrutural,	ou	recursão,	que	pode	ser	usada	para	
demonstrar	resultados	sobre	conjuntos	recursivamente	definidos.	Vamos	usar	o	método	de	diago-
nalização	de	Cantor,	que	pode	ser	usado	para	demonstrar	resultados	sobre	o	tamanho	de	conjun-
tos	 infinitos,	 na	 Seção	 2.4.	 No	 Capítulo	 5,	 vamos	 introduzir	 a	 noção	 de	 demonstrações	
combinatórias,	que	podem	ser	usadas	para	demonstrar	resultados	usando	argumentos	de	conta-
gem.	O	leitor	pode	notar	que	no	livro	inteiro	serão	discutidas	as	atividades	vistas	nesta	seção,	
incluindo	muitos	trabalhos	excelentes	de	George	Pólya	([Po61],	[Po71],	[Po90]).	
Finalmente,	note	que	não	demos	um	procedimento	que	pode	ser	usado	para	demonstrar	qual-
quer teorema em matemática. Este é um teorema profundo da lógica matemática que diz que não 
existe esse procedimento.
Exercícios
1. Demonstre que n2 +	1	≥	2n quando n é um número inteiro 
positivo	com	1	≤	n ≤	4.
2. Demonstre que não há cubos perfeitos positivos menores 
que 1.000 que são a soma dos cubos de dois números inteiros 
positivos.
3. Demonstre que se x e y são	números	reais,	então	max(x, y)	
+	min(x, y)	= x + y. [Dica: Use uma demonstração por 
casos,	com	os	dois	casos	correspondentes	a	x ≥	y e x < y,	
respectivamente.]
4. Use uma demonstração	por	casos	para	mostrar	que	min(a, 
min(b, c))	=	min(min(a, b), c),	sempre	que	a,	b e c forem 
números reais.
5. Demonstre que a desigualdade triangular,	que	afirma	que	
se x e y	são	números	reais,	então	|x| + |y|	≥	|x + y|	(em	que	
|x| representa o valor absoluto de x,	que	é	igual	a	x se x ≥	0	
e	igual	a	−x se x < 0).
 6. Demonstre que há um número inteiro positivo que é igual 
à soma dos números inteiros positivos não excedentes a 
ele. Sua demonstração é construtiva ou não construtiva?
 7. Demonstre que há 100 números inteiros positivos conse-
cutivos que não são raízes quadradas perfeitas. Sua de-
monstração é construtiva ou não construtiva?
 8. Demonstre que um desses números: 2 ⋅ 10500 + 15 ou 
2 ⋅ 10500 + 16 não é um quadrado perfeito. Sua demonstra-
ção é construtiva ou não construtiva? 
 9.	 Demonstre	que	há	um	par	de	números	inteiros	consecutivos,	
tal que um desses números inteiros é um quadrado perfeito 
e	o	outro,	um	cubo	perfeito.
10. Mostre que o produto de dois dos números 651.000	−	82.001 
+ 3177,	791.212	−	92.399 + 22.001,	e	244.493	−	58.192 + 71.777 
não é negativo. Sua demonstração é construtiva ou não 
construtiva? [Dica: Não tente avaliar esses números!]
11. Demonstre ou contrarie que há um número racional x e 
um número irracional y, tal que xy é irracional.
12. Demonstre ou contrarie que se a e b são números 
racionais,	então	ab é também racional.
13. Mostre que cada uma destas proposições pode ser usada 
para expressar o fato de que há um único elemento x, tal 
que P (x)	seja	verdadeira.	[Note	que	podemos	escrever	
também esta proposição como ∃!x P (x).]
a) ∃x∀y (P (y)	↔	x = y)
b) ∃x P (x)	∧ ∀x∀y (P (x)	∧ P (y)	→	x = y)
c) ∃x (P (x) ∧ ∀y (P (y) → x = y))
14. Mostre que se a,	b e c são números reais e a 	0,	então	
há uma única solução para a equação ax + b = c.
15. Suponha que a e b sejam	 números	 inteiros	 ímpares,	
com a  b. Mostre que há um único número inteiro c,	
tal que |a −	c| = |b −	c|.
16. Mostre que se r é	um	número	irracional,	há	um	único	
número inteiro n, tal que a distância entre r e n é menor 
que 1/2.
17. Mostre que se n é	um	número	inteiro	 ímpar,	então	há	
um único número inteiro k, tal que n é a soma de k −	2	
e k + 3.
18. Demonstre que dado um número real x, existem números 
únicos n e e,	tal	que	x = n + e,	n é um número inteiro e 
0	≤	e < 1.
19. Demonstre que dado um número real x, existem números 
únicos n e e,	tal	que	x = n - e,	n é um número inteiro e 
0	≤	e < 1.
20. Use um raciocínio direto para mostrar que se x é um 
número	 real	 diferente	 de	 zero,

Crie agora seu perfil grátis para visualizar sem restrições.