P1_12.1_Gabarito

Prévia do material em texto

UFSC - CTC - INE5403 - Fundamentos de Matema´tica Discreta para a Computac¸a˜o
Semestre 12.1 - Data: 13/abr/2012 - Prof. Daniel S. Freitas - Turma A - 1a Prova
1. (2,0 pontos) Seja A = {1, 2, 3, 4, 5}. Marque cada declarac¸a˜o abaixo como VERDADEIRA (V) ou FALSA (F):
(F) 5 ∈ P (A) (V) {{4, 5}} ⊆ P (A)
(F) ∅ ∈ A (V) ∅ ⊆ A
(V) {∅} ⊆ P (A) (V) ∅ ⊆ P (A)
(F) {∅} ∈ P (A) (V) (1, 1) ∈ A×A
2. (1,0 ponto) Sejam A,B e C conjuntos na˜o-vazios. Marque cada declarac¸a˜o abaixo como Verdadeira ou Falsa:
(V) A ∩ (B ∩ C) = (A ∩B) ∩ C (propriedade associativa de ∩)
(V) A−B = A ∩B
Prova:
1) Sejam A e B fixos (instanciac¸a˜o universal)
2) Prove que ∀x(x ∈ (A−B)⇔ x ∈ (A ∩B))
2.1) fixe x (Instanciac¸a˜o Universal)
2.2) prove que x ∈ (A−B) ⇒ x ∈ (A ∩B)
2.2.1) assuma que x ∈ (A−B)
2.2.2) enta˜o: (x ∈ A) ∧ (x /∈ B) (definic¸a˜o de diferenc¸a de conjuntos)
2.2.3) (x ∈ A) ∧ (x ∈ B) (definic¸a˜o de complemento)
2.2.4) x ∈ (A ∩B) (definic¸a˜o de intersecc¸a˜o)
2.3) prove que x ∈ (A ∩B) ⇒ x ∈ (A−B)
2.3.1) assuma que x ∈ (A ∩B)
2.3.2) enta˜o: (x ∈ A) ∧ (x ∈ B) (definic¸a˜o de intersecc¸a˜o)
2.3.3) (x ∈ A) ∧ (x /∈ B) (definic¸a˜o de complemento)
2.3.4) x ∈ (A−B) (definic¸a˜o de diferenc¸a de conjuntos)
2.4) Generalize para todo x (Generalizac¸a˜o Universal)
(F) A ∪B = A ∪B
• Contra-exemplo: U = {a, b, c, d} A = {a, b} B = {b, c}
(F) Se A ∪B = A ∪ C enta˜o B = C
• Contra-exemplo: A = {a, b, c} B = {b, c, d} C = {c, d}
3. (1,0 ponto) A fim de democratizar a discussa˜o sobre a pol´ıtica pu´blica cultural e fomentar os processos de produc¸a˜o de arte e cultura em todos
os centros e campi da Universidade Federal de Santa Catarina, a Secretaria de Cultura e Arte da UFSC instalou, em junho de 2011, uma
Comissa˜o Permanente de Cultura (CPC). O o´rga˜o reu´ne representantes de todos os Centros, dos quatro Campi, dos departamentos ligados a`
cultura e das entidades de classe dos estudantes (DCE), professores (APUFSC) e servidores (SINTUFSC). Em sua reunia˜o mensal de dezembro
de 2011, a principal deliberac¸a˜o da CPC foi a realizac¸a˜o de uma Semana de Cultura da UFSC, a qual devera´ acontecer todas as tardes de
segunda a sexta-feira, durante a terceira semana de setembro de 2012, no Centro de Eventos da UFSC. Em cada dia da Semana, havera´ a
apresentac¸a˜o de um grupo de teatro (pequenas pec¸as, que podem ser do geˆnero come´dia, drama ou romance) e a apresentac¸a˜o de um grupo de
mu´sica (que pode ser do geˆnero rock, samba ou funk). Ficou decidido que o programa desta Semana de Cultura devera´ obedecer a`s seguintes
condic¸o˜es gerais:
(1) Se uma pec¸a do geˆnero drama e´ programada para um dado dia, uma banda de rock deve se apresentar nesse mesmo dia.
(2) Se uma banda de funk e´ programada para um dado dia, uma pec¸a do geˆnero come´dia na˜o pode ser apresentada nesse mesmo dia.
(3) Em pelo menos um dia, uma pec¸a do geˆnero romance e uma banda de rock se apresentam juntos.
(4) Pec¸as do geˆnero romance nunca sa˜o programadas para dias consecutivos.
(5) Se pec¸as do geˆnero come´dia e do geˆnero drama sa˜o programadas para a Semana, pec¸as do geˆnero come´dia devem ser programadas em
dias anteriores a pec¸as do geˆnero drama.
(6) A programac¸a˜o de terc¸a-feira inclui a apresentac¸a˜o de uma banda de funk.
Sabendo que, adicionalmente, tanto pec¸as do geˆnero come´dia como pec¸as do geˆnero drama devera˜o ser programadas para a Semana, identifique
qual das afirmativas abaixo na˜o pode ser verdadeira:
Resposta: D (uma banda de funk e´ programada para 4a-feira)
Justificativa:
(i) Primeiro note que, pela condic¸a˜o 2, em um mesmo dia temos que: Funk ⇒ ¬Come´dia
(ii) Ale´m disto, pela condic¸a˜o 1, temos que (Drama ⇒ Rock), o que e´ equivalente a (¬Rock ⇒ ¬Drama) (tautologia da contrapositiva,
dispon´ıvel no formula´rio abaixo)
(iii) Ora, esta´ definido que a programac¸a˜o de 3a-feira inclui Funk (condic¸a˜o 6), de modo que, por (ii), na˜o pode incluir Drama
(iv) Logo, por (6)+(i)+(iii), na 3a-feira a programac¸a˜o devera´, necessariamente, incluir Romance
• Abaixo esta´ justificado, alternativa por alternativa, por que somente a alternativa D na˜o poderia ser V:
(a) Bandas de rock sera˜o programadas para dois dias consecutivos.
Pode ser V. Poss´ıvel configurac¸a˜o:
2a 3a 4a 5a 6a
pec¸a: Come´dia Romance Come´dia Romance Drama
mu´sica: Samba Funk Samba Rock Rock
1
(b) Pec¸as do geˆnero drama sera˜o programadas para dois dias consecutivos.
Pode ser V. Poss´ıvel configurac¸a˜o:
2a 3a 4a 5a 6a
pec¸a: Come´dia Romance Drama Drama Romance
mu´sica: Samba Funk Rock Rock Rock
(c) Samba na˜o sera´ um geˆnero de mu´sica programado na Semana.
Pode ser V. Poss´ıvel configurac¸a˜o: ver itens anteriores
(d) Uma banda de funk sera´ programada para quarta-feira.
Necessariamente F, pois necessariamente colocaria dois ”Romances”em dias consecutivos (pois, conforme comenta´rio acima, Funk ⇒
Romance), o que na˜o permitiria que a condic¸a˜o (4) fosse obedecida
(e) Pec¸as do geˆnero romance sera˜o programadas em dois dias.
Pode ser V. Poss´ıvel configurac¸a˜o: ver item b
(f) Uma pec¸a do geˆnero romance sera´ programada para terc¸a-feira.
Necessariamente V (ver comenta´rio acima)
4. (1,0 ponto) Dada a proposic¸a˜o: P : ∀x[B(x)→ [L(x) ∧ C(x)]], assinale a alternativa que conte´m uma proposic¸a˜o equivalente a ¬P .
(a) ∀x¬[B(x)→ [L(x) ∧ C(x)]]
(b) ∃x[B(x) ∧ [¬L(x) ∨ ¬C(x)]]
(c) ∀x[B(x)→ ¬[L(x) ∧ C(x)]]
(d) ∃x[¬B(x) ∧ [¬L(x) ∨ ¬C(x)]]
(e) ∃x[¬B(x) ∨ [L(x) ∧ C(x)]]
(f) ∀x[B(x) ∧ [¬L(x) ∨ ¬C(x)]]
Resposta: B
Justificativa: aplicac¸a˜o direta de leis listadas no formula´rio
passo justificativa
¬∀x[B(x)→ [L(x) ∧ C(x)]] negac¸a˜o de P
∃x¬[B(x)→ [L(x) ∧ C(x)]] ¬∀xP (x) ≡ ∃x¬P (x)
∃x¬[¬B(x) ∨ [L(x) ∧ C(x)]] (p→ q)⇔ (¬p ∨ q)
∃x[B(x) ∧ ¬[L(x) ∧ C(x)]] ¬(p ∨ q)⇔ (¬p ∧ ¬q)
∃x[B(x) ∧ [¬L(x) ∨ ¬C(x)]] ¬(p ∧ q)⇔ (¬p ∨ ¬q) �
5. (1,0 ponto) Assinale a proposic¸a˜o logicamente equivalente a ¬(p ∨ q) ∨ (¬p ∧ q):
(a) ¬p
(b) ¬p ∧ (q ∨ ¬q)
(c) (p ∨ q) ∧ (p ∨ ¬q)
(d) (p ∨ q) ∨ (p ∧ ¬q)
(e) p
(f) p⊕ q
Resposta: B (ou A)
Justificativa: usando tautologias listadas no formula´rio, temos que
• ¬(p ∨ q) ∨ (¬p ∧ q) ⇔ (¬p ∧ ¬q) ∨ (¬p ∧ q)
• (¬p ∧ ¬q) ∨ (¬p ∧ q) ⇔ (¬p ∧ (¬q ∨ q)) ⇔ (¬p ∧ (q ∨ ¬q))
Nota: o item (a) na˜o deveria estar presente, mas foi deixado por esquecimento, durante a elaborac¸a˜o da prova. De qualquer forma, ambas as
alternativas (A e B) foram consideradas corretas.
6. (1,0 ponto) A sentenc¸a lo´gica A ∧ (B ∨ ¬C) e´ equivalente a:
(a) A ∧ (¬B ∧ C)
(b) ¬A ∨ ¬(B ∨ ¬C)
(c) ¬A ∨ (¬B ∧ C)
(d) Todas as respostas anteriores
(e) Nenhuma das respostas anteriores
Resposta: E
Justificativa: Tabela Verdade:
A B C ¬A ¬B ¬C ¬B ∧ C B ∨ ¬C A ∧ (B ∨ ¬C) A ∧ (¬B ∧ C) ¬A ∨ (¬B ∧ C)
V V V F F F F V V F F
V V F F F V F V V F F
V F V F V F V F F V V
V F F F V V F V V F F
F V V V F F F V F F V
F V F V F V F V F F V
F F V V V F V F F F V
F F F V V V F V F F V
De acordo com a tabela verdade acima, vemos que:
• o bicondicional A ∧ (B ∨ ¬C)↔ A ∧ (¬B ∧ C) na˜o pode ser tautologia, de modo que A ∧ (B ∨ ¬C) 6⇔ A ∧ (¬B ∧ C)
• o bicondicional A ∧ (B ∨ ¬C)↔ ¬A ∨ (¬B ∧ C) na˜o pode ser tautologia, de modo que A ∧ (B ∨ ¬C) 6⇔ ¬A ∨ (¬B ∧ C)
• finalmente, uma vez que, pela 2a lei de De Morgan, temos que ¬A ∨ ¬(B ∨ ¬C) ⇔ ¬A ∨ (¬B ∧ C), sabemos que A ∧ (B ∨ ¬C) 6⇔
¬A ∨ ¬(B ∨ ¬C) �
2
7. (1,0 ponto) Existem treˆs suspeitos de invadir uma rede de computadores: Andre´, Bruna e Carlos. Sabe-se que a invasa˜o foi efetivamente
cometida por um ou por mais de um deles, ja´ que podem ter agido individualmente ou na˜o. Sabe-se, ainda, que:
I. Se Andre´ e´ inocente, enta˜o Bruna e´ culpada.
II. Ou Carlos e´ culpado ou Bruna e´ culpada, mas na˜o os dois.
III. Carlos na˜o e´ inocente.
Com base nestas considerac¸o˜es, conclui-se que:
(a) Somente Andre´ e´ inocente.
(b) Somente Bruna e´ culpada.
(c) Somente Carlos e´ culpado.
(d) Sa˜o culpados apenas Bruna e Carlos.
(e) Sa˜o culpados apenas Andre´ e Carlos.
Resposta: E
Justificativa:
• Pelo item III, sabemos que Carlos e´ culpado, de modo que as alternativas A e B podem ser descartadas
• Pelo item II, sabemosque Bruna na˜o e´ culpada, pois, de acordo com III, Carlos e´ culpado e II consiste em um ou-exclusivo, de modo
que a alternativa D pode ser descartada
• Como Bruna na˜o e´ culpada, sabemos, pela contrapositiva do item I, que Andre´ e´ culpado.
• Alternativamente, poderia ser feita uma prova formal, como em:
Sejam: A: “Andre´ e´ inocente”, B: “Bruna e´ inocente” e C: “Carlos e´ inocente”
passo justificativa
1) A→ ¬B (premissa)
2) (¬C ⊕ ¬B) (premissa)
3) (¬C ∧B) ∨ (C ∧ ¬B) (tautologia para ⊕ dispon´ıvel no formula´rio)
4) ¬C (premissa)
5) ¬C ∨B (4, adic¸a˜o)
6) ¬(C ∧ ¬B) (5, lei de De Morgan)
7) (¬C ∧B) (3, 6, silogismo disjuntivo)
8) ¬C (7, simplificac¸a˜o)
9) B (7, simplificac¸a˜o)
10) ¬A (1, 9, modus tollens) �
8. (1,0 ponto) Marque cada declarac¸a˜o abaixo como VERDADEIRA ou FALSA:
(F) ∀n ∈ Z+, n2 + 1 e´ ı´mpar se e somente se n e´ ı´mpar.
• Na˜o vale, por exemplo, para n = 3.
(F) ∀x, y ∈ R, bxcbyc = bx.yc
• Na˜o vale, por exemplo, para x = 3 e y = 0.5.
(V) Seja fn o n-e´simo nu´mero de Fibonacci. Enta˜o f21 + f
2
2 + · · ·+ f2n = fn.fn+1, aonde n e´ um inteiro positivo.
• Prova por induc¸a˜o fraca:
Passo ba´sico: P(1) e´ V, pois: 1 = 1× 1 (OK)
Passo indutivo: P(k) e´ V: “f21 + f
2
2 + ... + f
2
k = fk.fk+1”
Queremos obter: “f21 + f
2
2 + . . . + f
2
k + f
2
k+1 = fk+1.fk+2” (??)
Sabemos que: f21 + f
2
2 + ... + f
2
k + f
2
k+1 = fk.fk+1 + f
2
k+1
= fk+1.(fk + fk+1)
= fk+1.fk+2 �
(F) ∀n ∈ N, 1 + 2 + 22 + 23 + · · ·+ 2n = 2n−1
• Em uma tentativa de prova por induc¸a˜o, o passo ba´sico ja´ seria F, pois, para n = 0, ter´ıamos “1 6= 2−1”
• NOTA: o certo e´: ∀n ∈ N, 1 + 2 + 22 + 23 + · · ·+ 2n = 2n+1 − 1
9. (1,0 ponto) Prove que, ∀n ∈ Z+, 1 + 2 + 3 + · · ·+ n < 1
8
(2n + 1)2
Resposta: prova por induc¸a˜o fraca:
• Passo ba´sico: P(1) e´ V, pois: 1 < 9/8 (OK)
• Passo indutivo: vamos assumir que P(k) e´ V, de modo que, para k, temos: 1 + 2 + . . . + k < (1/8).(2k + 1)2
• (Queremos obter: 1 + 2 + . . . + k + (k + 1) < (1/8).(2k + 3)2) (??)
• (Ou, equivalentemente: 1 + 2 + . . . + k + (k + 1) < (1/8).(4k2 + 12k + 9)) (??)
• Podemos afirmar que: 1 + 2 + . . . + k + (k + 1) < (1/8).(2k + 1)2 + (k + 1)
= (1/8).(4k2 + 4k + 1 + 8k + 8)
= (1/8).(4k2 + 12k + 9) �
*********** FINAL DA PROVA ***********
3
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⊕ ¬q)⇔ (¬p ∧ q) ∨ (p ∧ ¬q) 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 P (1) e´ V E provar que (P (1) ∧ P (2) ∧ . . . ∧ P (k)) ⇒ P (k + 1)
• bxc = maior inteiro menor ou igual a x
4