Lista 6 - Conjuntos 2021-1

1 Conjuntos nada mais são que uma coleção de objetos denominados elementos. Porém, existem algumas restrições para considerarmos uma coleção de objetos um conjunto. A primeira diz respeito a ordem. Em um conjunto a ordem dos elementos é irrelevante. A segunda é sobre a multiplicidade. Esta especifica que em um conjunto qualquer há somente uma ocorrência de um certo valor, isto é, não é permitido que um elemento apareça mais de uma vez em um mesmo conjunto. Uma vez que elementos podem ocorrer uma única vez em um conjunto, podemos dizer que a operação de determinar se um elemento está ou não em um conjunto possui um valor lógico (isto é, verdadeiro ou falso). Se A é um conjunto e x um elemento, representamos por x ∈ A por x ∈/ A. Note que a seguinte equivalência é verdadeira: x ∈/ A ≡ ¬(x ∈ A). o fato de x ser um elemento do conjunto A. Representamos que x não é um elemento de A Denominamos por cardinalidade ou tamanho o número de elementos de um conjunto. Se A é um conjunto, representamos por |A| o número de elementos de A. representado como {} ou ∅. Existe um único conjunto A tal que |A| = 0. Este é conhecido como conjunto vazio e é Raciocínio aparentemente bem fundamentado e coerente, embora esconda contradições de- correntes de uma análise insatisfatória de sua estrutura interna. Aluno: Artur Linhares de Oliveira Matricua: 20.1.8022 Lista de Exercícios 06: Conjuntos Revisão 1. Responda formalmente as seguintes questões: a) O que são conjuntos e quais são suas características? b) Descreva, de maneira sucinta, os métodos utilizados para descrever conjuntos. c) O que é um paradoxo? d) Enumere as operações sobre conjuntos vistas na disciplina. Definimos um conjunto por enumeração simplesmente listando seus elementos. Este é um método conveniente para conjuntos finitos que possuam poucos elementos. Exemplo: A notação de set comprehension permite-nos especificar um conjunto em termos de uma propriedade que descreve quais são os elementos deste. De maneira simples, temos que um V = {a, e, i, o, u}. set comprehension é representado da seguinte maneira: {x ∈ X | p(x)} em que x é uma variável (ou uma expressão), X um conjunto e p(x) é uma fórmula da lógica de predicados. Esta maneira de descrever conjuntos é útil para descrever conjuntos com muitos elementos ou infinitos. 2 Damos o nome de família conjuntos que possuem como elementos outros conjuntos contidos em um universo 𝐶 . Suas operações podem ser definidas como segue. P(A) = {X | X ⊆ A} T F = { x F = {x|∀A.A ∈ F → x ∈ A} |∃ A.A ∈ F ∧ x ∈ A} • Caso base: 1 ∈ I. • Passo recursivo: ∀n.n ∈ I → n + 2 ∈ I. • Caso base: 0 ∈ C. • Passo recursivo: ∀n.n ∈ C → n + 5 ∈ C. {−1, 1} {0, 1, 4, 9, 16, 25, 36, 49, 64, 81} e) O que são famílias de conjuntos e como podemos definir suas operações? Exercícios 2. (Ribeiro 5.3.4.1) Apresente uma definição recursiva do conjunto de números naturais ímpares. 3. (Ribeiro 5.3.4.2) Apresente uma definião recursiva do conjunto de números inteiros múltiplos de 5. 4. (Rosen 2.1.1) Liste todos os elementos dos conjuntos abaixo. a) {x | x é um número real, tal que x2 = 1}. b) {x | x é um número inteiro positivo menor que 12}. c) {x | x é o quadrado de um número inteiro e x < 100}. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} A = B ≡ ∀x.x ∈ A ↔ x ∈ B A ⊂ B ≡ A ⊆ B ∧ A /= B A ∪ B = {x | x ∈ A ∨ x ∈ B} A ∩ B = {x | x ∈ A ∧ x ∈ B} A = {x | x ∈ 𝐶 ∧ x ∈/ A} A − B = {x | x ∈ A ∧ x ∈/ B} A ⊆ B ≡ ∀x.x ∈ A → x ∈ B 3 {} Verdadeiro. O conjunto tem 4 elementos, logo o conjunto potência possui 24 = 16 elementos. d) {x | x é um número inteiro, tal que x2 = 2}. 5. (Rosen 2.1.7) Determine se cada uma das proposições abaixo é verdadeira ou falsa. a) 0 ∈ ∅ e) {0} ∈ {0} b) ∅ ∈ {0} f) {0} ⊂ {0} c) {0} ⊂ ∅ g) {∅} ⊆ {∅} d) ∅ ⊂ {0} 6. (Rosen 2.1.21) Quantos elementos cada um dos conjuntos abaixo tem, se a e b são elementos distintos? a) P ({a, b, {a, b}}) b) P ({∅, a, {a}, {{a}}}) c) P (P (∅)) 7. (Ribeiro 5.4.4.2) Seja I = {2, 3, 4, 5} e para cada i ∈ I considere que Ai = {i, i + 1, i − 1, 2i}. a) Liste os elementos de F = {Ai | i ∈ I}. b) 8. (Ribeiro 5.4.4) Apresente exemplos de conjuntos A e B tais que P(A ∪ B) /= P(A) ∪ P(B). O conjunto potência do conjuto vazio possui 20 = 1 elemento. O conjunto potência deste conjunto possui 21 = 2 elementos. O conjunto tem 3 elementos, logo o conjunto potência possui 23 = 8 elementos. Verdadeiro. Falso. Falso. Falso. Falso. Falso. Calcule T i∈I Ai e S i∈I Ai. S i∈ i∈I Ai = {1, 2, 3, 4, 5, 6, 8, 10}. I Ai = { 4} ; F = {{2, 3, 1, 4}, {3, 4, 2, 6}, {4, 5, 3, 8}, {5, 6, 4, 10}}. 4 Conjuto dos estudantes que moram a um quilômetro de distância da faculdade e que vão a pé para as aulas. Conjuto dos estudantes que moram a um quilômetro de distância da faculdade e que não vão a pé para as aulas. A ∩ B A ∪ B 9. (Rosen 2.2.1) Seja A o conjunto de estudantes que mora a um quilômetro de distância da faculdade e B, o conjunto dos estudantes que vão a pé para as aulas. Descreva quais são os estudantes em cada um dos conjuntos abaixo. a) A ∩ B b) A ∪ B c) A − B d) B − A 10. (Rosen 2.2.2) Suponha que A seja o conjunto dos veteranos de sua faculdade e B, o conjunto dos estudantes de matemática discreta de sua faculdade. Expresse cada um dos conjuntos abaixo em termos de A e B. a) o conjunto dos veteranos que assistem às aulas de matemática discreta em sua faculdade. b) o conjunto dos veteranos que não assistem às aulas de matemática discreta em sua faculdade. c) o conjunto dos estudantes que são ou veteranos ou assistem às aulas de matemática discreta em sua faculdade. d) o conjunto dos estudantes que ou não são veteranos ou não assistem às aulas de matemática discreta em sua faculdade. 11. (Ribeiro 5.6.1.2) Prove que, se A ⊆ B então B ⊆ A. A ∪ B. A − B Conjuto dos estudantes que não moram a um quilômetro de distância da faculdade e que vão a pé para as aulas. Conjuto dos estudantes que moram a um quilômetro de distância da faculdade ou que vão a pé para as aulas. Sejam dois conjuntos disjuntos A e B tais que |A| = m e |B| = n. Como os conjuntos são disjuntos, temos que |A ∪ B| = m + n, logo |P(A ∪ B)| = 2(m+n). Também, |P(A)| = 2m, e |P(B)| = 2n, logo, |P(A) ∪ P(B)| = 2m + 2n Portanto, P(A ∪ B) /= P(A) ∪ P(B). =/ 2(m+n). 5 Rascunho: Hipóteses X é arbitrário Conclusão (→) X ∈ P(A) X ∈ [P(A) ∩ P(B)] ∀X.X ∈ [P(A) ∩ P(B)] → X ∈ P(A ∩ B) P(A) ∩ P(B) ⊆ P(A ∩ B) X ⊆ A X ∈ P(A ∩ B) x é arbitrário x ∈ X Hipóteses X é arbitrário X ⊆ B X ∈ P(B) X ⊆ A ∩ B ∀x.x ∈ X → x ∈ A ∩ B x ∈ A ∧ x ∈ B x ∈ A ∩ B Conclusão (←) X ∈ P(A ∩ B) P(A ∩ B) ⊆ P(A) ∩ P(B) X ⊆ A ∩ B ∀X.X ∈ P(A ∩ B) → X ∈ [P(A) ∩ P(B)] x é arbitrário x ∈ X X ∈ [P(A) ∩ P(B)] X ⊆ A ∧ X ⊆ B X ∈ P(A) ∧ X ∈ P(B) ∀x.x ∈ X → x ∈ A ∧ ∀x.x ∈ X → x ∈ B Texto: x ∈ A ∧ x ∈ B Suponha A e B são conjuntos quaisquer (→) Suponha X arbitrário. Suponha X ∈ P(A) ∩ P(B). Suponha x arbitrário. Suponha x ∈ X. 12. (Ribeiro 5.6.1.4) Prove que P(A) ∩ P(B) = P(A ∩ B). Rascunho: Hipóteses Conclusão A ⊆ B ∀y.y ∈ A → y ∈ B ∀x.x ∈ B → x ∈ A B ⊆ A x é arbritário x ∈ B x ∈ A x ∈/ A x ∈ A x ∈ A → x ∈ B ⊥ Texto: Suponha que A ⊆ B Suponha que x é arbitrário e que x ∈ B. Suponha que x ∈/ A. Como x ∈/ A, temos que x ∈ A. Como x ∈ A e A ⊆ B, temos que x ∈ B. Como x ∈ B e x ∈ B temos uma contradição. Logo, x ∈ A. Como x é arbitrário, temos B ⊆ A. Logo, se A ⊆ B, então B ⊆ A. x ∈ B 6 Rascunho: Hipóteses Conclusão A ∪ B = A − B A ∪ B ⊆ A − B B = ∅ ⊥ x ∈ A ∨ x ∈ B → x ∈ A ∧ x ∈/ B ∀x.x ∈ (A ∪ B) → x ∈ (A − B) B /= ∅ x ∈ B ∃x.x ∈ B Texto: Suponha A ∪ B = A − B. Suponha B /= ∅. Seja x arbitrário e x ∈ B. Como x ∈ B, logo x ∈ A ∪ B. Como A ∪ B = A − B, logo x ∈ A − B. Como x ∈ A − B, logo x ∈/ B. Como x ∈ B e x ∈/ B, temos uma contradição. Logo, B = ∅. Logo, se A ∪ B = A − B então B = ∅. x ∈/ B 13. (Ribeiro 5.6.1.7) Prove que se A ∪ B = A − B então B = ∅. 14. (Ribeiro 5.6.1.11) Prove que se A e B − C são disjuntos então A ∩ B ⊆ C. Como X ∈ P(A) ∩ P(B), logo X ⊆ A e X ⊆ B. Como x ∈ X, X ⊆ A e X ⊆ B, logo x ∈ A ∩ B. Logo, se x ∈ X então x ∈ A ∩ B. Como x é arbitrário, temos que X ⊆ A ∩ B. Logo, se X ∈ P(A) ∩ P(B) então X ∈ P(A ∩ B). Como X é arbitrário, temos que P(A) ∩ P(B) ⊆ P(A ∩ B). (←) Suponha X arbitrário. Suponha x arbitrário. Suponha x ∈ X. Como X ∈ P(A ∩ B), logo X ⊆ A ∩ B. Como x ∈ X e X ⊆ A ∩ B, logo x ∈ A e x ∈ B. Logo, se x ∈ X então x ∈ A e x ∈ B. Como x é arbitrário, temos que X ⊆ A e X ⊆ B. Logo, se X ∈ P(A ∩ B) então X ∈ P(A) ∩ P(B). Como X é arbitrário, temos que P(A ∩ B) ⊆ P(A) ∩ P(B). Portanto, sendo A e B conjuntos, P(A) ∩ P(B) = P(A ∩ B). Suponha X ∈ P(A ∩ B). 7 Referências [1] Rodrigo G Ribeiro. Notas de aula de matemática discreta, 2016. [2] Kenneth H Rosen. Matemática discreta e suas aplicações. Sexta edição, 2009. Rascunho: Hipóteses x é arbitrário Conclusão A ∩ (B − C) = ∅ A e B − C são disjuntos A ∩ B ⊆ C ∀x.x ∈ A ∩ B → x ∈ C ∀x.x ∈/ A ∩ (B − C) x ∈ C ¬(x ∈ A ∧ x ∈ (B − C) ¬(x ∈ A ∩ (B − C) x ∈/ A ∨ x ∈/ B ∨ x ∈ C) x ∈/ A ∨ ¬(x ∈ B ∧ x ∈/ C) ¬(x ∈ A ∧ (x ∈ B ∧ x ∈/ C)) Texto: x ∈ A ∧ x ∈ B Suponha A e B − C são disjuntos. Suponha x arbitrário e que x ∈ A ∩ B. Como A e B − C são disjuntos, logo x ∈/ A ∩ (B − C). Como x ∈/ A ∩ (B − C), logo x ∈/ A ∨ x ∈/ B ∨ x ∈ C. Como x ∈ A ∩ B e x ∈/ A ∨ x ∈/ B ∨ x ∈ C, logo x ∈ C. Logo, A ∩ B ⊆ C. Logo, se A e B − C são disjuntos então A ∩ B ⊆ C.