Exercicios Resolvidos

Matemática Discreta

Lista de exercícios resolvidos

Parte I: Técnicas de prova e definições indutivas

1) Vamos provar a conjectura “Para um número ser primo não é suficiente que seja ímpar”. Siga os seguintes passos para prová-la:
(a) Desconsidere o não do enunciado e coloque o restante na forma “se P então Q”
(b) Para provar a frase original “não (se P então Q)” basta refutar “se P então Q”
(a) Como o enunciado fala em suficiência o P será a segunda parte “o número é impar”. Logo, o enunciado sem a negação será “se um número é ímpar então ele é primo”
(b) para refutar (a) basta encontrar um contra-exemplo. Ora, 9 é ímpar mas não é primo. Logo a conjectura original está provada.

2)
Prove que para um inteiro n, n3+5 é ímpar se somente se n é par:
a) por contraposição (a parte ‘se’)
Temos que provar que Se n é par então n3+5 é ímpar por contraposição, ou seja:
. Temos que provar que Se n3+5 é par então n é ímpar
Se n3+5 é par então n3+5 = 2k logo n3 +2.2 + 1 = 2k, logo n3 tem que ser ímpar pois se fosse par daria 2m+2.2 + 1= 2(m+2) + 1 o que é ímpar.
Mas, se n3 é ímpar, n não pode ser par pois nesse caso n3=2r.2r.2r = 2(4r2) que é par.
Logo n tem que ser ímpar. c.q.d.

Temos que provar que Se n não é par então n3+5 não é ímpar.
Como, por hipótese n é ímpar, será da forma n= 2k+1 para algum k. Então n3 +5= (2k+1)3 +5= (4k2 + 4k+1)(2k+1)+5 = 8k3+8k+2k+4k2+4k+1+5 =
8k3+4k2+14k+6= 2 (4k3+2k714k+3), logo r= 4k3+2k714k+3 é um inteiro e temos que n3 +5= 2r, portanto é par. C.Q.D.
b) por absurdo ( a parte ‘somente se’)
Temos que provar que Se n3+5 é ímpar então n é par por absurdo.
Suponhamos que n3+5 é ímpar mas n também é ímpar.
Mas, se n é ímpar, é da forma 2k+1, nesse caso teríamos n3 +5 = (2k+1)3 = (2k+1) (2k+1) (2k+1) + 5 = (4k2+ 4k+3)(2k+1) + 5 =
8k3 + 4k2 + 8k2 + 4k + 6k + 3 + 5 = 8k3 + 12k2 + 8k + 8 = 2(4k3 + 6k2 + 4k + 4)
Que é para, em contradição de que n3+5 é ímpar. c.q.d.

3) Prove que “se x é