AD2-2012-2

Prévia do material em texto

Matemática Discreta – AD2 – 2012/2
Resoluções
1. [Enunciados com quantificadores e conjunto universo.] Dada uma generalização
∀xϕ(x) e um domı́nio de quantificação D, um contra-exemplo para ∀xϕ(x) em D é um
elemento x ∈ D para o qual o enunciado ϕ(x) é falso. Por exemplo, 1 é contra-exemplo para
∀x (x é par) em {1, 2}.
Considerando o conjunto universo U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} como domı́nio de quan-
tificação, para cada enunciado abaixo, apresente um contra-exemplo em U ou diga que um
contra-exemplo não existe. Em cada caso, justifique a resposta apresentada.
(a) ∀x(x ≤ 10 ∧ x + 5 < 15).
(b) ∀x(x é primo ∨ x é positivo).
(c) ∀x(x é par→ 1 ≤ x2).
(d) ∀x(x é primo→ x é par).
(e) ∀x(x não é número positivo↔ x não é número inteiro).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolução da Questão 1:
(a) 10 é um contra-exemplo, pois 10 + 5 = 15 6< 15.
Ou seja, x + 5 < 15 é F quando x é 10 e, portanto, x ≤ 10∧ x + 5 < 15 é F quando x
é 10.
(b) Não há contra-exemplo, pois 1 é positivo, 2 é positivo, . . . , 10 é positivo.
Ou seja, x é positivo é V qualquer que seja o valor que x assume em U e, portanto,
x é primo ∨ x é positivo é V qualquer que seja o valor que x assume em U .
(c) Não há contra-exemplo, pois 1 ≤ 12, 1 ≤ 22, . . . , 1 ≤ 102.
Ou seja, 1 ≤ x2 é V qualquer que seja o valor que x assume em U e, portanto, x é par→
1 ≤ x2 é V qualquer que seja o valor que x assume em U .
(d) 3 é um contra-exemplo, pois 3 é primo é V , mas 3 é par é F .
Ou seja, (x é primo→ x é par) é F quando x é 3.
(e) Não há contra-exemplo, pois 1 não é número positivo , 1 não é número inteiro ,
2 não é número positivo , 2 não é número inteiro , . . . , 10 não é número positivo ,
10 não é número inteiro são todos F .
Ou seja, x não é número positivo↔ x não é número inteiro é V qualquer que seja o valor
que x assume em U .
1
2. [Pertinência e inclusão.] Considere os conjuntos A = {1}, B = {1, 2} e C = {1, {1}}.
Classifique cada enunciado da Lista 1 como V ou F e associe os enunciados da Lista 2
aos enunciados da lista 1, de modo a produzir justificativas corretas e completas para a
classificação apresentada.
Lista 1 Lista 2
A ⊂ B ( ) s ∧ ¬r
B ⊂ A ( ) p ∧ v
A ∈ C ( ) p ∧ ¬w
A ⊂ C ( ) t ∧ u
C ∈ A ( ) p ∧ q
onde
p : 1 é o único elemento de A
q : 1 ∈ B
r : 2 ∈ A
s : 2 ∈ B
t : A = {1}
u : {1} ∈ C
v : 1 ∈ C
w : C = 1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolução da Questão 2:
A ⊂ B é V , pois 1 é o único elemento de A e 1 também é elemento de B. Assim, a justificativa
correta é p ∧ q.
B ⊂ A é F , pois 2 é elemento de B, mas 2 não é elemento de A. Assim, a justificativa
correta é s ∧ ¬r.
A ∈ C é V , pois A = {1} e {1} ∈ C. Assim, a justificativa correta é t ∧ u.
A ⊂ C é V , pois 1 é o único elemento de A e 1 também é elemento de C. Assim, a justificativa
correta é p ∧ v.
C ∈ A é F , pois 1 é o único elemento de A e C 6= 1. Assim, a justificativa correta é p ∧ ¬w.
2
3. [Definição de conjunto por listagem.] Considere os seguintes conjuntos A = {1},
B = {{x} ∈ U | x ∈ A} e C = {{2, 3}} ∪ {x ∈ U | x = D}, onde D = {3, 4}.
(a) Definir o conjunto B por listagem.
(b) Definir o conjunto C por listagem.
(c) Quantos elementos C possui?
(b) Listar todos os subconjuntos de C.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolução da Questão 3:
(a) 1 é o único elemento de A e B = {{x} ∈ U | x ∈ A}.
Logo, B = {1}.
(b) Como D = {3, 4}, temos que {x ∈ U | x = D} = {{3, 4}}.
Assim, C = {{2, 3}} ∪ {{3, 4}}.
Logo, C = {{2, 3}, {3, 4}}.
(c) C tem exatamente 2 elementos: {2, 3} e {3, 4}.
(d) Como C tem 2 elementos, C tem 4 subconjuntos: ∅, {{2, 3}}, {{3, 4}} e {{2, 3}, {3, 4}}.
3
4. [Definição de conjunto por propriedade.] Dado um conjunto E de empresas, denota-se
por En o conjunto de todas as empresas em E que possuem pelo menos n empregados, onde
n ∈ N.
Classifique como verdadeiro ou falso:
Para todos x, y ∈ N, se x ≤ y, então Ey ⊂ Ex.
Justifique a sua resposta.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolução da Questão 4:
Dados x, y ∈ N, com x ≤ y, temos que verificar se todo elemento de Ey também é elemento
de Ex.
Mas, temos que Ex é o conjunto de todas as empresas que possuem ao menos x empregados
e Ey é o conjunto de todas as empresas que possuem ao menos y empregados.
Assim, se uma empresa e ∈ Ey, ela possui ao menos y empregados.
Agora, como x ≤ y, temos que e também possui ao menos x empregados.
Ou seja, se uma empresa pertence a Ey, então ela pertence a Ex.
Assim, Ey ⊂ Ex e o enunciado é V .
4
5. [Problemas de contagem.] Considere a figura abaixo que representa os filamentos que
podem ser acesos para formar, por exemplo, d́ıgitos em uma calculadora:
Para representar um śımbolo, acendemos um certo grupo dos filamentos, incluindo a pos-
sibilidade de não acendermos nenhum filamento. Quantos śımbolos diferentes podem ser
representados?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolução da Questão 5:
Para referência, vamos considerar os filamentos numerados do seguinte modo:
2
1
3
5
4
6
7
Para formar um śımbolo, podemos tomar 7 decisões:
di : acender ou não o filamento i
onde 1 ≤ i ≤ 7.
Temos que
#di = 2
onde 1 ≤ i ≤ 7.
Assim, pelo PM, o número de śımbolos diferentes que podem ser representados é 2× 2× 2×
2× 2× 2× 2 = 27 = 128.
5
6. [Problemas de contagem.] De quantos modos 3 pessoas podem se sentar em 10 cadeiras
em fila?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolução da Questão 6:
Para referência, vamos chamar as pessoas de P1, P2 e P3.
Para sentar as pessoas nas cadeiras, podemos fazer 3 escolhas:
e1 : escolher uma cadeira para sentar P1
e2 : escolher uma cadeira ainda não escolhida para sentar P2
e3 : escolher uma cadeira ainda não escolhida para sentar P3
Temos que
#e1 = 10
#e2 = 9
#e3 = 8
Assim, pelo PM, o número de modos que as 3 pessoas podem sentar nas cadeiras é 10×9×8 =
720.
6
7. [Problemas de contagem.] Um vagão do metrô tem 10 bancos individuais, sendo 5 de
frente e 5 de costas. De 10 passageiros que ingressam neste vagão, 4 preferem sentar de
frente, 3 preferem sentar de costas e os demais não têm preferência. De quantos modos eles
podem se sentar, respeitadas as preferências?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolução da Questão 7:
Para referência, vamos chamar os passageiros que preferem os bancos de frente de F1, F2,
F3 e F4; os passageiros que preferem os bancos de costas de C1, C2 e C3; e os passageiros
que não tem preferência de N1, N2 e N3.
Para sentar os passageiros nos bancos, respeitando as preferências, podemos efetuar 10 tare-
fas:
t1 : escolher um banco de frente para P1
t2 : escolher um banco de frente ainda não escolhido para P2
t3 : escolher um banco de frente ainda não escolhido para P3
t4 : escolher um banco de frente ainda não escolhido para P4
t5 : escolher um banco de costas para C1
t6 : escolher um banco de costasainda não escolhido para C2
t7 : escolher um banco de costas ainda não escolhido para C3
t8 : escolher um banco qualquer ainda não escolhido para N1
t9 : escolher um banco qualquer ainda não escolhido para N2
t6 : escolher um banco qualquer ainda não escolhido para N3
Temos que
#t1 = 5
#t2 = 4
#t3 = 3
#t4 = 2
#t5 = 5
#t6 = 4
#t7 = 3
#t8 = 3
#t9 = 2
#t10 = 1
Assim, pelo PM, o número de modos de sentar os passageiros, respeitando as preferências,
é 5× 4× 3× 2× 5× 4× 3× 3× 2× 1 = 43.200.
c© 2012 Márcia Cerioli e Petrucio Viana
Coordenação da Disciplina MD/CEDERJ-UAB
7