Lista4_MatDis

Prévia do material em texto

Lista 4 de Matemática Discreta I
Teoria dos Conjuntos
1. Liste os elementos dos seguintes conjuntos:
(a) {x | x é um número real tal que x2 = 1}.
(b) {x | x é um quadrado de um inteiro e x < 100}.
(c) {x | x é um inteiro tal que x2 = 2}.
2. Determine quais das seguintes afirmações são verdadeiras ou falsas.
(a) 0 ∈ ∅.
(b) ∅ ∈ {0}.
(c) {0} ⊂ ∅.
(d) {0} ∈ {0}.
(e) {∅} ⊂ {∅}.
3. Suponha que A, B e C são subconjuntos tais que A ⊂ B e B ⊂ C. Mostre que A ⊂ C.
4. Qual a cardinalidade de cada um dos conjuntos abaixo:
(a) {a}.
(b) {{a}}.
(c) {a, {a}}.
(d) {a, {a}, {a, {a}}}.
5. Qual a cardinalidade de cada um dos conjuntos abaixo se a e b são elementos
distintos.
(a) P({a, b, {a, b}}).
(b) P({a, b, b}).
(c) P(P(∅)).
6. Suponha que A × B = ∅. O que se pode dizer sobre os conjuntos A e B?
1
2
7. Seja A um conjunto. Mostre que ∅ × A = A × ∅ = ∅.
8. Qual a cardinalidade de A × B se A tem m elementos e B tem n elementos.
9. Explique porque A × B × C é diferente de (A × B) × C.
10. Determine o valor lógico de cada uma das setenças abaixo.
(a) ∀x ∈ R(x2 , −1).
(b) ∃x ∈ Z(x2 = 2).
(c) ∀x ∈ Z(x2 > 0).
(d) ∃x ∈ R(x2 = x).
(e) ∃x ∈ R(x3 = −1).
(f) ∃x ∈ Z(x + 1 > x).
(g) ∀x ∈ Z(x − 1 ∈ Z).
(h) ∀x ∈ Z(x2 ∈ Z).
11. Ache o valor lógico de cada um dos predicados abaixo considerando como domínio
o conjunto dos inteiros.
(a) P(x) : ”x2 < 3”.
(b) Q(x) : ”x2 > x”.
(c) R(x) : ”2x + 1 = 0”.
12. Prove que (A) = A.
13. Prove as identidades A ∪ ∅ = A e A ∩U = A.
14. Prove a lei comutativa para conjuntos, isto é, A ∪ B = B ∪ A e A ∩ B = B ∩ A
15. Sejam A e B conjuntos. Prove que A ∪ (A ∩ B) = A.
16. Sejam A e B conjuntos. Prove que A ∩ (A ∪ B) = A.
17. Sejam A e B conjuntos. Mostre que:
(a) (A ∩ B) ⊂ A.
(b) A ⊂ (A ∪ B).
(c) A − B ⊂ A.
(d) A ∩ (B − A).
(e) A ∪ (B − A) = A ∪ B.
(f) A − B = A ∩ B.
3
(g) (A ∩ B) ∪ (A ∩ B) = A.
18. O que se pode dizer dos conjuntos A e B se:
(a) A ∪ B = A.
(b) A ∩ B = A.
(c) A − B = A.
(d) A − B = B − A.
(e) A ∩ B = B ∩ A.
19. Sejam A e B subconjuntos de um conjunto universal. Mostre que A ⊂ B se, e só se
B ⊂ A. Esta é a análoga à contrapositiva em teoria de conjuntos.
20. Suponha que o conjunto universal U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Expresse cada um
dos conjuntos abaixo no formato “bit string”.
(a) {3, 4, 5}.
(b) {1, 3, 6, 10}.
(c) {2, 3, 4, 7, 8, 9}.
21. Usando o mesmo conjunto universal do exercício anterior e a representação “bit
string” para conjuntos, ache o conjunto especificado por cada “bit string” abaixo.
(a) 11 1100 1111
(b) 01 0111 1000
(c) 10 0000 0001
22. Seja U um conjunto universal finito. Dadas as “bit string” abaixo, indique o que
cada conjunto significa.
(a) uma string somente com zeros.
(b) uma string somente com uns.
23. Qual é a “bit string” correspondente à diferença de dois conjuntos?
24. Indique a união e a interseção dos conjuntos 01 0111 1000 e 11 0100 1110.