P1_12.2_Gabarito

Prévia do material em texto

UFSC - CTC - INE5403 - Fundamentos de Matema´tica Discreta para a Computac¸a˜o
Semestre 12.2 - Data: 01/out/2012 - Prof. Daniel S. Freitas - Turma A - Primeira Prova
1. (2,0 pontos) Determine o valor verdade (V ou F) das proposic¸o˜es a seguir:
(V) ∀n ∈ Z+, a + ar + ar2 + · · ·+ arn−1 = a(1−rn)
1−r para r 6= 1
Justificativa (prova por induc¸a˜o):
• P (1) : a = a. (1−r)
(1−r) = a (OK)
• P (k) : a + ar + ar2 + · · ·+ ark−1 = a(1−rk)
1−r
• Assumindo que P (k) e´ V, sera´ que P (k + 1) : a + ar + ar2 + · · ·+ ark−1 + ark = a(1−rk+1)
1−r ??
• P (k + 1) : a + ar + ar2 + · · ·+ ark−1 + ark = a. (1−rk)
(1−r) + a.r
k (usando a hipo´tese indutiva)
=
a.(1−rk)+a.rk−a.rk+1
(1−r)
= a.
(1−rk+1)
(1−r) �
(F) ∀n ∈ Z+, 12 + 32 + 52 + · · ·+ (2n− 1)2 = n(n+2)(2n−1)
3
Justificativa: na˜o vale para n = 2, pois: 1 + 9 6= 2×4×3
3
(V) ∀n ∈ Z+ tal que n > 27, ∃a, b ∈ Z tais que n = 5a + 8b.
Justificativa (prova por induc¸a˜o forte):
• Passo ba´sico:
P (28) : 28 pode ser escrito como 5.4 + 8.1 (OK)
P (29) : 29 pode ser escrito como 5.1 + 8.3 (OK)
P (30) : 30 pode ser escrito como 5.6 + 8.0 (OK)
P (31) : 31 pode ser escrito como 5.3 + 8.2 (OK)
P (32) : 32 pode ser escrito como 5.0 + 8.4 (OK)
• Passo indutivo: P (k − 4)⇒ P (k + 1), pois:
– se P (k − 4) e´ V, temos que ∃A,B tais que k − 4 = 5A + 8B
– da´ı, para encontrar a e b tais que k + 1 = 5a + 8b, e´ so´ fazer: a = A + 1 e b = B
– isto vale para qualquer valor de k + 1 ≥ 33, pois k − 4 ≥ 28 �
(V) ∀n ∈ Z+, seja fn o n-e´simo nu´mero de Fibonacci, enta˜o: f21 + f22 + · · ·+ f2n = fn.fn+1.
Justificativa (prova por induc¸a˜o):
• P (1) : f21 = 12 = f1.f2 = 1.1 (OK)
• P (k) : f21 + f22 + · · ·+ f2k = fk.fk+1
• Assumindo que P (k) e´ V, sera´ que P (k + 1) : f21 + f22 + · · ·+ f2k + f2k+1 = fk+1.fk+2 tambe´m e´ sempre V ??
• P (k + 1) : f21 + f22 + · · ·+ f2k + f2k+1 = fk.fk+1 + f2k+1
= fk+1.(fk + fk+1)
= fk+1.fk+2 �
2. (1,0 ponto) Dadas as quatro premissas:
• “Se o universo e´ finito, enta˜o a vida e´ curta.”
• “Se a vida vale a pena, enta˜o a vida e´ complexa.”
• “Se a vida e´ curta ou complexa, enta˜o a vida tem sentido.”
• “A vida na˜o tem sentido.”
e as asserc¸o˜es:
I) se o universo e´ finito e a vida vale a pena, enta˜o a vida tem sentido;
II) a vida na˜o e´ curta;
III) a vida tem sentido ou o universo e´ finito;
quais asserc¸o˜es pode-se dizer que seguem logicamente das premissas dadas?
Resposta: somente (I) e (II).
Justificativa (prova):
• sejam as proposic¸o˜es:
f: “o universo e´ finito”
c: “a vida e´ curta”
p: “a vida vale a pena”
x: “a vida e´ complexa”
s: “a vida tem sentido”
• nestes termos, as asserc¸o˜es dadas sa˜o:
I) (f ∧ p) → s
II) ¬c
III) s ∨ f
1
Passo Justificativa
1) f → c hipo´tese
2) p→ x hipo´tese
3) (c ∨ x)→ s hipo´tese
4) ¬s hipo´tese
5) ¬c ∧ ¬x 3, 4, modus tollens
6) ¬c 5, simplificac¸a˜o ⇒ II e´ V
7) ¬f 6, 1, modus tollens
8) ¬s ∧ ¬f 4, 7, conjunc¸a˜o ⇒ III e´ F pois: (¬s ∧ ¬f) ⇔ ¬(s ∨ f)
9) ¬x 5, simplificac¸a˜o
10) ¬p 2, 9, modus tollens
11) ¬f ∧ ¬p 7, 10, conjunc¸a˜o ⇒ I e´ V pois: f e´ F e p tambe´m e´ F �
3. (1,0 ponto) As Olimp´ıadas Esportivas da UFSC sa˜o realizadas todo ano em uma certa semana de outubro. Esta ol´ımpiada ja´ e´ tradicional no
cena´rio catarinense e atualmente conta com seis modalidades: corrida, salto em distaˆncia, salto em altura, arremesso de peso, natac¸a˜o, e judoˆ.
Em uma edic¸a˜o t´ıpica desta competic¸a˜o, duas modalidades ocorrem na segunda-feira, duas na terc¸a-feira e duas na quarta-feira, obedecendo
a`s seguintes restric¸o˜es:
• Arremesso de peso ocorre no mesmo dia que natac¸a˜o.
• Corrida na˜o ocorre no mesmo dia que salto em distaˆncia.
• Se salto em altura ocorre na segunda-feira, corrida ocorre na terc¸a-feira.
• Se judoˆ ocorre na quarta-feira, salto em distaˆncia ocorre na terc¸a-feira.
Sabendo disto, responda a` seguinte questa˜o: se corrida ocorrer no dia anterior a natac¸a˜o, qual das seguintes modalidades na˜o pode ocorrer
em uma terc¸a-feira da olimp´ıada?
Resposta: salto em distaˆncia.
Justificativa:
• sejam os predicados:
C(x) : “tem corrida no dia x”
D(x) : “tem salto em distaˆncia no dia x”
H(x) : “tem salto em altura no dia x”
A(x) : “tem arremesso de peso no dia x”
N(x) : “tem natac¸a˜o no dia x”
J(x) : “tem judoˆ no dia x”
• nestes termos, as premissas dadas sa˜o:
I) ∀x, A(x)⇔ N(x)
II) ∀x, D(x)⇒ ¬C(x)
III) H(2a)⇒ C(3a)
IV) J(4a)⇒ D(3a)
• Como corrida ocorre no dia anterior a natac¸a˜o, temos duas opc¸o˜es: (C(2) ∧N(3)) OU (C(3) ∧N(4)).
• Qualquer que seja a opc¸a˜o, D(3a) nunca e´ verdade, pois:
– na opc¸a˜o 1 (C(2) ∧N(3)), a distribuic¸a˜o semanal de jogos fica:
2a 3a 4a
C N D
J A H
Justificativas:
∗ A(3a), pois: A(3a)⇔ N(3a) (instanciac¸a˜o de I)
∗ D(4a), pois: C(2a)⇔ ¬D(2a) (instanciac¸a˜o de II + contrapositiva)
∗ J(2a) pois: ¬D(3a)⇒ ¬J(4a) (IV, contrapositiva)
∗ H(4a) pois: ¬C(3a)⇒ H(2a) (III, contrapositiva)
– na opc¸a˜o 2 (C(3) ∧N(4)), a distribuic¸a˜o semanal de jogos tem duas possibilidades:
2a 3a 4a 2a 3a 4a
D C N D C N
H J A J H A
Justificativas:
∗ A(4a), pois: A(4a)⇔ N(4a) (instanciac¸a˜o de I)
∗ D(2a), pois: C(3a)⇔ ¬D(3a) (instanciac¸a˜o de II + contrapositiva)
∗ J(2a) ou J(3a), pois: ¬D(3a)⇒ ¬J(4a) (IV, contrapositiva)
∗ H(2a) ou H(3a), pois: C(3a) (de qualquer um dos dois jeitos, III e´ satisfeita)
4. (1,0 ponto) Considere a proposic¸a˜o s, dada por s : (p→ q) ∧ (¬p→ q), e as seguintes proposic¸o˜es:
(I) q ∨ q
(II) (¬p→ ¬q) ∨ (p→ ¬q)
(III) (¬p ∨ q) ∧ (p ∨ q)
(IV) q
(V) (¬q → p) ∧ (¬q → ¬p)
Quais proposic¸o˜es pode-se dizer que sa˜o logicamente equivalentes a` proposic¸a˜o s?
Resposta: (I), (III), (IV) e (V)
2
Justificativa:
• para comec¸ar, a tautologia p ∨ p⇔ p (ver formula´rio) ja´ indicava que as alternativas (I) e (IV) eram ideˆnticas
– de modo que as respostas que inclu´ıssem apenas uma delas ja´ poderiam ser eliminadas (o que eliminava dois itens)
– em seguida, podia-se constatar que as tautologias (¬p ∨ q)⇔ (p→ q) e (p→ q)⇔ (¬q → ¬p) mostravam imediatamente que as
alternativas (III) e (V) eram expresso˜es equivalentes a` s dada
– logo, a resposta deveria conter (III) e (V)
– com estas duas observac¸o˜es, chegava-se a` conclusa˜o de que a u´nica alternativa correta seria: (I), (III), (IV) e (V)
• alternativamente, esta conclusa˜o poderia se basear na construc¸a˜o de uma tabela-verdade:
p q ¬p ¬q p→ q ¬p→ q s ¬p→ ¬q p→ ¬q (II) (III) (V)
(I) ¬p ∨ q ¬q → p
(IV) ¬q → ¬p p ∨ q
V V F F V V V V F V V V
V F F V F V F V V V F F
F V V F V V V F V V V V
F F V V V F F V V V F F
– conclusa˜o: as colunas correspondentes a (I), (III), (IV) e (V) sa˜o equivalentes a` coluna de s, mas a coluna de (II) na˜o
• havia ainda a possibilidade da resposta correta ser obtida por uma aplicac¸a˜o das tautologias (¬p∨q)⇔ (p→ q) e (p→ q)⇔ (¬q → ¬p)
aos itens (II), (III) e (V) aliada a` seguinte sequeˆncia de aplicac¸o˜es de propriedades (listadas no formula´rio) para concluir que (I) e (IV)
eram equivalentes a s:
passo justificativa
(p→ q) ∧ (¬p→ q) proposic¸a˜o original
⇔ (¬p ∨ q) ∧ (p ∨ q) tautologia (¬p ∨ q)⇔ (p→ q)
⇔ ((¬p ∨ q) ∧ p) ∨ ((¬p ∨ q) ∧ q) tautologia da distributividade
⇔ ((¬p ∧ p) ∨ (q ∧ p)) ∨ ((¬p ∧ q) ∨ (q ∧ q)) tautologia da distributividade
⇔ F ∨ (q ∧ p) ∨ (¬p ∧ q) ∨ (q ∧ q) contradic¸a˜o
⇔ F ∨ (q ∧ p) ∨ (¬p ∧ q) ∨ q idempoteˆncia
⇔ F ∨ (q ∧ (p ∨ ¬p)) ∨ q tautologia da distributividade
⇔ F ∨ (q ∧ T ) ∨ q tautologia
⇔ (q ∧ T ) ∨ q tautologia F ∨ p⇔ p
⇔ q ∨ q tautologia q ∧ T ⇔ q
⇔ q idempoteˆncia �
5. (1,0 ponto) Assinale a proposic¸a˜o logicamente equivalente a ¬(p ∨ q) ∨ (¬p ∧ q):
(a) ¬p ∧ (q ∧ ¬q)
(b) ¬p
(c) (p ∨ q) ∧ (p ∨ ¬q)
(d) (p ∨ q) ∨ (p ∧ ¬q)
(e) p
Resposta: ¬p
Justificativa: ¬(p ∨ q) ∨ (¬p ∧ q) ⇔ (¬p ∧ ¬q) ∨ (¬p ∧ q) (2a lei de De Morgan)
⇔ ¬p ∧ (¬q ∨ q) (distributividade)
⇔ ¬p ∧V ((¬q ∨ q) e´ tautologia)
⇔ ¬p ((p ∧V)⇔ p) �
6. (1,0 ponto) Se e´ verdade que as treˆs sentenc¸as a seguir sa˜o verdadeiras:
(i) p⇒ q (ii) r ⇒ s (iii) (p ∧ t)⇔ r
enta˜o e´ verdade que:
Resposta: apenas ¬q ⇒ ¬r
Justificativa: aplicac¸a˜o direta das treˆs leis abaixo (todas listadas no formula´rio)
• ¬r ⇒ ¬s na˜o podeser V, pois se trata da inversa da 2a premissa
• ¬s⇒ (t ∨ p) na˜o pode ser V, pois:
passo justificativa
(1) ¬s⇒ ¬r (ii), contrapositiva
(2) ¬r ⇒ ¬(p ∧ t) (iii), contrapositiva
(3) ¬s⇒ ¬(p ∧ t) (1)+(2), silogismo disjuntivo
(4) ¬s⇒ (¬t ∨ ¬p) (3), De Morgan + comutatividade
– ou seja, o que sabemos e´ que a declarac¸a˜o que e´ V e´ aquela que envolve as negac¸o˜es de p e de t no consequente
– da´ı, como (t ∨ p) na˜o e´ equivalente a (¬t ∨ ¬p), temos que ¬s⇒ (t ∨ p) na˜o pode ser inferido a partir das premissas dadas
• finalmente, ¬q ⇒ ¬r e´, de fato, V, pois:
passo justificativa
(1) ¬p ∨ q (i), tautologia (p→ q)⇔ (¬p ∨ q)
(2) ¬r ∨ (p ∧ t) (iii), tautologia (p→ q)⇔ (¬p ∨ q)
(3) (¬r ∨ p) ∧ (¬r ∨ t) (2), lei de distributividade
(4) ¬r ∨ p (3), regra da simplificac¸a˜o
(5) ¬r ∨ q (1), (4), regra da resoluc¸a˜o
(6) q ∨ ¬r (5), lei da comutatividade
(7) ¬q → ¬r (6), tautologia (p→ q)⇔ (¬p ∨ q) �
3
7. (1,0 ponto) Prove que, ∀n ∈ N, n2 e´ par se e somente se n e´ par.
1) Fixe n (Instanciac¸a˜o Universal)
2) Prove que: n ı´mpar ⇒ n2 ı´mpar (contrapositiva de: n2 par ⇒ n par):
2.1) Assuma que n e´ ı´mpar
2.2) Enta˜o ∃k ∈ N / n = 2.k + 1 (definic¸a˜o de ı´mpar)
2.3) Escolha k ∈ N / n = 2.k + 1 (Instanciac¸a˜o Existencial)
2.4) da´ı: n2 = (2.k + 1)2 = 4.k2 + 4.k + 1 = 2.(2.k2 + 2.k) + 1 (a´lgebra)
2.5) ∃m ∈ N / n2 = 2.m + 1 (Generalizac¸a˜o Existencial)
2.6) n2 e´ ı´mpar (definic¸a˜o de ı´mpar)
3) Prove que: n par ⇒ n2 par:
3.1) Assuma que n e´ par
3.2) Enta˜o ∃k ∈ N / n = 2.k (definic¸a˜o de par)
3.3) Escolha k ∈ N / n = 2.k (Instanciac¸a˜o Existencial)
3.4) da´ı: n2 = (2.k)2 = 4.k2 = 2.(2.k2) (a´lgebra)
3.5) ∃m ∈ N / n2 = 2.m (Generalizac¸a˜o Existencial)
3.6) n2 e´ par (definic¸a˜o de par)
4) Generalize para todo n (GU) �
8. (1,0 ponto) Prove ou refute a seguinte conjectura: ∀x, y ∈ R, bxcbyc = bx.yc
• Esta conjectura na˜o e´ va´lida
• Basta notar que ela na˜o vale, por exemplo, quando x = 2 e y = 0.5 �
9. (1,0 ponto) Prove que o quadrado de um inteiro sempre termina com 0, 1, 4, 5, 6 ou 9. (Dica: note que qualquer inteiro sempre pode ser escrito
na forma n = 10.a + b, aonde a ∈ Z e b = 0, 1, ..., 9.)
• primeiro, note que (10a + b)2 = 100a2 + 20ab + b2 = 10(10a2 + 2ab) + b2
• de modo que o u´ltimo d´ıgito de n2 e´ o mesmo que o de b2
• por outro lado: o d´ıgito decimal final de b2 e´ o mesmo que o de (10− b)2 = 100− 20b + b2
• da´ı veˆm 6 casos (5 + 1), dados por: “u´ltimo d´ıgito = 1 ∨ 9, 2 ∨ 8, 3 ∨ 7, 4 ∨ 6, 5, 0”
– caso 1 ∨ 9: u´ltimo d´ıgito de n2 vale 1
– caso 2 ∨ 8: u´ltimo d´ıgito de n2 vale 4
– caso 3 ∨ 7: u´ltimo d´ıgito de n2 vale 9
– caso 4 ∨ 6: u´ltimo d´ıgito de n2 vale 6
– caso 5: u´ltimo d´ıgito de n2 vale 5
– caso 0: u´ltimo d´ıgito de n2 vale 0 �
Formula´rio (definic¸o˜es e fo´rmulas possivelmente u´teis):
• Conjuntos e sub-conjuntos (sejam A, B e C conjuntos):
A ∩B = {x| x ∈ A ∧ x ∈ B} A ∪B = {x| x ∈ A ∨ x ∈ B} A = {x|x /∈ A} A−B = {x| x ∈ A ∧ x /∈ B}
A ⊆ B ⇔ (x ∈ A→ x ∈ B) A = B ⇔ (A ⊆ B ∧ B ⊆ A) A×B = {(a, b)|a ∈ A ∧ b ∈ B}
P (A): conjunto formado por todos os subconjuntos de A (nota: |P (A)| = 2|A|)
A ∪B = B ∪A A ∩B = B ∩A A ∪ (B ∪ C) = (A ∪B) ∪ C A ∩ (B ∩ C) = (A ∩B) ∩ C
A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C) A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C) A ∪A = A A ∩A = A
• Regras de infereˆncia (sejam p, q e r proposic¸o˜es):
Adic¸a˜o: p→ (p ∨ q) Simplificac¸a˜o: p ∧ q → p
Modus Ponens: [p ∧ (p→ q)]→ q Modus Tollens: [¬q ∧ (p→ q)]→ ¬p
Silogismo hipote´tico: [(p→ q) ∧ (q → r)]→ (p→ r) Silogismo disjuntivo: [(p ∨ q) ∧ ¬p]→ q
Resoluc¸a˜o: [(p ∨ q) ∧ (¬p ∨ r)]→ (q ∨ r) Conjunc¸a˜o: ((p) ∧ (q))→ (p ∧ q)
• Tautologias: ¬(p ∧ q)⇔ (¬p ∨ ¬q) ¬(p ∨ q)⇔ (¬p ∧ ¬q) (¬p ∨ q)⇔ (p→ q) (p→ q)⇔ (¬q → ¬p)
p ∧ p⇔ p p ∨ p⇔ p p ∨ q ⇔ q ∨ p p ∧ q ⇔ q ∧ p (p ∨ q) ∨ r ⇔ p ∨ (q ∨ r) (p ∧ q) ∧ r ⇔ p ∧ (q ∧ r)
p ∨ (q ∧ r)⇔ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r)⇔ (p ∧ q) ∨ (p ∧ r)
• Predicados: ¬∀x P (x) ≡ ∃x ¬P (x) ¬∃x Q(x) ≡ ∀x ¬Q(x)
• Induc¸a˜o fraca: provar que P (1) e´ V E provar que P (k) ⇒ P (k + 1)
• Induc¸a˜o forte: provar que casos base sa˜o V E provar que (P (1) ∧ P (2) ∧ . . . ∧ P (k)) ⇒ P (k + 1)
• Definic¸a˜o: bxc e´ igual ao maior inteiro que e´ menor ou igual a x.
4