Download Tarea 1 - Pontificia Universidad Católica de Chile

Pontificia Universidad Católica de Chile
Escuela de Ingenierı́a
Departamento de Ciencia de la Computación
Tarea 1
IIC2212 - Lógica para Ciencia de la Computación
Primer Semestre, 2004
Entrega: Martes 30 de marzo, a las 18 hrs.
1.
a) Demuestre que el conjunto {¬, →} es funcionalmente completo, y que {∧, ∨} no lo es.
b) Demuestre que en toda fórmula formalmente escrita de lógica proposicional, el doble del
número de conectivos es mayor o igual que el número de paréntesis.
Indicación: Debe definir inductivamente las funciones “número de conectivos” y “número
de paréntesis” de una fórmula de LP.
c) Demuestre, usandoWinducción, que si L(P ) es un lenguaje proposicional,
entonces la
Vn
n
fórmula de L(P ), ( i=1 ϕi ) → ψ, es lógicamente equivalente a i=1 (ϕi → ψ), para todo
n ≥ 1.
2.
Diga si las siguientes fórmulas de lógica proposicional son tautologı́as, contradictorias o sólo
satisfactibles y no válidas.
a)
b)
c)
d)
e)
f)
3.
(ϕ → ψ) → (ψ → ϕ).
(ϕ → ψ) → (¬ψ → ¬ϕ).
(q → ((p ∧ ¬p) → ¬r)) → ((q → (p ∧ ¬p)) → (q → ¬r)).
(p ∨ (p ∧ q)) ↔ p.
(p ∧ (p ∨ q)) ↔ ¬p.
(p ∧ (p → q)) ↔ p.
Diga si las siguientes afirmaciones son verdaderas o no, demostrando su respuesta.
a) Si φ1 y φ2 son fórmulas satisfactibles, entonces φ1 ∧ φ2 también lo es.
b) Si φ1 y φ2 son fórmulas satisfactibles, entonces φ1 ∨ φ2 también lo es.
c) Si φ1 y φ2 son fórmulas satisfactibles, entonces φ1 → φ2 lo es.
d ) Si φ es satisfactible, entonces siempre existe una fórmula ψ tal que φ → ψ es contradictoria.
e) Si ϕ es contradictoria, no existe una fórmula ψ tal que ψ → ϕ es tautologı́a.
f ) Si ϕ es satisfactible, ¬ϕ también lo es.
4.
1
Traduzca los siguientes razonamientos a lógica proposicional y luego demuestre si la conclusión
es o no consecuencia lógica de las premisas. Si la consecuencia no se concluye de las premisas
diga, en castellano, qué premisa hay que agregar1 para que sı́ lo haga. Demuestre usando la
definición de consecuencia lógica.
La premisa debe ser no trivial y debe mencionar información presente en las otras premisas.
a)
“Tendremos clases sólo si hay proyector de transparencias o si hay lápiz en la sala”
“No hay proyector de transparencias y Jorge no trajo lápiz”
“No tendremos clases”
b)
“Si crı́o cuervos entonces si éstos salen ágiles, aprenderé francés”
“Los cuervos no salen ágiles a menos que pasten junto a las vacas”
“Nunca aprenderé francés”
“No crı́o cuervos”
c)
“Era necesario que Sócrates dejara Atenas o tratara
de cambiar las leyes para que él no las aprobara”
“Si Sócrates no dejó Atenas y no trató de cambiar las leyes,
entonces estuvo de acuerdo con obedecerlas”
“Sócrates no trató de cambiar las leyes”
“Si Sócrates no aprobó las leyes o no estuvo de acuerdo con obedecerlas,
entonces dejó Atenas”
d)
“O bien Bush deja el poder o bien el terrorismo aumenta”
“Cuando el terrorismo aumenta, el dólar sube o hay atentados”
“Para que haya un atentado es necesario que termine
el curso de lógica o que Bush deje el poder”
“Bush deja el poder”
5. Suponga que Σ es un subconjunto arbitrario de un lenguaje proposicional. Diga si las siguientes afirmaciones son verdaderas o falsas, demostrando su respuesta.
a)
Si Σ ∪ {p} |= φ, entonces Σ |= φ.
b)
Σ ∪ {p ∨ ¬p} |= φ si y sólo si Σ |= φ.
c)
Si Σ ∪ {p → q} |= φ, entonces Σ ∪ {¬p} |= φ.
d)
Si Σ ∪ {p → q} |= φ, entonces Σ ∪ {p} |= (φ ∧ q).
e)
Σ ∪ {p} |= φ si y sólo si Σ ∪ {¬φ} |= (q → ¬(q → p)).
f)
Si Σ ∪ {ψ} |= χ y Σ ∪ {ψ → ϕ} |= χ, entonces Σ |= χ.
2