Prova 2

Prévia do material em texto

Prova #2 - GCC103 - Matemática Discreta
(Noturno)
Prof. Eric Fernandes de Mello Araújo
11 de Maio de 2011
1. (a) Provaremos que (i) A∪(B−A) ⊆ A∪B e que (ii) A∪B ⊆ A∪(B−A).
(i) Seja x ∈ A∪ (B−A). Podemos afirmar que x ∈ A∨x ∈ (B−A). Daí,
temos que (x ∈ A) ∨ (x ∈ B ∧ x /∈ A). Aplicando-se a distributividade,
temos que (x ∈ A∨x ∈ B)∧ (x ∈ A∨x /∈ A). Por simplificação, podemos
afirmar que x ∈ A ∨ x ∈ B. Logo, x ∈ A ∪B.
(ii) Seja x ∈ A ∪ B. Logo x ∈ A ∨ x ∈ B. Podemos afirmar que todos os
elementos desse conjunto pertencem ao conjunto universo. Dessa forma,
(x ∈ A ∨ x ∈ B) ∧ x ∈ U . De outra forma, pelo princípio de dominação,
podemos dizer que (x ∈ A ∨ x ∈ B) ∧ (x ∈ A ∨ x /∈ A). Podemos afirmar
que a expressão anterior é equivalente a x ∈ A ∨ (x ∈ B ∧ x /∈ A). Logo,
x ∈ A ∪ (B −A). Q.E.D.
(b) Provaremos que (i) A ∩B ∩ C ⊆ A¯ ∪ B¯ ∪ C¯ e que (ii) A¯ ∪ B¯ ∪ C¯ ⊆
A ∩B ∩ C
(i) Seja x ∈ A ∩B ∩ C. Aplicando a Lei de DeMorgan, temos que x ∈
A ∩B∪C. Aplicando-se DeMorgan novamente, temos que x\in A∪B∪C.
(ii) Seja x ∈ A ∪ B ∪ C. Pela lei de DeMorgan, podemos dizer que x ∈
A ∩B ∪C. Novamente por DeMorgan, temos que x ∈ A ∩B ∩ C. Q.E.D.
2. Todos os conjuntos são referentes às partes. Logo, o número de subcon-
juntos que compõem as partes de um conjunto são dadas pela fórmula 2n,
onde n é o número de elemetos do conjunto. Dessa forma, temos:
(a) |P ({a, b, {a, b}})| = 23 = 8
(b) |P ({∅, a, {a}, {{a}}})| = 24 = 16
(c) |P (P (∅))| = 221 = 4. Nesse caso, temos que |P (∅)| = 2.
3. Quantos números com três dígitos:
(a) não contém o mesmo dígito três vezes: nesse caso, teríamos todas as
possibilidades de números detrês dígitos, com exceção dos que tem o
1
mesmo dígito três vezes. Logo, teríamos 10 × 10 × 10 − 10 possibil-
idades. Termos 1000 números possíveis de serem representados com
3 dígitos, de 000 até 999, sendo que os números 000, 111, 222, 333,
..., 888, 999 não satisfazem o enunciado.
(b) começam com um dígito ímpar: teremos então 5 possibilidades para o
primeiro dígito, somando-se então 5×10×10 números que satisfazem
esse enunciado.
(c) tem exatamente dois dígitos iguais a 4: nesse caso, teríamos como
alternativas uma combinação dos dois dígitos 4 com a possibilidade
dos demais dígitos complementando o terceiro valor. C(3, 2)× 9.
4. Um boliche tem 10 bolas vermelhas e 10 bolas azuis. Uma pessoa seleciona
bolas aleatoriamente sem olhar para elas.
(a) Quantas bolas precisam ser retiradas para ter certeza de que há pelo
menos três bolas da mesma cor?
Pelo princípio da casa do pombos podemos afirmar que são necessárias
5 bolas para garantir que três serão da mesma cor. Considerando as
cores como as casas, e as bolas como os pombos, nesse caso, teremos
obrigatoriamente uma cor com três bolas.
(b) Quantas bolas precisam ser selecionadas para ter certeza de que há
pelo menos três bolas azuis?
Pelo princípio da casa dos pombos, podemos afirmar que são necessárias
13 bolas para garantir que teremos três azuis. Considerando o pior
caso, onde todas as bolas vermelhas são retiradas primeiro, teríamos
a 13ª bola sendo a 3ª azul.
5. Quantas sequências diferentes podem ser obtidas com as letras da palavra
ABRACADABRA, usando-se todas as letras?
Considerando-se as repetições das letras A (5 vezes), B (2 vezes), C (1 vez),
D (1 vez) e R(2 vezes), com um total de 11 letras, temos
11!
5!×2!×1!×1!×2! ,
ou, usando combinações, C(11, 5)× C(6, 2)× C(4, 1)× C(3, 1)× C(2, 2).
2