provas 2016_2

Prévia do material em texto

UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ 
Campus Pato Branco 
ENGENHARIA DE COMPUTAÇÃO 
 
 
Prova Parcial 1: Matemática Discreta para Computação – 2016-2 
Aluno(a):__________________________________________________________ Data: 14/09/2016 
1. (1p) Para determinar a validade de um argumento são usadas tabelas verdade. Para simplificar a 
análise são identificadas as linhas críticas da tabela verdade: 
a. O que é uma linha crítica? 
b. Porque as linhas críticas permitem determinar a validade de um argumento? 
 
2. (1p) Expresse as especificações a seguir usando as proposições “p: O usuário entra com uma senha 
válida”, “q: O acesso é liberado” e “r: O usuário pagou a taxa de assinatura”, juntamente com 
conetivos lógicos. 
a. “O usuário pagou a taxa de assinatura, mas não entra com uma senha válida.” 
b. “O acesso é liberado sempre que o usuário pagar a taxa de assinatura e entrar com uma 
senha válida.” 
c. “O acesso é negado se o usuário não pagou a taxa de assinatura.” 
 
3. (1,5p) Encontre um contraexemplo, se possível, para estas proposições quantificadas 
universalmente, em que o domínio para todas as varáveis são todos os números inteiros. 
a. ( ) b. ( ) c. ( ) 
 
4. (2p) Considere ( ) como a proposição “x pode enganar y”, em que o domínio são todas as 
pessoas no mundo. Use quantificadores para expressar cada uma das proposições: 
 
Exemplo: Todos podem enganar Fred: ( ) 
 
a. Evelyn pode enganar a todos 
b. Todos podem enganar alguém 
c. Não há ninguém que possa enganar a todos 
d. Todos podem ser enganados por alguém 
 
5. (2p) Dadas estas duas suposições: 
i: “Lógica é difícil ou não muitos estudantes gostam de lógica” 
ii: “Se matemática é fácil, então lógica não é difícil” 
Transcreva as suposições em proposições que envolvam variáveis proposicionais e conectivos 
lógicos. Determine se cada uma das seguintes conclusões é válida para as suposições (Use regras de 
inferência e equivalência. Dica: transcreva também as conclusões): 
a. Matemática não é fácil, se muitos estudantes gostam de lógica. 
b. Poucos estudantes gostam de lógica, se matemática não é fácil. 
c. Matemática não é fácil ou lógica é difícil. 
d. Lógica não é difícil ou matemática não é fácil. 
 
6. (2,5p) Mostre que (indique o tipo de método utilizado): 
a. Se é um número inteiro e é ímpar então é par 
b. Se e são números inteiros pares, em que m, n e p são números inteiros, então 
 é par. 
 
UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ 
Campus Pato Branco 
ENGENHARIA DE COMPUTAÇÃO 
 
Prova Parcial 2: Matemática Discreta para Computação – 2016-2 
Aluno(a):_______________________________________________________________ Data: 19/10/2016 
 
1. (1p) Considere os seguintes subconjuntos de ℤ 
 
𝐴 = {𝑥|(∃𝑦)(𝑦 ∈ ℤ e 𝑦 ≥ 4 e 𝑥 = 3𝑦)} 
𝐵 = {𝑥|(∃𝑦)(𝑦 ∈ ℤ e 𝑥 = 2𝑦)} 
𝐶 = {𝑥|𝑥 ∈ ℤ e |𝑥| ≤ 10} 
 
Usando as operações de conjuntos, descreva cada um dos seguintes conjuntos em termos de A, B e C: 
 
a. { - 9, - 7, - 5 , - 3, - 1 , 0 , 1, 3, 5, 7, 9} b. {𝑥|(∃𝑦)(𝑦 ∈ ℤ e 𝑦 ≥ 2 e 𝑥 = 6𝑦)} 
 
2. (1p) Sejam: 
 
 𝐴 = {𝑥|𝑥 ∈ ℕ e 𝑥 ≥ 5} 𝐵 = {10, 12, 16, 20} 𝐶 = {𝑥|(∃𝑦)(𝑦 ∈ ℕ e 𝑥 = 2𝑦)} 
 
Quais das seguintes sentenças são verdadeiras 
a. 𝐵 ⊆ 𝐶 
b. 𝐴 ⊆ 𝐶 
c. {11, 12, 13} ⊆ 𝐴 
d. {12} ∈ 𝐵 
e. {𝑥|𝑥 ∈ ℕ e 𝑥 < 20} ⊈ 𝐵 
f. {∅} ⊆ 𝐵 
g. 𝐵 ⊂ 𝐴 
h. 26 ∈ 𝐶 
i. {11, 12, 13} ⊂ 𝐶 
j. {12} ⊆ 𝐵 
k. 5 ⊆ 𝐴 
l. ∅ ∉ 𝐴
 
3. (0,5p) Determine se cada um dos conjuntos abaixo é contável ou incontável. Para aqueles que forem contáveis, exiba 
uma bijeção entre o conjunto dos números naturais e o conjunto: 
 
a. O conjunto de todos os números racionais positivos que não podem ser escritos com denominadores menores que 4. 
b. O conjunto dos números reais que não tenha o 0 em sua representação decimal. 
 
4. (1p) De um exemplo de uma função 𝑓: ℕ → ℕ (dos naturais para os naturais) que seja: 
 
a. Injetora, mas não Sobrejetora. b. Nem Injetora nem Sobrejetora. 
 
5. (0,5p) Qual é a condição com respeito ao Domínio e a Imagem que devem cumprir duas funções para poder encontrar a 
função composta 𝑓𝑜𝑔 e 𝑔𝑜𝑓? Coloque um exemplo. 
 
6. (1,5p) Quantas soluções inteiras não negativas distintas existem para a equação: 
 
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 = 10 
Onde as soluções: 𝑥1 = 3, 𝑥2 = 1, 𝑥3 = 4, 𝑥4 = 2 e 𝑥1 = 4, 𝑥2 = 2, 𝑥3 = 3, 𝑥4 = 1 são consideradas distintas. 
 
7. (1p) Qual é o número de estudantes necessário em uma sala de matemática discreta para se ter certeza de que pelo menos 
seis receberão a mesma nota, se são possíveis cinco notas A, B, C, D e F? 
 
8. (1,5p) Use indução matemática e demonstre que 5 divide 𝑛5 − 𝑛 sempre que 𝑛 for um número inteiro não negativo. 
 
9. (2p) Use a definição de coeficientes binomiais e mostre que se n e k são inteiros positivos com nk 1 , então 
12 






k
kn
k
n
 
 
 
 
 
UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ 
Campus Pato Branco 
ENGENHARIA DE COMPUTAÇÃO 
 
Prova Parcial 3: Matemática Discreta para Computação – 2016-2 
Aluno(a):_______________________________________________________________ Data: 06/12/2016 
1. (1p) Definição: Uma relação de equivalência sobre um conjunto A é uma relação R sobre A que é reflexiva 
sobre A, simétrica e transitiva. Determine se a relação R no conjunto de todos os números reais é uma 
relação de equivalência se (x,y) ϵ R se e somente se: 
a) x + y = 0 b) x = ± y 
 
2. (1,5p) Teorema: A relação R em um conjunto A é transitiva se e somente se para n = 1, 2, 3, .... 
Seja R a relação no conjunto {1, 2, 3, 4, 5} com os pares ordenados (1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (3, 1), (3, 
4), (3, 5), (4, 2), (4, 5), (5, 1), (5, 2) e (5, 4). Determine: 
a) Determine R
2 b) Baseado na resposta de a. A relação R é transitiva? 
 
3. Seja a Relação R representada pelo dígrafo da Figura 1. Represente 
com uma matriz e: 
a) (0,5p) Explane como se determina se R é reflexiva ou simétrica 
usando a representação de matriz. 
b) (1,5p) R é Transitiva? Se não for utilize o algoritmo de Warshall 
e encontre o fecho transitivo. Apresente todos os passos. 
 
 Figura 1 
 
4. (0,5p) Utilize a forma da definição da questão 1 e defina Relação de Ordem Parcial e Relação de Ordem 
Total. 
5. (1p) Para a relação {(a, b)| a divide b} definida no conjunto {1, 2, 3, 4, 6, 8, 12}. Desenhe o dígrafo e o 
Diagrama de Hasse. 
 
6. (1,5p) Determine se os grafos U e da Figura 2 são 
isomorfos. Justifique apresentando a função de 
vértice e de aresta: 
 ( ) ( ) 
 ( ) ( ) 
 
Ou forneça um argumento rigoroso para provar 
que não existe isomorfismo. 
Figura 2 
7. (1p) Teorema de Kuratowski disse que “Um grafo é planar se e somente se não contém nenhum subgrafo 
homeomorfo a K3,3 ou K5 O que é homeomorfismo? Coloque um exemplo. 
 
 
8. (1p) Na figura 3 apresenta-se um grafo dirigido. 
Quais os critérios para determinar se um grafo 
tem: 
a) Circuito Euleriano ou Trajeto Euleriano? 
b) Use os critérios elencados no item (a) e 
verifique se o grafo tem circuito ou trajeto 
Euleriano. 
 
Figura 3 
9. (0,5p) Qual a diferença entre circuito Euleriano e Circuito Hamiltoniano? 
U V 
 
UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ 
Campus Pato Branco 
ENGENHARIA DE COMPUTAÇÃO 
 
Prova Substitutiva Matemática Discreta para Computação – 2016-2 
Aluno(a):_______________________________________________________________ Data: 13/12/2016 
 
1. (1p) Porque f não é uma função de ℤ para ℝ . Justifique sua resposta baseando-se na definição de função. 
 
a. 𝑓(𝑛) = ±𝑛 b. 𝑓(𝑛) = 1/(𝑛2 − 4) 
 
2. (1p) Encontre fog e gof , em que 𝑓(𝑥) = 𝑥2 + 1 e 𝑔(𝑥) = 𝑥 + 2. O que pode dizer respeito da comutatividade 
da composição de funções? 
 
3. (2p) Determine se as funções a seguir são bijetoras de ℝ para ℝ. Justifique sua resposta baseando-se nas 
propriedades que devem cumprir as funções para serem bijetoras. 
 
a. 𝑓(𝑥) = −3𝑥 +4 b. 𝑓(𝑥) = −3𝑥2 + 7 
 
4. (1p) Determine se a relação 𝑅 no conjunto de todos os números reais é reflexiva, simétrica, anti-simétrica e 
transitiva, em que (𝑥, 𝑦) 𝜖 𝑅 se e somente se 𝑥𝑦 ≥0. Justifique sua resposta baseando-se na definição de cada 
propriedade solicitada das relações. 
 
5. (2p) Quais das relações a seguir é um POSET? Justifique sua resposta baseando-se nas propriedades que deve 
ter um Poset: 
 
Seja S é o conjunto de todas as pessoas mundo e R uma relação sobre S, onde (𝑎, 𝑏) ∈ 𝑅 se: 
 
a. 𝑎 é mais alto que 𝑏. b. 𝑎 = 𝑏 ou 𝑎 é uma ancestral de 𝑏. 
 
 
6. (1p) Determine se os grafos da Figura 1 e 
2 são bipartidos, caso sejam apresente os 
dois conjuntos de vértices que verificam 
a partição. 
 
Figura 1 
 
Figura 2 
 
7. (1p) Para os grafos das Figuras 
3, 4 e 5: indique para cada um 
se há trajeto ou circuito 
euleriano e explane porque 
existe ou porque não existe. 
 
 Figura 3 Figura 4 Figura 5 
 
 
8. (1p) Defina conectividade em grafos 
não orientados. Baseado em sua 
definição determine se os grafos da 
Figura 6, 7 e 8 são conexos. Se não 
forem, encontre as componentes 
conexas. 
 Figura 6 Figura 7 Figura 8