Lista de Exercicios Resolvidos Teoria dos Conjuntos Matematica Discreta UFMG

Lista de Exercícios 5 Soluções Teoria dos Conjuntos UFMGICExDCC DCC111 Matemática Discreta Ciências Exatas Engenharias 2o Semestre de 2014 1 Escreva uma negação para a seguinte afirmação conjuntos A se A R então A Z O que é verdadeira a afirmação ou sua negação Justifique a sua resposta Resposta Negação um conjunto A tal que A R e A Z A negação é verdadeira Por exemplo seja A x R0 x 2 Então A R mas A Z já que por exemplo 1 2 A 2 Sejam os seguintes conjuntos A m Zm 2i 1 para algum inteiro i B n Zn 3j 2 para algum inteiro j Prove se A B Resposta Temse que A B Por exemplo 1 A já que a 2 1 1 mas 1 B Se 1 fosse um elemento de B então teríamos 1 3j 2 para algum inteiro j o que daria 3j 2 1 3j 1 j 1 3 o que não é um número inteiro ou seja 1 B Assim existe um elemento em A que não está em B Conseqüentemente A B 3 Seja A 1 2 3 B u v e C m n Liste os elementos do conjunto A B C Resposta A B C 1 u m 2 u m 3 u m 1 u n 2 u n 3 u n 1 v m 2 v m 3 v m 1 v n 2 v n 3 v n 4 Prove que para todos os conjuntos A e B B A B Ac Resposta Prova que B A B Ac Suponha x B A Pela definição de diferença de conjuntos x B e x A Pela definição de complemento x B e x Ac Pela definição de intersecção x B Ac Assim pela definição de subconjunto B A B Ac 1 Prova que B Ac B A Suponha x B Ac Pela definição de intersecção x B e x Ac Pela definição de complemento x B e x A Pela definição de diferença de conjuntos x B e x A Assim pela definição de subconjunto B Ac B A Como B A B Ac e B Ac B A temos que B A B Ac 5 Prove por indução matemática que para todo inteiro n 1 e todos os conjuntos A1 A2 An e B A1 B A2 B An B A1 A2 An B Resposta Prova por indução matemática a Passo base Para n 1 a fórmula é expressa como A1 B A1 B que é claramente verdadeira Logo o passo base é verdadeiro b Passo indutivo se a fórmula é verdadeira para n k k 1 então deve ser verdadeira para n k1 Hipótese indutiva A1 B A2 B Ak B A1 A2 Ak B Devese mostrar que A1 B A2 B Ak1 B A1 A2 Ak1 B Temse que A1 B A2 B Ak1 B Que pode ser reescrito como A1 B A2 B Ak B Ak1 B Pela hipótese indutiva temos A1 A2 Ak B Ak1 B Pela propriedade de diferença ou seja X Z Y Z X Y Z para conjuntos X Y e Z temse que A1 A2 Ak Ak1 B 6 Prove que para todos os conjuntos A B e C A B B C A B Resposta A expressão A B B C pode ser expressa como A Bc B Ccc Representação alternativa para diferença A Bc Bc C De Morgan A Bc Bc A Bc C Distributividade A Bc Bc A Bc C Associatividade A Bc A Bc C Lei da interseção A Bc A C Bc Comutatividade A Bc A C Bc Associatividade Bc A Bc A C Comutatividade Bc A A C Distributividade Bc A Absorção A Bc Comutatividade A B Representação alternativa para diferença 2 7 Dados dois conjuntos A e B defina a diferença simétrica de A e B representada por A B como A B A B B A Prove se A B B A Resposta Sejam A e B conjuntos quaisquer Pela definição de mostrar que A B B A é equivalente a mostrar que A B B A B A A B Esta igualdade é obtida diretamente da comutatividade da 8 Prove se para todos os conjuntos A B e C A B e C B são necessariamente disjuntos Resposta Não ou seja A B C B Sejam os conjuntos A 1 2 B 3 e C 1 4 Temse que A B 1 2 Temse que C B 1 4 No entanto A B C B 1 ou seja a intersecção não é um conjunto vazio 9 Sejam os conjuntos A 1 e B u v Determine o conjunto potência de A B ie PA B Resposta A B 1 u 1 v PA B 1 u 1 v 1 u 1 v 10 Determine PPP Resposta O conjunto potência do conjunto vazio tem os dois elementos 21 2 abaixo ie o conjunto vazio e um subconjunto que tem um elemento que é o conjunto vazio P 1 2 O conjunto potência do conjunto potência do conjunto vazio tem os quatro elementos 22 4 abaixo o conjunto vazio e elementos formados a partir do conjunto 1 2 ou seja um subconjunto formado pelo primeiro elemento um subconjunto formado pelo segundo elemento e um subconjunto com os dois elementos PP 1 2 3 4 O conjunto PPP tem os 16 elementos 24 4 abaixo o conjunto vazio e 15 elementos formados a partir do conjunto 1 2 3 4 Esses 15 elementos são obtidos da seguinte forma quatro subconjuntos unitários cada um formado a partir dos conjuntos 1 2 3 e 4 acima seis subconjuntos de cardinalidade dois cada um formado a partir dos conjuntos 1 e 2 1 e 3 1 e 4 2 e 3 2 e 4 3 e 4 quatro subconjuntos de cardinalidade três cada um formado a partir dos conjuntos 1 2 e 3 1 2 e 4 1 3 e 4 2 3 e 4 um subconjunto de cardinalidade quatro com os quatro conjuntos 1 2 3 e 4 3 PPP 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 11 Seja A x y Determine a A PA Resposta O conjunto PA x y x y Assim A PA x y x y x y x y A b PA A A Resposta PA A x y x y x y x y Assim temos PA A A x y x y c PPA x Resposta PPA x P x y x y x P y x y Py x y y x y y x y 12 Prove que AB C ABAC usando apenas as propriedades de conjuntos sem usar diagrama de Venn Lembrese que dados dois conjuntos A e B A B sse A B e B A ou seja a prova deve ser feita em duas partes Resposta A prova deve ser dividida em duas partes 4 a A B C A B A C Suponha que exista um elemento x contido no conjunto resultante de A B C Pela definição da união temos duas possibilidades a x A ou b x B C ie x B e x C Devese provar que x está contido no conjunto resultante de A B A C Para x estar contido nesse conjunto resultante x A B e x A C No primeiro caso se x A então x estará na interseção dos dois termos ie caso a acima Se x A x deve pertencer simultaneamente a B e a C para estar na interseção dos dois termos ie caso b acima Assim se x é um elemento presente no conjunto resultante de AB C então x estará presente no conjunto resultante de ABAC b A B A C A B C Suponha que exista um elemento x contido no conjunto resultante de ABAC Pela definição de interseção temos que a x A ou x B e b x A ou x C Isto significa que x pertence a A ou x pertence simultaneamente a B e a C Devese provar que x está contido no conjunto resultante de A B C Para x estar contido nesse conjunto resultante x A ou x B C Mas essas duas condições representam exatamente a hipótese feita 13 Simplifique as seguintes expressões usando apenas as propriedades de conjuntos a A B C A B B Cc Resposta A B A C A Bc B Cc A Bc A B A Bc A C B Cc A A Bc C B Cc A B Cc b A A B B A B Resposta A A A B B A B B A B B A A Bc B Ac 14 Sejam os conjuntos A B e C Sabese que A B e os conjuntos B e C são disjuntos mas A e C têm elementos em comum Esboce se for possível o diagrama de Venn desses conjuntos Resposta Prova por contradição Suponha que sim que é possível fazer esse diagrama Suponha que x é o elemento em comum dos conjuntos A e C Sabese que A B Assim o elemento x deve também pertencer a B Logo B e C também devem ter um elemento em comum o que contradiz a afirmação que esses conjuntos são disjuntos Consequentemente não existe tal diagrama de Venn 5