exercícios ufmg

UFMG/ICEx/DCC DCC111 – Matemática Discreta
Lista de Exercícios 3: Soluções Métodos de Prova
Ciências Exatas & Engenharias 2o Semestre de 2014
1. Identifique o erro na prova do teorema abaixo.
Teorema: Para todos inteiros k, se k > 0 então k2 + 2k + 1 é um número composto.
Prova: Suponha que k é um número inteiro tal que k > 0. Se k2+2k+1 é composto, então k2+2k+1 = r·s, para inteiros r e s tal que 1 < r < (k2 + 2k + 1) e 1 < s < (k2 + 2k + 1). Já que k2 + 2k + 1 = r · s e ambos r e s estão necessariamente entre 1 e k2 + 2k + 1, então k2 + 2k + 1 não é primo. Assim, k2 + 2k + 1 é composto, o que devia ser mostrado.
Resposta:
A partir do ponto
Já que k2+2k+1 = r·s e ambos r e s estão necessariamente entre 1 e k2+2k+1, então k2+2k+1 não é primo. Assim, k2 + 2k + 1 é composto, o que devia ser mostrado. é usada a questão a ser provada. Nesse ponto na prova, não foi mostrado ainda que k2 +2k+1 é um número composto, o que devia ser provado.
2. Identifique o erro na prova do teorema abaixo.
Teorema: A soma de quaisquer dois inteiros pares é igual a 4k para algum inteiro k.
Prova: Suponha que m e n são dois inteiros pares quaisquer. Pela definição de par m = 2k para algum inteiro k e n = 2k para algum inteiro k. Por substituição, m + n = 2k + 2k = 4k, o que devia ser provado.
Resposta:
O erro na “prova” é que o mesmo símbolo k é usado para representar dois números diferentes. Ao supor que m e n são iguais a 2k, temos que m = n e, assim, a prova é válida apenas para o caso onde m = n. Se m 6= n, a conclusão é, em geral, falsa. Por exemplo, 6 + 4 = 10 mas 10 6= 4k para qualquer inteiro k.
3. Identifique o erro na prova do teorema abaixo.
Teorema: Seja n um número inteiro ímpar. Sabe-se que bn/2c = (n 1)/2.
Prova: Suponha que n é um número inteiro ímpar. Sabe-se que n = 2k + 1 para algum inteiro k. Conse- quentemente, 2k + 1  = (2k + 1) 1
2
2 = 2k2 = k.
Como n = 2k + 1, temos que k = (n 1)/2. Assim, por substituição temos que bn/2c = (n 1)/2.
Esta prova