P1 2012.1 com gab

Prévia do material em texto

Lógica para Computação
2012.1 – P1
Profs. Bruno Lopes e Marcela Cruz
1. Três deputados, João, Eduardo e Ricardo, da ALERJ, foram denunciados por um empresario que estava sendo
chantageado. Oministério público entrevistou cada deputado:
• “Foi o ilustríssimo Dr. Ricardo”, disse Dep. João.
• “Fui eu”, disse Dep. Eduardo, surpreendendo o procurador.
• “Foi o ilustre colega Dep. Eduardo”, disse o Dep. Ricardo.
O ministério, achando muito estranho, investigou e descobriu que somente um dos três dizia a verdade, e além
disso, apurou-se que o Dep. Eduardo estava mentindo. Formalize em lógica o problema e indique, justificando,
se ítens abaixo são verdade ou não. Use J para indicar que a frase de João é verdadeira e JC para indicar que João
é culpado; o mesmo para os demais personagens: R e E .
(a) (4 pontos) Pode-se deduzir que Ricardo, além de mentir, é culpado (é necessário a prova).
Solução:
F→ (∧(→ (J ,RC ),∧(→ (E ,EC ),∧(→ (R ,EC ),∧(→ (RC , J ),∧(→ (EC ,∧(E ,R)),∧(∨(J ,R),∧(¬(∧(J ,R)),∧(¬(E ),RC )))))))),∧(¬(R),RC ))
T ∧(→ (J ,RC ),∧(→ (E ,EC ),∧(→ (R ,EC ),∧(→ (RC , J ),∧(→ (EC ,∧(E ,R)),∧(∨(J ,R),∧(¬(∧(J ,R)),∧(¬(E),RC ))))))))
F ∧(¬(R),RC )
T→ (J ,RC )
T ∧(→ (E ,EC ),∧(→ (R ,EC ),∧(→ (RC , J ),∧(→ (EC ,∧(E ,R)),∧(∨(J ,R),∧(¬(∧(J ,R)),∧(¬(E ),RC )))))))
T→ (E ,EC )
T ∧(→ (R ,EC ),∧(→ (RC , J ),∧(→ (EC ,∧(E ,R)),∧(∨(J ,R),∧(¬(∧(J ,R)),∧(¬(E),RC ))))))
T→ (R ,EC )
T∧(→ (RC , J ),∧(→ (EC ,∧(E ,R)),∧(∨(J ,R),∧(¬(∧(J ,R)),∧(¬(E ),RC )))))
T→ (RC , J )
T ∧(→ (EC ,∧(E ,R)),∧(∨(J ,R),∧(¬(∧(J ,R)),∧(¬(E),RC ))))
T→ (EC ,∧(E ,R))
T ∧(∨(J ,R),∧(¬(∧(J ,R)),∧(¬(E ),RC )))
T ∨(J ,R)
T ∧(¬(∧(J ,R)),∧(¬(E),RC ))
T ¬(∧(J ,R))
T ∧(¬(E),RC )
T ¬(E)
⇒T (RC )
F ∧(J ,R)
⇒F (J )
F ¬(R)
T (R)
⇒F (RC ) ⇒T (J )
F ¬(R)
⇒T (R)
⇒F (RC ) ⇒F (RC )
⇒F (R)
F ¬(R)
⇒T (R)
⇒F (RC ) ⇒F (RC )
⇒F (RC )
⇒F (RC ) ⇒F (RC )
Uma vez que o tableau fecha, sim, pode-se deduzir esta relação.
(b) (1 ponto) EC é condição suficiente para R e E .
Solução: Sim, uma vez que caso Eduardo seja culpado, é impossível que os depoimentos de Ricardo e
Eduardo sejam falsos.
2. Apresente umaprova de que as seguintes relações são ounão válidas (em aomenos uma delas utilize um tableau).
(a) (11/2 pontos) ((a→ b)∧ (b→ a))→ (c→ c)⊢ (a→ b)∨ (¬c→¬b)
Solução: F→ (→ (∧(→ (a,b),→ (b,a)),→ (c,c)),∨(→ (a,b),→ (¬(c),¬(b))))
T→ (∧(→ (a,b),→ (b,a)),→ (c,c))
F ∨(→ (a,b),→ (¬(c),¬(b)))
F→ (a,b)
F→ (¬(c),¬(b))
T ¬(c)
F ¬(b)
⇒T (b)
F (c)
T (a)
⇒F (b)
Como o tableau fecha, a relação é válida
(b) (11/2 pontos) ((a∨b)∧ (¬b∨c))→ (¬a→ c)
Solução: F→ (∧(∨(a,b),∨(¬(b),c)),→ (¬(a),c))
T ∧(∨(a,b),∨(¬(b),c))
F→ (¬(a),c)
T ¬(a)
⇒F (c)
⇒F (a)
T ∨(a,b)
T∨(¬(b),c)
T ¬(b)
⇒F (b)
⇒T (a) T (b)
⇒T (c)
⇒T (a) ⇒T (a)
Como o tableau fecha, a relação é válida
3. (2 pontos) Apresente uma expressão equivalente à seguinte e a prova de sua equivalência, utilizando apenas a o
operador {→}: ¬(¬(a∧¬b)∧ (b∧¬c)).
Solução: (a→ b)→ (b→ c), com prova via tabela verdade.