md_LE5_Solucao

Prévia do material em texto

LISTA DE EXERCÍCIOS 5: SOLUÇÕES
UFMG/ICEx/DCC Matemática Discreta
Graduação em Ciência da Computação 2o Semestre de 2011
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.
Negação: ∃ um conjunto A tal que A ⊆ R e A 6⊆ Z.
A negação é verdadeira. Por exemplo, seja A = {x ∈ R|0 < x < 2}. Então A ⊆ R mas A 6⊆ Z, já que, por
exemplo, 12 ∈ A.
2. Sejam os seguintes conjuntos:
A = {m ∈ Z|m = 2i− 1, para algum inteiro i}
B = {n ∈ Z|n = 3j + 2, para algum inteiro j}
Prove se A = B.
Tem-se que A 6= B. Por exemplo, 1 ∈ A, já que a = 2 · 1 − 1, mas 1 6∈ 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 6∈ B. Assim, existe um elemento em A que não está em B.
Conseqüentemente, A 6= B.
3. Seja A = {1, 2, 3}, B = {u, v} e C = {m,n}. Liste os elementos do conjunto A× (B × C).
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.
Prova que B −A ⊆ B ∩Ac:
– Suponha x ∈ B −A.
– Pela definição de diferença de conjuntos, x ∈ B e x 6∈ 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.
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 6∈ A.
– Pela definição de diferença de conjuntos, x ∈ B e x 6∈ A.
1
– 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
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 = k+1.
– Hipótese indutiva:
(A1 −B) ∪ (A2 −B) ∪ . . . ∪ (Ak −B) = (A1 ∪A2 ∪ . . . Ak)−B
– Deve-se mostrar que:
(A1 −B) ∪ (A2 −B) ∪ . . . ∪ (Ak+1 −B) = (A1 ∪A2 ∪ . . . Ak+1)−B
Tem-se que:
(A1 −B) ∪ (A2 −B) ∪ . . . ∪ (Ak+1 −B)
Que pode ser reescrito como:
[(A1 −B) ∪ (A2 −B) ∪ . . . ∪ (Ak −B)] ∪ (Ak+1 −B) =
Pela hipótese indutiva temos:
[(A1 ∪A2 ∪ . . . Ak)−B] ∪ (Ak+1 −B)
Pela propriedade de diferença, ou seja, (X − Z) ∪ (Y − Z) = (X ∪ Y )− Z, para conjuntos X, Y e Z,
tem-se que:
(A1 ∪A2 ∪ . . . Ak ∪Ak+1)−B
6. Prove que para todos os conjuntos A, B e C, (A−B)− (B − C) = A−B.
A expressão (A−B)− (B − C) pode ser expressa como
(A ∩Bc) ∩ (B ∩ C)c 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
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.
– 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)
2
– 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.
Não, ou seja, (A−B) ∩ (C −B) 6= ∅.
– Sejam os conjuntos A = {1, 2}, B = {3} e C = {1, 4}.
– Tem-se que A−B = {1, 2}.
– Tem-se que C −B = {1, 4}.
– No entanto, (A−B) ∩ (C −B) = {1} 6= ∅, 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 (P(A×B)).
A×B = {(1, u), (1, v)}
P(A×B) = {∅, {(1, u)}, {(1, v)}, {(1, u), (1, v)}}
10. Determine P(P(∅)).
P(P(∅)) = P({∅}) = {∅, {∅}}
11. Prove se a afirmação é verdadeira ou não:
(a) Para todos os conjuntos A e B, (Ac −Bc) ⊆ (A ∪B)c.
(b) Para todos os conjuntos A, B e C, se A− (B ∩ C) e B − (A ∩ C) são necessariamente disjuntos.
onde Xc representa o complemento do conjunto X.
3