Html5

L´gica Inform´tica (Ingenier´ del Software).
o
a
ıa

Curso 2013–2014.

Relaci´n 1: Sintaxis y sem´ntica de la l´gica proposicional.
o
a
o
Ejercicio 1.– Determinar todas las subf´rmulas de las f´rmulas
o
o
((¬p ∨ q) ∧ (q → r))

y

(¬(¬(¬p ∨ p) ∨ p) ∨ q)

Ejercicio 2.– Eliminar todos los par´ntesis posibles de las siguientes f´rmulas:
e
o
(((p → q) ∨ r) → (p ∧ ¬p))
((p → (q∧ r)) → (¬¬p ∧ q))
(((p ∨ q) ∨ (r ∨ s)) → ¬p)

(¬(p ∧ q) → (q ∧ r))
¬((p ∧ p) ∧ (p ∧ p))
(p → ((q ↔ s) → p))

Ejercicio 3.– Escribir con par´ntesis las siguientes f´rmulas:
e
o
p→q ↔r∨s
p ∨ q ↔ ¬r ∨ s

q → ¬p ∨ r ∨ s
q ∧ ¬q ∨ p → r

Ejercicio 4.– Dada una f´rmula proposicional A, sean s(A) el n´mero de estancias de variables
o
u
proposicionales en A y b(A) el n´mero de estanciasde conectivas binarias en A. Prueba que
u
para toda f´rmula A se verifica que s(A) = b(A) + 1.
o
Ejercicio 5.– Prueba que existe una unica funci´n L que a cada f´rmula proposicional, A, le
´
o
o
asocia un n´mero natural, L(A), como sigue:
u
L(p) = 1 si p ∈ V P .
L(¬A) = L(A) + 1.
L((A B)) = L(A) + L(B) + 3, si

es cualquier conectiva binaria.

¿Qu´ informaci´n nos proporciona L(A)sobre la f´rmula A?
e
o
o
Ejercicio 6.– Sea | una nueva conectiva binaria (barra de Sheffer), cuya funci´n de verdad
o
viene dada por
H| (i, j) = 1 ⇐⇒ i = 0 o bien, j = 0
Sea ↓ una nueva conectiva binaria (negaci´n conjunta) cuya funci´n de verdad viene dada por
o
o
H↓ (i, j) = 1

⇐⇒

i=j=0

1. Expresar las conectivas | y ↓ en funci´n de ¬ y ∨.
o
2. Expresar las conectivas ¬ y ∨,primero utilizando s´lo la conectiva | y luego utilizando
o
s´lo la conectiva ↓.
o
1

Ejercicio 7.– Para cada f´rmula, determina todos sus modelos (esto es, las valoraciones de
o
verdad que hagan que el valor de verdad de la f´rmula sea 1).
o
p → (q → r ∧ q)
(p ↔ q) ∧ (p → ¬q) ∧ p

q → (p ∧ ¬p) → r
(p ∧ r) ∨ (¬p ∧ q) → ¬q

¿Cu´les de las anteriores f´rmulas son satisfactibles?¿Cu´les son tautolog´
a
o
a
ıas?
Ejercicio 8.– Decide razonadamente si los siguientes enunciados son verdaderos o falsos.
1. Si F y G son f´rmulas consistentes, entonces {F, G} es consistente.
o
2. Si F es una tautolog´ y G es consistente, entonces {F, G} es consistente.
ıa
3. Si G es una contradicci´n, entonces F → G → F es una tautolog´
o
ıa.
4. Si F es satisfactible, todas sussubf´rmulas tambi´n lo son.
o
e
5. F es satisfactible si, y s´lo si, todas sus consecuencias l´gicas tambi´n lo son.
o
o
e
Ejercicio 9.– En cada caso, prop´n ejemplos de f´rmulas F y G tales que:
o
o
1. ¬F → G es una contradicci´n.
o
2. F y F → G son satisfactibles, pero G es una contradicci´n.
o
3. F |= G y F |= ¬G.
4. F |= G y F |= ¬G.
Ejercicio 10.– Expresar mediante f´rmulasproposicionales las siguientes afimaciones. En cada
o
caso ind´
ıquese el significado que se asigna a las variables proposicionales (p, q, etc.) utilizadas.
1. Si el sol brilla hoy, entonces no brillar´ ma˜ana.
a
n
2. O Roberto tiene celos de Chari o no est´ de buen humor hoy.
a
3. Cuando la presi´n atmosf´rica baja, entonces llueve o nieva.
o
e
4. Si has le´ los apuntes y has hecho los ejercicios,est´s preparado para el examen. En
ıdo
a
caso contrario, tienes un problema.
5. No habr´ cura para el c´ncer salvo que se determine su causa y se encuentre un nuevo
a
a
medicamento.
6. Si Pablo se encontr´ con Chari ayer, entonces tomaron caf´ juntos o pasearon por el
o
e
parque.
2

7. Juan duerme muchas horas y muy profundamente.
8. Mi hermana tiene un gato blanco y negro.Ejercicio 11.– Decide razonadamente si los siguientes enunciados son verdaderos o falsos.
1. Si {F, G, H} es inconsistente, entonces F |= ¬G ∨ ¬H.
2. {F, G} es consistente si y s´lo si {¬F, ¬G} es inconsistente.
o
3. Si U es un conjunto de f´rmulas tal que U |= F , entonces U |= ¬F .
o
4. Si U es un conjunto de f´rmulas tal que U |= F , entonces U |= ¬F .
o
Ejercicio 12.– Determinar cu´les...