turma 3ZC - Departamento de Matemática - PUC-Rio

DEPARTAMENTO DE MATEMÁTICA
MAT1310 – Matemática Discreta - P1
TURMA: 3ZC
PUC-RIO
09/04/2013
SOLUÇÕES
1. Para cada expressão lógica abaixo, encontre uma expressão equivalente que envolva apenas
os conectivos ∼ (“não”) e ∧ (“e”), além de variáveis lógicas (p, q, r) e parênteses.
(a) [5 pt] p ∨ q.
(Dica: Use as Leis de De Morgan.)
Solução: Usamos dupla negação e De Morgan:
p ∨ q ⇔ ∼ ∼(p ∨ q) ⇔ ∼((∼ p) ∧ (∼ q)) .
(b) [5 pt] p → q.
Solução: Usamos uma equivalência conhecida e o item anterior:
p → q ⇔ (∼ p) ∨ q ⇔ ∼ (∼ ∼ p) ∧ (∼ q) ⇔ ∼ p ∧ (∼ q) .
(c) [5 pt] p ∨ q ↔ r .
Solução: Usamos os itens anteriores:
p ∨ q ↔ r ⇔ p ∨ (q → r) ∧ (r → q)
⇔ ∼ (∼ p) ∧ ∼ (q → r) ∧ (r → q)
⇔ ∼ (∼ p) ∧ ∼ ∼ q ∧ (∼ r) ∧ ∼ r ∧ (∼ q)
2. Determine o valor lógico (V ou F) das seguintes proposições no universo R dos números
reais, justificando da maneira apropriada (demonstração, contra-exemplo, . . . ).
Destaque sua resposta final (V ou F), sob pena de ter o item anulado.
(a) [5 pt] (∀x)(x < 0 → x2 ≥ 0)
Solução: V erdadeira : o quadrado de qualquer número x (em particular dos
x < 0) é ≥ 0.
(b) [5 pt] (∀x)(∀y)(x2 = y 2 → x = y)
Solução: F alsa . Um contra-exemplo é x = 1, y = −1.
(c) [5 pt] (∀x)(∃y)(x < y ∧ y < x + 1)
Solução: V erdadeira . Dado x qualquer podemos tomar por exemplo y = x + 12 .
(d) [5 pt] (∀x)(x < x − 1 → x = 0)
Solução: V erdadeira : Para todo x, o predicado x < x − 1 é falso, e portanto a
implicação x < x − 1 → x = 0 é automaticamente verdadeira.
3. [15 pt] Encontre uma fórmula fechada para a expressão
n
Pn (x) = 1 + x 1 + x2 1 + x4 · · · 1 + x2
(onde n ≥ 0 é inteiro, x 6= 1 é real)
da forma
1 − xF (n)
,
1−x
onde F (n) é uma expressão que você deve determinar.
Pn (x) =
Prove que sua resposta é correta.
1−x2
1−x , logo F (0) = 2. Para n = 1 temos
2
1−(x2 )2
1−x4
2
P1 (x) = P0 (x) · (1 + x2 ) = 1−x
1−x · (1 + x ) = 1−x = 1−x , logo F (0) = 4. Para n = 2
4
1−(x4 )2
1−x8
4
temos P2 (x) = P1 (x) · (1 + x4 ) = 1−x
1−x · (1 + x ) = 1−x = 1−x , logo F (0) = 8.
Solução: Para n = 0 temos P0 (x) = 1 + x =
Aparentemente F (n) = 2n+1 . Vamos provar isso por indução.
Passo base: Vimos acima que F (0) = 2, e 20+1 = 2.
Passo indutivo: Se vale F (n) = 2n então
n+1
n+1
Pn+1 (x) = Pn (x) · 1 + x
2n+1
1 − x2
=
1−x
· 1+x
2n+1
n+2
1 − x2 )2
1 − x2
=
=
,
1−x
1−x
isto é, F (n + 1) = 2n+1 , como queríamos provar.
Por indução, vale F (n) = 2n+1 para todo inteiro n ≥ 0.
4. As palavras obtidas por re-arranjo das letras de uma palavra dada são chamados os seus
anagramas; por exemplo, a palavra ABA tem 3 anagramas: AAB, ABA, BAA.
(a) [10 pt] Quantos anagramas tem a palavra BALACOBACO?
Dê uma resposta final numérica.
Solução: Temos 10 letras, sendo 2 B’s, 3 A’s, 1 L, 2 C’s e 2 O’s. Portanto a
resposta é
10!
= 75600 .
2! 3! 1! 2! 2!
(b) [10 pt] Suponha que item anterior contamos como válidos apenas aqueles anagramas
onde cada consoante é imediatamente seguida por uma vogal. (Por exemplo, o anagrama BOCOBALACA é válido, mas ABLACOBACO e ABACOBACOL são inválidos). Quantos anagramas válidos existem?
Dê uma resposta final numérica.
Solução: Com as consoantes BLCBC podemos formar
5!
= 30 anagramas.
2! 1! 2!
Com as vogais AAOAO podemos formar
5!
= 10 anagramas.
3! 2!
Intercalando cada anagrama das consoantes com cada anagrama das vogais, obtemos um anagrama válido diferente (por exemplo, intercalando BCBLC e OOAAA
obtemos BOCOBALACA). Portanto o número de anagramas válidos é 30 × 10 =
300 .
5. [15 pt] Quantos retângulos diferentes podem ser desenhados com lados contidos nos segmentos da grade abaixo?
(Um retângulo deve ter uma altura e uma largura não-nulas possivelmente iguais; retângulos
com as mesmas dimensões mas em posições diferentes são considerados diferentes.)
Dê uma resposta final numérica.
Solução: A grade contém 10 segmentos verticais e 6 segmentos horizontais. Cada
retângulo é unicamente especificado pelos segmentos que contém seus lados. Há 10
2 =
45 maneiras de escolher dois segmentos verticais, e 62 = 15 maneiras de escolher dois
segmentos horizontais. Portanto existem 45 × 15 = 675 retângulos.
6. [15 pt] Simplifique:
100
1 100
1 100
1 100
1 100
+
+
+ · · · + 99
+ 100
.
0
2 1
4 2
2
99
2
100
Solução: Considere a fórmula do binômio:
n
(x + y) =
n X
n
k=0
k
xn−k y k .
Substituindo n = 100, x = 1, y = 1/2, temos
100 1 100 X 100 1
=
1+
.
2
k 2k
k=0
Logo a resposta é (3/2)100 .