Final de Matemática Discreta

Prévia do material em texto

UNIVERSIDADE FEDERAL RURAL DE PERNAMBUCO – UFRPE 
Matemática Discreta – Bacharelado em Sistemas de Informação 
Prova Final – valor 10 pontos 
 
 
Nome ________________________________________________ Nota __________ 
 
1. Considere a seguinte sentença: O produto de um inteiro par e um inteiro ímpar é par. 
a) Escreva a sentença na forma “se .. então”. 
b) Apresente sua contrapositiva. 
 c) É interessante usar a contrapositiva para provar esta afirmação? Justifique. 
 d) Prove a afirmação usando redução ao absurdo. 
 
2. Este sistema de especificações é consistente: O roteador pode mandar pacotes para o sistema principal 
somente se ele suportar um novo espaço de endereço. Para o roteador suportar um novo endereço é 
necessário que a última liberação do software seja instalada. Se a última liberação do software estiver 
instalada, o roteador pode mandar pacotes para o sistema principal. O roteador não suporta um novo 
espaço. 
3. Prove usando as definições de conjuntos que )()()( CABACBA  
4. Considere a seguinte sequência definida pela recorrência: a0=3 e, para n>0, seja an = an-1 + n. Prove 
que 
2
62 

nn
an
. 
5. Calcule o inverso de 7 módulo 23 e resolva a equação 7� ≡ 5 ��� 23. Cite uma aplicação do uso 
de inverso modular. 
 
6. Seja o grafo G: 
 
a) Considere a relação “está ligado” no conjunto dos vértices de G. Verifique todas as 
propriedades dessa relação. Essa é uma relação de equivalência? Se sim, determine uma 
partição para V(G). 
b) Defina ciclo Hamiltoniano, caminho Euleriano, grau de um vértice e grafo completo. 
 
7. Sabendo que 
 
3
1
2
1
1
2









nnn
j
n
j
 calcule  



1
0
2 14)(5
n
i
ii 
8. Considere uma fechadura com 5 botões rotulados com os algarismos de 1 a 5. A fechadura se abre 
mediante a três ações. Cada ação consiste em apertar um dos botões, ou apertar dois botões 
simultaneamente. Por exemplo, 12-4-3 é uma combinação possível. A combinação 21-4-3 é mesma 
que 12-4-3 porque 12 ou 21 significa que apertamos simultaneamente os botões 1 e 2. Quantas 
combinações são possíveis?