Prévia do material em texto
Prova #2 - GCC103 - Matemática Discreta (Diurno) Prof. Eric Fernandes de Mello Araújo 18 de Maio de 2011 1. Eis as provas: (a) Seja x ∈ (∅∩A)∪ (B ∩A). Daí, podemos dizer que x ∈ (∅∩A)∨x ∈ (B ∩A). Podemos ainda afirmar que (x ∈ ∅ ∧ x ∈ A) ∨ (x ∈ B ∧ x ∈ A). Aplicando-se a propriedade de distributividade na proposição, teremos que (x ∈ ∅∨x ∈ B)∧(x ∈ ∅∨x ∈ A)∧(x ∈ A∨x ∈ B)∧(x ∈ A∨x ∈ A). Usando a simplifação, temos que (x ∈ A∨x ∈ A), donde chegamos que x ∈ A. Logo, (∅ ∩A) ∪ (B ∩A) ⊆ A, Q.E.D. (b) Nesse caso, teremos que provar (i) (A∩B)∪(A∩B)∪(A∩B) ⊆ (A∪B) e (ii) (A ∪B) ⊆ (A ∩B) ∪ (A ∩B) ∪ (A ∩B). (i) Seja x ∈ (A ∩ B) ∪ (A ∩ B) ∪ (A ∩ B). Daí, temos que x ∈ (A ∩ B) ∨ x ∈ (A ∩ B) ∨ x ∈ (A ∩ B). Podemos então dizer que (x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ B). Aplicando- se a distributividade entre os dois primeiros termos, teremos, [(x ∈ A ∨ x ∈ A) ∧ (x ∈ A ∨ x ∈ B) ∧ (x ∈ B ∨ x ∈ A) ∧ (x ∈ B ∨ x ∈ B)] ∨ (x ∈ A ∧ x ∈ B). Pelo princípio da dominação, teremos então [x ∈ U ∧ (x ∈ A∨ x ∈ B)∧ (x ∈ B ∨ x ∈ A)∧ x ∈ U)]∨ (x ∈ A∧ x ∈ B).Ainda pelo princípio da dominação, temos que [(x ∈ A ∨ x ∈ B) ∧ (x ∈ B ∨ x ∈ A)] ∨ (x ∈ A ∧ x ∈ B). Aplicando-se novamente a distributividade, temos [(x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∨ x ∈ B)] ∧ [(x ∈ A ∧ x ∈ B) ∨ (x ∈ B ∨ x ∈ A)]. Por simplifacação, ficamos com [(x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∨ x ∈ B)]. Por distributividade, temos (x ∈ A ∨ x ∈ B ∨ x ∈ A) ∧ (x ∈ A ∨ x ∈ B ∨ x ∈ B). Simplificando, teremos (x ∈ A ∨ x ∈ B), ou seja, x ∈ A ∪B. (ii) A volta é simétrica à ida, partindo de x ∈ A ∪ B, duplicando a expressão, para (x ∈ A ∪B) ∧ (x ∈ A ∪B) e assim por diante. 2. Os estudantes podem fazer C(12, 3)×C(9, 3)×C(6, 3)×C(3, 3), ou sim- plesmente 12! 3!3!3!3! . 3. Ache o menor número de cabos suficientes para conectar 100 computa- dores a 20 impressoras para garantir que 20 computadores podem acessar diretamente 20 impressoras diferentes. Cada cabo liga um computador a 1 uma impressora, e somente uma conexão pode ser feita de cada vez. Jus- tifique sua resposta. Considere os computadores como C1, C2, . . . , C100, e as impressoras P1, P2, . . . , P20. Considerando que devemos ter 20 computadores diferentes ligados à cada uma das 20 impressoras, colocamos 20 cabos para ligar os computadores C1 à impressora P1, C2 à impressora P2, até C20 à impressora P20. As demais máquinas mantém a configuração com a ligação de todos os com- putadores em todas as impressoras. Nesse caso, teríamos 20 cabos mais o restante, que daria 80× 20, obtendo-se um total de 1620 cabos. 4. Sejam A, B, C e D cursos de, respectivamente, arquitetura, biologia, cin- ema e desenho. Ache o número N de estudantes em um dormitório, con- siderando os seguintes dados: (a) 12 cursam A, 20 cursam B, 20 cursam C e 8 cursam D; (b) 5 cursam A e B; 7 cursam A e C; 4 cursam A e D; 16 cursam B e C; 4 cursam B e D; 3 cursam C e D; (c) 3 cursam A, B e C; 2 cursam A, B e D; 2 cursam B, C e D; 3 cursam A, C e D; (d) 2 cursam os quatro; (e) 71 não cursam nenhum. Usando o Princípio da Inclusão e Exclusão, temos N(A∪B∪C∪D) = N(A)+N(B)+N(C)+N(D)−N(A∩B)−N(A∩C)−N(A∩D)− N(B∩C)−N(B∩D)−N(C ∩D)+N(A∩B∩C)+N(A∩B∩D)+ N(A ∩ C ∩D) +N(B ∩ C ∩D)−N(A ∩B ∩ C ∩D). Assim, temos que N(A∪B ∪C ∪D) = 12 + 20 + 20 + 8− 5− 7− 4− 16− 4− 3 + 3 + 2 + 2 + 3 − 2 = 29. Somando com os que não cursam nenhum, temos 29 + 71 totalizando 100 estudantes. 5. Resolva para todos os inteiros x: (a) 3x ≡ 17(mod 19) Sabemos que 19|3x− 17. Dessa forma, temos que x = 12 (b) 2x+ 5 ≡ 7(mod 13) Sabemos que 13|2x+ 5− 7. Logo, x = 14. (c) 10− 3x ≡ 2(mod 11) Sabemos que 11|10− 3x− 2. Logo, x = −1 (d) 100x ≡ 74(mod 127) - ANULADA (O correto seria 100x ≡ 73(mod 127) ) Sabemos que 127|100x− 73. Logo, x = 2 2