lista estudo 01 gabarito

Prévia do material em texto

Lógica para Computação
2016.1 – Lista 1
Profs. Cecilia Englander e Guilherme Lima
1. Enumere todas as subfórmulas das seguintes fórmulas:
(a) ¬p∨ (q→ r )
Solução: S = {¬p∨ (q→ r ),¬p, (q→ r ),p,q,r }
(b) ¬¬α→β
Solução: S = {¬¬α→β,¬¬α,β,¬α,α}
(c) (α→ (β∧¬α))→¬α
Solução: S = {(α→ (β∧¬α))→¬α,α→ (β∧¬α),¬α,α,β∧¬α,β}
(d) (p→ q)→ (¬p∨ r )
Solução: S = {(p→ q)→ (¬p∨ r ),p→ q,¬p∨ r,p,q,¬p,r }
(e) p∨ (q ∧ r )
Solução: S = {p∨ (q ∧ r ),p,q ∧ r,q,r }
(f) ¬¬(p∧¬q)→ t
Solução: S = {¬¬(p∧¬q)→ t ,¬¬(p∧¬q), t ,¬(p∧¬q),p∧¬q,p,¬q,q}
(g) ¬(α∧β)→ (α∨¬β)
Solução: S = {¬(α∧β)→ (α∨¬β),¬(α∧β),α∨¬β,α∧β,α,β,¬β}
2. Reescreva cada sentença abaixo identificando os conectivos usados em sua formação. Note que todas as sen-
tenças podem ser reescritas usando apenas quatro sentenças atômicas (“Ele acordou cedo”, “Ele partiu para o
serviço”, “Ele tomou café da manhã” e “Ele chegou atrasado ao trabalho”.)
(a) Não acordou cedo, ou se tomou café, chegou atrasado ao trabalho.
Solução: Não é o caso que “Ele acordou cedo” ou, se “Ele tomou café da manhã”, então “Ele chegou
atrasado ao trabalho”.
Vamos usar a seguinte convenção:
a: “Ele acordou cedo”,
p: “Ele partiu para o serviço”
t: “Ele tomou café da manhã”
c: “Ele chegou atrasado ao trabalho”
¬a∨ (t→ c)
(b) Acordou cedo mas chegou atrasado ao trabalho.
Solução: “Ele acordou cedo” e “Ele chegou atrasado ao trabalho”.
a∧ c
(c) Acordou cedo, tomou café e partiu para o serviço.
Solução: “Ele acordou cedo” e “Ele tomou café da manhã” e “Ele partiu para o serviço”.
a∧ t ∧p
(d) Ele chega na hora ao trabalho ou toma café.
Solução: Não é o caso que “Ele chegou atrasado ao trabalho” ou “Ele tomou café da manhã”.
¬c∨ t
(e) Ele chega atrasado toda vez que toma café.
Solução: Se “Ele tomou café da manhã”, então “Ele chegou atrasado ao trabalho”.
t→ c
(f) Ele não sai para o trabalho sem tomar café.
Solução: Se “Ele partiu para o serviço”, então “Ele tomou café da manhã”.
p→ t
(g) Ele perdeu a hora, não tomou café e chegou atrasado ao trabalho.
Solução: Não é o caso que “Ele acordou cedo” e não é o caso que “Ele tomou café da manhã” e “Ele
chegou atrasado ao trabalho”.
¬a∧¬t ∧ c
(h) Se ele não acordar cedo ou se ele tomar café, então ele chegará atrasado ao trabalho.
Solução: Se não é o caso que “Ele acordou cedo” ou “Ele tomou café da manhã”, então “Ele chegou
atrasado ao trabalho”.
(¬a∨ t )→ c
3. Traduza as sentenças do exercício anterior para a linguagem da Lógica Proposicional.