Gabarito Lista Inf1009 Logica PUCRIO

Prévia do material em texto

Lógica para Computação
2016.2 – Lista 1
Profs. Cecilia Englander e Guilherme Lima
1. Negue as seguintes sentenças1:
(a) Se eu estudar, vou passar em Lógica. Modelo de resposta: Estudo e não passo em Lógica.
Solução:
e : Eu estudo.
p : Eu passo em Lógica.
¬(e→ p)≡ e∧¬p
(b) Se o sol brilhar hoje, ele não brilhará amanhã.
Solução:
O sol brilha hoje e o sol brilhará amanhã.
h : O Sol brilha hoje.
a : O Sol brilha amanhã.
¬(h→¬a)≡ h∧a
(c) Pedro estava com ciúmes de Maria, ou ele não estava bem-humorado.
Solução:
Pedro não estava com ciúmes de Maria e estava bem-humorado.
m : Pedro estava com ciúmes de Maria.
h : Pedro estava bem-humorado.
6= (m∨¬h)≡¬m∧h
(d) Se o barômetro cair, então vai chover ou vai nevar. (Duas leituras)
Solução:
O barômetro cai e não chove e não neva (as duas leituras possuem a mesma negação2)
b : O barômetro cai
c : Vai chover
n : Vai nevar
¬((b→ c)∨n)≡¬(b→ (c∨n))≡ b∧¬c¬n
(e) Hoje vai chover ou vai fazer sol, mas não ambos.
Solução:
Chove se, e somente se, faz sol.
c : Chove
s : Faz Sol
¬(c∨ s)∧¬(c∧ s)≡ (c→ s)∧ (s→ c)≡ c↔ s
1Mais tarde você aprenderá uma tecnica para verificar se uma sentença é a negação de outra.
(f) Minha irmã quer um gato branco e preto.
Solução:
Minha irmã não quer um gato branco e preto.
m : Minha irmã quer um gato branco e preto.
¬m
(g) Maria não estuda nem trabalha.
Solução:
Maria estuda ou trabalha.
e : Maria estuda.
t : Maria trabalha.
¬(¬e∧¬t )≡ e∨ t
(h) Se Carlos ou Marcos forem à festa, então Pedro também irá.
Solução:
Carlos ou Marcos vão à festa e Pedro não vai.
c : Carlos vai à festa.
m : Marcos vai à festa.
p : Pedro vai à festa.
¬((c∨m)→ p)≡ (c∨m)∧p
(i) Se ferradura trouxesse sorte, burro não puxava carroça.
Solução:
Ferradura traz sorte e burro puxa carroça.
f : Ferradura traz sorte.
b : Burro puxa carroça.
¬( f →¬b)≡ f ∧b
(j) Eduardo abriu os olhos mas não quis se levantar.
Solução:
Eduardo não abriu os olhos ou quis se levantar.
a : Eduardo abriu os olhos.
l : Eduardo não quis se levantar.
¬(a∧¬l )≡¬a∨ l
(k) Se formos à praia e à feira, então não iremos ao cinema.
Solução:
Vamos à praia, à feira e ao cinema.
p : Vamos à praia.
f : Vamos à feira.
c : Vamos ao cinema.
¬(( f ∧ f )→¬c)≡ p∧ f ∧ c
(l) Se chover, então ficaremos em casa e veremos um filme.
Solução: Também admite duas leituras:
• (Se chover, então ficaremos em casa) e veremos um filme.
Chove e não ficamos em casa, ou não vemos um filme.
c : Chove
f : Ficaremos em casa.
v : Veremos um filme.
¬((c→ f )∧ v)≡ (c∧¬ f )∨¬v
• Se chover, então (ficaremos em casa e veremos um filme).
Chove e, não ficamos em casa ou não vemos um filme. ou
Chove e, se ficarmos em casa, não veremos um filme.
c : Chove
f : Ficaremos em casa.
v : Veremos um filme.
¬(c→ ( f ∧ v))≡ c∧ (¬ f ∨¬v)≡ c∧ ( f →¬v)
(m) Pedro saiu atrasado de casa e perdeu o ônibus.
Solução:
Se Pedro saiu atrasado de casa, então ele não perdeu o ônibus.
a : Pedro saiu atrasado.
p : Pedro perdeu o ônibus.
¬(a∧p)≡ (¬a∨¬p)≡ a→¬p
(n) Não acordou cedo, ou se tomou café, chegou atrasado ao trabalho.
Solução:
Acordou cedo, tomou café e não chegou atrasado ao trabalho.
a : Acordou cedo.
t : Tomou café.
c : Chegou atrasado ao trabalho.
¬(¬a∨ (t→ c))≡ a∧ t ∧¬c
2. Enumere todas as subfórmulas das seguintes fórmulas:
(a) ¬p∨ (q→ r ) Modelo de resposta: 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 = {¬(α∧β)→ (α∨¬β),¬(α∧β),α∨¬β,α∧β,α,β,¬β}
3. 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) Ele não sai para o trabalho sem tomar café. Modelo de resposta: Se “Ele partiu para o serviço”, então “Ele
tomou café da manhã”.
(b) 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)
(c) Acordou cedo mas chegou atrasado ao trabalho.
Solução: “Ele acordou cedo” e “Ele chegou atrasado ao trabalho”.
a∧ c
(d) 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
(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 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
(g) 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
4. Traduza as sentenças do exercício anterior para a linguagem da Lógica Proposicional.
(a) Ele não sai para o trabalho sem tomar café. Modelo de resposta: Se “Ele partiu para o serviço”, então “Ele
tomou café da manhã”. p→ t
5. Traduza as sentenças do primeiro exercício e suas respostas para a linguagem da Lógica Proposicional.