Prova 1 - José Afonso Barrionuevo

Prévia do material em texto

Matemática Discreta B 
Primeiro Exame 
 
02/10/2014 
 
 
Nome:______________________________Matrícula:__________Turma:_______ 
 
1. (a) Sejam X, Y, Z proposições. Suponha que X implica Y, e que Z implica X. Sabendo que Y é falsa, 
podemos concluir que: 
 A. ( ) Apenas X é falsa. B. ( ) Apenas Z é falsa. C. ( ) Z implica Y. 
 D. ( ) B e C. E. ( ) A e C F. ( ) X e Z são falsas. 
 G. ( ) Nenhuma das conclusões acima. 
 (b) Para provar que "se algum X é Y, então algum Z é W", é suficiente provar que: 
 A. ( ) Todo Z é X, e todo W é Y. B. ( ) Algum Z é X, e todo Y é W. 
 C. ( ) Todo X é Z, e todo Y é W. D. ( ) Todo X é Z, e algum Y é W. 
 E. ( ) Algum Z é X, e algum Y é W. F. ( ) Todo Z é X, e todo Y é W. 
 G. ( ) Algum X é Z, e todo Y é W. 
 
 
2. (a) Sejam A, B, C conjuntos não vazios. Mostre que A x (B - C) = (A x B) - (A x C). 
 (b) Sejam A1, A2, ... conjuntos. Seja E o conjunto formado pelos elementos que pertencem a infinitos dos 
conjuntos An. Mostre que 
 
 
3. Construa a tabela verdade para demonstrar a seguinte preposição 
[(p ⇒q) ∧ (q ⇒r) ] ⇒ (p ⇒ r) 
 
4. Demonstre as seguintes preposições: 
 (a) [(A ∨ B) ∧ (A ⇒ C) ∧ (B ⇒ C)] ⇒ C. 
 (b) Um número natural é divisível por 3 se, e somente se for a soma de 3 números inteiros 
consecutivos. 
 
5. Seja a relação R definida em Z por xRy ⇐⇒ x + 3y é múltiplo de 4. Mostre que R é relação de 
equivalência . 
 Descreva a clase de equivalência [5]R. 
 
 
6. (a) A sequência de equivalências abaixo está correta? Encontre o erro que forneça uma prova. 
{ ( x X P(x)) } ⇒ Q} ⇐⇒ { x X ~ P(x )) ∨ Q } ⇐⇒ { x X(~p(x )) ∨ Q } ⇐⇒ { x X(~p(x ) ⇒ Q) } 
 (b) Compare sua resposta na seguinte interpretação: Seja N um número natural, seja X = {1, 2,..., N-1}, 
seja P(x ) = x não é divisor de N, e Q = N é primo.