Prova de Matemática Discreta

Prévia do material em texto

Prova #1 - Matema´tica Discreta (Diurno)
Prof. Eric Fernandes de Mello Arau´jo
19 de abril de 2011
1. Marcelo gostaria de saber os sala´rios de treˆs colegas de trabalho utilizando
dois fatos. Primeiro, ele sabe que se Fred na˜o tem o maior sala´rio dos
treˆs, enta˜o Janice tem. Segundo, ele sabe que se Janice na˜o recebe o
menor sala´rio, enta˜o Magali recebe mais. E´ poss´ıvel determinar os sala´rios
relativos de Fred, Janice e Magali com as informac¸o˜es de Marcelo? Se for
poss´ıvel, quem ganha mais e quem ganha menos? Explique sua resposta.
Resposta: E´ poss´ıvel. Janice na˜o pode receber o maior sala´rio, pois isso
implicaria em Magali receber o maior sala´rio. E Janice na˜o pode receber
um sala´rio intermedia´rio, pois enta˜o tanto Fred quanto Magali recebem
o maior sala´rio. Logo e´ necessa´rio que Janice receba o menor sala´rio,
concluindo, assim, que Fred e´ quem recebe o maior sala´rio.
2. Utilize predicados, quantificadores, conectivos lo´gicos e operadores ma-
tema´ticos para expressar a afirmac¸a˜o que existe um inteiro positivo que
na˜o seja a soma dos quadrados de treˆs inteiros.
Resposta: ∃x∀a∀b∀c((x > 0)x 6= a2 + b2 + c2).
3. Mostre, usando regras de infereˆncia, que “Matusale´m trabalha duro”, “Se
Matusale´m trabalha duro, enta˜o ele e´ um bom garoto”, e “Se Matusale´m
e´ um bom garoto, enta˜o ele na˜o conseguira´ um novo emprego”implicam
na conclusa˜o de que “Matusale´m na˜o conseguira´ um novo emprego”.
Resposta: Consederando as seguintes proposic¸o˜es (i)p: Matusale´m traba-
lha duro; (ii)q: Matusale´m e´ um bom garoto; (iii)r: Matusale´m conseguira´
um novo emprego:
Passo Expresso˜es Regras
H1 p Hipo´tese 1
H2 p→ q Hipo´tese 2
H3 q →∼ r Hipo´tese 3
4 p→∼ r Silogismo Hipote´tico usando H2 e H3
5 ∼ r Modus Ponens atrave´s de H1 e 4
1
4. Prove por contradic¸a˜o que se x + y ≥ 2, onde x e y sa˜o nu´meros reais,
enta˜o x ≥ 1 ou y ≥ 1.
Resposta: Faremos a prova por contradic¸a˜o. Consideremos que x < 1
e y < 1 e mantenhamos a nossa hipo´tese. Dessa forma temos uma nova
hipo´tese de que x + y ≥ 2 e x < 1 e y < 1. Tomando x < 1 e somando
1 dos dois lados da equac¸a˜o, tem-se que x + 1 < 2. Sabendo que y < 1,
pode-se dizer que x+y < x+1. Logo, tem-se que x+y < x+1 < 2, atrave´s
do qual pode-se concluir que x + y < 2. Como nossa hipo´tese afirma que
x+ y ≥ 2, temos uma contradic¸a˜o, o que prova o enunciado do problema.
5. Prove que 1 · 1! + 2 · 2! + ...+ n · n! = (n+ 1)!− 1 para qualquer n inteiro
positivo.
Resposta: Iremos provar usando Induc¸a˜o Fraca, ou o Primeiro Princ´ıpio
da Induc¸a˜o. Para isso, consideremos os treˆs passos a seguir:
(i) Passo Base: P (1) = 1 · 1! = 1 = 2!− 1 = 2 · 1− 1
(ii) Hipo´tese Indutiva: P (k) = c1 · 1! + 2 · 2! + ... + k · k! = (k + 1)!− 1
(iii) Passo Indutivo: P(k+1)
P (k+ 1) = 1 · 1! + 2 · 2! + ...+ k · k! + (k+ 1) · (k+ 1)! = (k+ 1)!− 1 + (k+
1) · (k + 1)! = (k + 1)!(1 + (k + 1))− 1 = (k + 1)!(k + 2)− 1 = (k + 2)!− 1
Q.E.D.
2