P1 - 2011.1 - Gabarito

Prévia do material em texto

P1 de Lo´gica (INF1009) – 2011.1
Profs. Alexandre Rademaker e Cecilia Lustosa
Nome/Matr.:
1. (4 points) Usando Tableaux, em cada um dos ı´tens abaixo, indique se ha´ consequeˆncia lo´gica (table-
aux fechado) ou alguma interpretac¸a˜o que na˜o valide a consequeˆncia lo´gica.
(a) A→ (B ∧ C), C → D |= (A→ B) ∧ (A→ D)
Solution: A→ (B ∧C), C → D |= (A→ B)∧ (A→ D) sse ((A→ (B ∧C))∧ (C → D))→
((A→ B) ∧ (A→ D)) for uma tautologia.
F (((A→ (B ∧ C)) ∧ (C → D))→ ((A→ B) ∧ (A→ D)))
V (A→ (B ∧ C)) ∧ (C → D)
F (A→ B) ∧ (A→ D)
V (A→ (B ∧ C))
V C → D
F A→ B
V A
F B
F A V B ∧ C
V B
V C
F A→ D
V A
F D
F A V B ∧ C
V B
V C
F C V D
Como todos os ramos fecharam, temos que ha´ consequeˆncia lo´gica.
(b) A1 → A2, A2 → A3, A3 → A4 |= ¬A4 → A1 ∧ ¬A2 ∧ ¬A3
Solution: A1 → A2, A2 → A3, A3 → A4 |= ¬A4 → (A1 ∧ ¬A2 ∧ ¬A3) sse ((A1 →
A2) ∧ (A2 → A3) ∧ (A3 → A4))→ (¬A4 → (A1 ∧ ¬A2 ∧ ¬A3)).
F ((A1 → A2) ∧ (A2 → A3) ∧ (A3 → A4))→ (¬A4 → (A1 ∧ ¬A2 ∧ ¬A3))
V (A1 → A2) ∧ (A2 → A3) ∧ (A3 → A4)
F ¬A4 → (A1 ∧ ¬A2 ∧ ¬A3)
V ¬A4
F A1 ∧ ¬A2 ∧ ¬A3
F A4
V (A1 → A2)
V A2 → A3 ∧A3 → A4
V A2 → A3
V A3 → A4
F A3
F A2
F A1 V A2
V A3
V A4
Como um dos ramos na˜o fechou (o ramos mais a` esquerda), temos que na˜o ha´ consequeˆncia
lo´gica. A interpretac¸a˜o que na˜o valida a consequeˆncia lo´gica e´: F (A1), F (A2), F (A3), F (A4),
pois com essa interpretac¸a˜o, as premissas sa˜o verdadeiras mas a conclusa˜o e´ falsa.
2. (2 points) Marque (V) ou (F) justificando:
(a) Se α tem β como consequeˆncia lo´gica enta˜o α e β sa˜o satisfat´ıveis.
Solution: Falso. Se α e´ insatisfat´ıvel, tem qualquer fo´rmula, inclusive β como consequencia
lo´gica.
(b) Se α ∧ β e´ Va´lida enta˜o tanto α quanto β sa˜o va´lidas.
Solution: Correto. Se α∧ β e´ va´lida, significa que qualquer interpretac¸a˜o faz esta fo´rmula
ser verdade. A u´nica forma de um ∧ ser verdade e´ quando ambas as suas sub-fo´rmulas sa˜o
verdade.
(c) Se α e´ insatisfat´ıvel enta˜o β → α tambe´m e´.
Solution: Falso. Se β tambe´m for insatisfat´ıvel, a fo´rmula sera´ va´lida.
(d) Se β → α e´ va´lida enta˜o β tem α como consegueˆncia lo´gica.
Solution: Correto. Pela definic¸a˜o β |= α sse |= β → α.
3. Considere o seguinte texto:
O inspetor Tuma esta´ encarregado da investigac¸a˜o de um roubo de quadros em uma galeria
de arte. Os seus assistentes sa˜o: Raul e Geraldo, que o auxiliam na investigac¸a˜o e que
Page 2
prenderam quatro pessoas: Ju´lia, Diego, Miguel e Francisco. Apo´s interrogar os suspeitos
os dois assistentes fornecem a seguinte informac¸a˜o ao inspetor Tuma: – Raul: ”Ju´lia e´
inocente, mas estou seguro de que pelo menos um dos outros e´ culpado-- Geraldo: ”se
Diego e´ o culpado, ha´ somente um cu´mplice entre os outros-- Raul: ”se Miguel e´ o culpado,
ha´ dois cu´mplices entre os outros.”
(a) (3 points) Considere que J , D, M e F indicam a culpabilidade de Ju´lia, Diego, Miguel e Fran-
cisco, respectivamente. As fo´rmulas abaixo deveriam representar proposic¸o˜es enunciadas pelos
assistentes do inspetor, mas algumas delas esta˜o com incorrec¸o˜es. Indique a incorrec¸a˜o mos-
trando a correc¸a˜o necessa´ria ou marque como “correta” cada fo´rmula abaixo, justifcando.
1. ¬J ∧ ((D ∨M ∨ F ) ∧ ¬(D ∧M) ∧ ¬(M ∧ F ) ∧ ¬(D ∧ F )).
2. M → ¬(D ∧ F ∧ J)
3. ((F ∧ J) ∨ (J ∧M) ∨ (F ∧M))→ ¬D
Solution:
¬J ∧ (D ∨M ∨ F ) (1)
D → ((F → ¬(J ∨M)) ∧ (M → ¬(J ∨ F )) ∧ (J → ¬(F ∨M))) (2)
M → ((D ∧ J) ∨ (F ∧ J) ∨ (D ∧ F )) (3)
Alternativas:
M → ((¬F → (D ∧ J)) ∧ (¬D → (F ∧ J)) ∧ (¬J → (D ∧ F )) (4)
(J ∨M ∨ F )→ (((F ∧ J) ∨ (J ∧M) ∨ (F ∧M))→ ¬D) (5)
(b) (1 point) Argumente (na˜o e´ necessa´rio construir Tableaux) que pode-se concluir que ¬M e´
consequeˆncia lo´gica das proposic¸o˜es enunciadas pelo problema. Dica: Argumente que se ¬M e´
falso enta˜o alguma das proposic¸o˜es enunciadas no problema tambe´m e´ falsa, indicando qual.
Solution: Observe que se ¬M e´ falso, enta˜o M e´ true. Mas se M e´ true, enta˜o ¬J → D∧F
necessariamente true (vide 3). Ora, ¬J e´ true (vide 1) enta˜o D ∧ F tambe´m precisam ser
true. Mas se D e´ true e se F e´ true, enta˜o ¬J ∧ ¬M e´ true (vide 2), contradic¸a˜o.
Outra poss´ıvel argumentac¸a˜o. Ju´lia e´ inoccente (ja´ foi dito no problea). Se Miguel for cul-
pado enta˜o ha´ dois cu´mplices, que so´ podem ser Francisco e Diego. Diego sendo culpado diz
implica em somente um cu´mplice. Portanto esta frase sobre Diego na˜o pode ser verdadeira.
Outra argumentac¸a˜o seria considerar a frase sobre Diego verdadeira e a a frase sobre Julia
como sendo falsa. Enfim, o objetivo era usar lo´gica em argumentac¸a˜o informal mas correta.
O tableaux completo da figura abaixo foi constru´ıdo com no site http://www.umsu.de/
logik/trees/.
Page 3
Definic¸o˜es Importantes nesta avaliac¸a˜o:
• Uma fo´rmula e´ satisfat´ıvel se e somente se e´ verdadeira para alguma valorac¸a˜o.
• Uma fo´rmula e´ va´lida se e somente se e´ verdadeira para todas as valorac¸o˜es.
• α tem β como consegueˆncia lo´gica (α |= β em s´ımbolos), se e somente se, β e´ verdadeira em toda
valorac¸a˜o que α e´ verdadeira. Equivalentemente, na˜o e´ poss´ıvel que β seja falsa em uma valorac¸a˜o
que faz α verdadeira.
Page 4