lista2 gabarito inf1009 Logica PUCRio

Prévia do material em texto

Lógica para Computação
2016.1 – Lista 2
Profs. Cecilia Englander e Guilherme Lima
1. Um vaso antigo e valioso foi roubado de um museu. O ladrão (ou os ladrões) fugiu(ram) de carro. Três famosos
delinquentes, A, B e C, foram presos e interrogados. Os seguintes fatos ficaram estabelecidos:
• nenhuma outra pessoa, salvo A, B e C, estava implicada no roubo;
• C nunca pratica nenhum roubo sem usar A (e talvez outros) como cúmplice;
• B não sabe dirigir.
(a) Traduza as informações dadas para a linguagem da Lógica Proposicional.
Solução: Usando A : “A é culpado”, B : “B é culpado” eC : “C é culpado”, temos que:
• A∨B ∨C
• C → A
• B→ (A∨C )
(b) Utilize tabela verdade para mostrar que A é culpado.
Solução:
A B C A∨B ∨C C → A B→C ∨ A
V V V V V V
V V F V V V
V F V V V V
V F F V V V
F V V V F V
F V F V V F
F F V V F V
F F F F V V
Pela tabela verdade acima, toda valoração que satisfaz A∨B ∨C ,C → A e B→C ∨ A também satisfaz A.
Logo, {A∨B ∨C ,C → A,B→C ∨ A} |= A, ou seja, A é culpado.
2. Ainda usando as informações da questão anterior, traduza para a linguagem da LP:
(a) Há pelo menos um culpado entre os suspeitos.
Solução: A∨B ∨C
(b) Há pelo menos dois culpados entre os suspeitos.
Solução: (A∧B)∨ (A∧C )∨ (B ∧C )
(c) Há exatamente um culpado entre os suspeitos.
Solução: (A∨B ∨C )∧ (A→ (¬B ∧¬C ))∧ (B→ (¬A∧¬C ))∧ (C → (¬A∧¬B))
(d) Há exatamente dois culpados entre os suspeitos.
Solução: ((A∧B)∨ (A∧C )∨ (B ∧C ))∧ ((A∧B)→¬C )∧ ((A∧C )→¬B)∧ ((B ∧C )→¬A)
(e) A ou B é culpado, mas não ambos.
Solução: (A∨B)∧¬(A∧B)
3. Complete as afirmações abaixo com satisfatível, insatisfatível, tautologia, falsificável ou npa (nada podemos afir-
mar) de forma que as sentenças sejam verdadeiras.
(a) Se β é tautologia, então α→β é . . . .
Solução: tautologia
(b) Se β é insatisfatível, então α→β é . . . .
Solução: npa
(c) Se α é satisfatível, então α∨β é . . . .
Solução: satisfatível
(d) Se α é insatisfatível, então α∧β é . . . .
Solução: insatisfatível
(e) Se α é insatisfatível, então α∨β é . . . .
Solução: npa
(f) Se α∧β é tautologia, então α é . . . e β é . . . .
Solução: tautologia, tautologia
(g) Se α→β é falsificável, então α é . . . e β é . . . .
Solução: satisfatível, falsificável
4. Dadas duas fórmulas α e β, diga se cada uma das afirmações abaixo é verdadeira ou falsa. Justifique.
(a) Se α é tautologia, então α |=β→α.
Solução: Verdadeira. Pela tabela verdade abaixo, toda valoração que satisfazα (qualquer uma) também
satisfaz β→α.
β α β→α
V V V
F V V
(b) Se α é insatisfatível, então α |=β→α.
Solução: Verdadeira. Pela tabela verdade abaixo, toda valoração que satisfaz α (nenhuma) também
satisfaz β→α.
β α β→α
V F F
F F V
(c) α∧β |=α∨β.
Solução: Verdadeira. Pela tabela verdade abaixo, toda valoração que satisfazα∧β também satisfazα∨β.
α β α∧β α∨β
V V V V
V F F V
F V F V
F F F F
(d) Se α≡ γ, então α→β≡ γ→β.
Solução: Verdadeira. Se α≡ γ então toda valoração que satisfaz α também satisfaz γ e vice versa. Logo,
pela tabela verdade abaixo, toda valoração que satisfaz α→ β também satisfaz γ→ β e vice versa, ou
seja, α→β≡ γ→β.
α γ β α→β γ→β
V V V V V
V V F F F
F F V V V
F F F V V
(e) Se α∨β é insatisfatível, então α |= ¬β.
Solução: Verdadeira. Pela tabela verdade abaixo, toda valoração que satisfaz α∨β (nenhuma) também
satisfaz ¬β.
α β α∨β ¬β
F F F V
(f) Se α∧β é tautologia, então β |=α.
Solução: Verdadeira. Pela tabela verdade abaixo, toda valoração que satisfaz β também satisfaz α.
α β α∧β
V V V
5. Utilizando tabelas verdade para justificar sua resposta, apresente uma fórmula equivalente à A→ B que utilize
apenas os conectivos lógicos {¬,∧}.
Solução: ¬(A∧¬B). Pela tabela verdade abaixo, toda valoração que satisfaz A→B também satisfaz¬(A∧¬B)
e vice versa, ou seja, as colunas de A→B e ¬(A∧¬B) são idênticas. Logo, A→B ≡¬(A∧¬B).
A B A→B A∧¬B ¬(A∧¬B)
V V V F V
V F F V F
F V V F V
F F V F V