P3_12.2_Gabarito

Prévia do material em texto

UFSC - CTC - INE5403 - Fundamentos de Matema´tica Discreta para a Computac¸a˜o
Semestre 12.2 - Data: 12/dez/2012 - Prof. Daniel S. Freitas - Turma A - Terceira Prova
1. (1,0 ponto) Em relac¸a˜o a conjuntos parcialmente ordenados, analise as seguintes afirmativas:
I. Em um Reticulado, pode-se afirmar que: ∀a, b, c, a ∨ (b ∨ c) = a ∧ (b ∧ c).
II. Todo subconjunto de um poset linearmente ordenado e´ um sub-reticulado.
III. Em um Reticulado, e´ va´lido afirmar que: ∀a, b, c, se a ≤ b enta˜o a ∨ (b ∧ c) = b ∧ (a ∨ c).
IV. O poset dado por D12 pode ser considerado um Reticulado.
V. Para todo Reticulado, e´ va´lido afirmar que: se a ≤ c e b ≤ c, enta˜o a ∨ b ≤ c
Com base nesta ana´lise, e´ correto afirmar que:
Resposta: Somente a afirmativa I e´ falsa.
2. (1,0 ponto) Em relac¸a˜o ao conjunto parcialmente ordenado A = ({a, b, c, d, e, f},≤), representado pelo diagrama de Hasse abaixo, analise as
seguintes afirmativas:
I. A estrutura e´ um reticulado limitado, tendo a como menor elemento e f como maior elemento.
II. As cotas superiores de {b, c} sa˜o os elementos d e e.
III. O ı´nfimo de {d, e} e´ o elemento a.
IV. A estrutura A na˜o e´ reticulado.
V. A estrutura A possui apenas dois subconjuntos de 4 elementos totalmente ordenados: {a, b, d, f} e {a, c, e, f} .
VI. O supremo de {b, c, a} e´ o elemento e
A ana´lise permite concluir que
Resposta: somente IV e´ Verdadeira
3. (1,0 ponto) A quantidade de reticulados diferentes que existem sobre A = {a, b, c, d} e´ dada por: (dica: um reticulado e´ definido pela disposic¸a˜o
dos elementos sobre um diagrama de Hasse)
Resposta: 4! +A(4, 2)
Justificativa: (Reticulados e Diagramas de Hasse)
• todo reticulado pode ser associado com o seu diagrama de Hasse;
• existem apenas duas possibilidades de estrutura para o diagrama de Hasse de um reticulado com 4 elementos:
o o
| / \
o o o
| \ /
o o
|
o
• cada reticulado diferente corresponde a uma maneira de acomodar os 4 elementos em uma destas duas estruturas;
• no primeiro caso, qualquer permutac¸a˜o dos 4 elementos gera um diagrama diferente;
• no 2o caso, o reticulado e´ determinado pelo maior elemento e pelo menor elemento: uma vez definidos estes dois, a posic¸a˜o dos outros dois
e´ irrelevante;
• portanto, existem 4! +A(4, 2) = 36 reticulados diferentes diferentes sobre um conjunto com 4 elementos �
4. (1,0 ponto) Analise as afirmac¸o˜es a seguir:
(a) Os 2 u´ltimos d´ıgitos de 9643 sa˜o 39.
(b) ∀a, b, c, d ∈ Z+, se a|b e c|d, enta˜o ac|bd.
(c) ∀n ∈ Z tal que n > 1, se ∃a ∈ Z tal que mdc(a, n) = 1 e an−1 ≡ 1 (mod n), enta˜o n e´ primo.
(d) A inversa multiplicativa s de 8 mo´dulo 67, que satisfaz 0 < s < 67, e´ dada por s = 17.
(e) Se a e b sa˜o congruentes mo´dulo 7, enta˜o 10a+ 13 e −4b+ 20 tambe´m sa˜o congruentes mo´dulo 7.
Com base nesta ana´lise, e´ correto afirmar que:
Resposta: somente duas afirmativas sa˜o V (“b” e “e”)
5. (0,5 ponto) O produto de treˆs nu´meros naturais e´ 105 e a sua soma e´ a maior poss´ıvel. Qual e´ esta soma?
Resposta: 107
6. (0,5 ponto) Qual das alternativas abaixo apresenta um divisor de 35 · 44 · 53?
Resposta: 45 = 32 · 51
7. (0,5 ponto) Quantos inteiros positivos menores do que 30 teˆm exatamente quatro divisores positivos?
Resposta: 9.
Justificativa:
• Sa˜o 7 nu´meros n do tipo pk · qm , aonde: p e q sa˜o primos e aonde k = 1 e m = 1
- nu´meros assim sa˜o menores do que 30 para as seguintes duplas {p, q}: {2, 3}, {2, 5}, {2, 7}, {2, 11}, {2, 13}, {3, 5}, {3, 7}
• E tambe´m sa˜o 2 nu´meros n do tipo pk , aonde: p e´ primos e aonde k = 3
- nu´meros assim sa˜o menores do que 30 para os seguintes valores de p: 2 e 3 �
8. (0,5 ponto) Quantos divisores positivos de 120 sa˜o mu´ltiplos de 6?
Resposta: 6.
Justificativa:
• 120 = 23 · 31 · 51 = (21 · 31) · 22 · 51
• Ou seja, na montagem dos divisores de 120, teremos liberdade de escolher apenas 3 expoentes para o fator primo 2 e 2 expoentes para o
fator primo 5, o que da´ um total de 6 escolhas poss´ıveis �
1
9. (2,0 pontos) Prove que ∀a, b ∈ Z, se a ≡ b (mod 3), enta˜o 2a2 ≡ 2b2 (mod 3).
Resposta: Isto e´ equivalente a mostrar que ∃k ∈ Z tal que 2a2 − 2b2 = 3.k
• sabemos que a ≡ b (mod 3) pode ser escrito como: ∃m ∈ Z tal que a = b+ 3.m
• substituindo isto na equac¸a˜o anterior, temos:
2a2 − 2b2 = 2.(b+ 3m)2 − 2.b2 =
= 2.(b2 + 6bm+ 9m2)− 2b2 = 12bm+ 18m2 = 3.(4bm+ 6m2)
• da´ı, uma vez que 4bm+ 6m2 e´ inteiro, podemos dizer que ∃n ∈ Z tal que 2a2 − 2b2 = 3.n
• logo: 2a2 ≡ 2b2 (mod 3) �
10. (2,0 pontos) Seja a operac¸a˜o y = x7 mod n, aonde n = p.q e´ dado pelo produto de 2 nu´meros primos.
(a) Com base no que foi visto em aula sobre o RSA, descreva uma forma eficiente (melhor do que testar todas as possibilidades) de se obter x
a partir de um valor dado y (ou seja, explique como obter de maneira eficiente a “raiz se´tima modular” de um valor y dado).
Resposta: esta operac¸a˜o e´ equivalente a uma cifragem do RSA, com expoente pu´blico e = 7. Enta˜o, para obter x novamente a partir do
y dado, basta fazer yd mod n, aonde d = 7−1 mod φ(n), para φ(n) = (p − 1).(q − 1). Isto vai funcionar porque 7.d ≡ 1 (mod φ(n)) ⇒
7.d = k.φ(n) + 1, de modo que, pelo Teorema de Euler, teremos yd ≡ x7.d ≡ (xφ(n))k.x1 ≡ x (mod n) (com o aux´ılio do Teorema Chineˆs
do Resto, pode-se mostrar que isto funciona mesmo quando mdc(x, n) 6= 1).
(b) Utilize o procedimento descrito no item anterior para obter o valor de x que satisfaz: x7 ≡ 4 (mod 33)
Resposta:
• φ(33) = φ(3× 11) = (3− 1)× (11− 1) = 20
• 7× d ≡ 1 (mod 20) ⇒ d = 3 (por simples inspec¸a˜o)
• desta forma, temos que: x = 43 mod 33 = 64 mod 33 = 31 �
2
Formula´rio (definic¸o˜es e fo´rmulas possivelmente u´teis):
• Relac¸a˜o R sobre um conjunto A e´ reflexiva sse: ∀a ∈ A, (a, a) ∈ R
• Relac¸a˜o R sobre um conjunto A e´ antissime´trica sse: sea 6= b, ∀a, b ∈ A, (a, b) ∈ R→ (b, a) /∈ R
• Relac¸a˜o R sobre um conjunto A e´ transitiva sse: ∀a, b, c ∈ A, (a, b) ∈ R ∧ (b, c) ∈ R→ (a, c) ∈ R
• Relac¸a˜o R sobre um conjunto A e´ uma relac¸a˜o de ordenamento sse R e´ reflexiva, antissime´trica e transitiva
• Dado um poset (A,≤), um elemento a ∈ A e´ chamado de um menor elemento de A se a ≤ x, ∀x ∈ A.
• Dado um poset (A,≤), um elemento b ∈ A e´ um elemento minimal de A se ¬∃x ∈ A tal que x < b
• Dado um poset (A,≤) e um subconjunto B ⊆ A, um elemento x ∈ A e´ uma cota superior (“upper bound”) de B, se ∀b ∈ B, b ≤ x e um
elemento y ∈ A e´ uma cota inferior (“lower bound”) de B, se ∀b ∈ B, y ≤ b
• Dado um poset (A,≤) e dois elementos x, y ∈ A, o supremo de {x, y}, denotado por x ∨ y = sup(x, y), se houver, e´ o menor elemento das cotas
superiores e o ı´nfimo de {x, y}, denotado por x ∧ y = inf(x, y), se houver, e´ o maior elemento das cotas inferiores
• Dado um reticulado (L,≤), vale: “a ≤ a ∨ b e b ≤ a ∨ b” e tambe´m: “se a ≤ c e b ≤ c, enta˜o a ∨ b ≤ c”
• Sejam 2 elementos de uma A´lgebra Booleana Bn: x = a1a2 . . . an e y = b1b2 . . . bn. Enta˜o:
x ≤ y ⇔ ak ≤ bk para k = 1, 2, . . . , n
x ∧ y = c1c2 . . . cn , onde ck = min{ak, bk} x ∨ y = d1d2 . . . dn , onde dk = max{ak, bk}
x′ = z1z2 . . . zn , onde: zk = 1 se xk = 0 e zk = 0 se xk = 1
• Teoria de Nu´meros: (a, b ∈ Z), (n ∈ Z, n > 1)
a|b⇔ b = a.k para k ∈ Z e a ≡ b (mod n)⇔ n|(a− b)
a = ba/nc × n+ (a mod n) [(a mod n)× (b mod n)] modn = (a× b) mod n
Teorema de Euler: se mdc(a, n) = 1, enta˜o: aφ(n) ≡ 1(mod n)
Func¸a˜o Totient de Euler: φ(n) = n.
∏
p|n
(
1− 1
p
)
em particular: φ(p.q) = (p− 1).(q − 1)
Se d = mdc(a, b), enta˜o: ∃ inteiros x e y tais que: d = ax+ by
Algoritmo euclideano estendido recursivo: (a na˜o-negativo e b positivo)
1. if b == 0 then return(a, 1, 0)
2. (d′, x′, y′) = Euclideano-estendido(b , amod b)
3. (d, x, y) = (d′, y′, x′ − ba/bc.y′)
4. return (d, x, y)
RSA: cifragem: y = xemodn, decifragem: x = ydmodn onde: n = p.q, p e q sa˜o primos, e = d−1modφ(n)
3