FUNDAMENTOS DE TEORÍA DE LA COMPUTACIÓN 2025
Trabajo Práctico Nro 8
Lógica Proposicional
Ejercicio 1. Dada la siguiente información:
“Si el unicornio es mítico, entonces es inmortal, pero si no es mítico, entonces es un
mamıfero mortal. Si el unicornio es o inmortal o un mamıfero, entonces tiene un cuerno. El
unicornio es mágico sí tiene un cuerno. Simbolizar en el Cálculo de Enunciados y
responder:
I. El unicornio es mıtico?. Fundamentar.
II. El unicornio no es mítico?. Fundamentar.
III. El unicornio es mágico?. Fundamentar.
Sabiendo ahora que el unicornio es inmortal, responder:
IV. El unicornio no es mágico?. Fundamentar.
Ayuda: simbolizar como forma argumentativa y determinar si es válida o no. Ver def. 1.28, Hamilton.
Ejercicio 2. Para cada una de las siguientes argumentaciones, escribir una forma
argumentativa que se corresponda con ella y determinar si es válida o inválida.
I. Si la función f no es continua, entonces la función g no es diferenciable. g es
diferenciable. Por lo tanto, f no es continua.
II. Sí Juan ha instalado la calefacción central, entonces ha vendido su coche o ha
pedido dinero prestado al banco. Juan no ha vendido su coche ni ha pedido dinero
prestado al banco. Por lo tanto, Juan no ha instalado la calefacción central.
Ayuda: Ver def. 1.28, Hamilton.
Ejercicio 3. Una fórmula booleana es satisfactible si existe al menos una combinación de
valores de verdad (una asignación de verdadero o falso a las variables) que hace que la
fórmula sea verdadera. Dados los siguientes enunciados, determinar cuales son verdaderos
y cuáles son falsos. Justificar en cada caso.
I. Una fórmula que es una tautología es satisfactible.
II. Una fórmula que es satisfactible es una tautología.
III. Una fórmula que no es satisfactible es una contradicción.
IV. Una fórmula que es una contradicción no puede ser satisfactible.
Ayuda: Ver def. 1.5, Hamilton.
Ejercicio 4. Un conjunto de fórmulas es satisfactible si existe al menos una asignación de
valores de verdad (una interpretación) que hace que todas las fórmulas del conjunto sean
verdaderas al mismo tiempo. Determinar si los siguientes conjuntos son satisfactibles:
I. {p, (p→q), r}
Página 1 de 3
II. {p, q, (p ∧ ¬p)}
Ejercicio 5. Sean A, B fbfs que cumplen que (¬A ∨ B) es tautología. Sea C una fbf
cualquiera. Determinar, si es posible, cuáles de las siguientes fbfs son tautologías y cuales
contradicciones. Justificar las respuestas.
I. ((¬(A → B) )→ C )
II. ( C → ((¬A ) ∨ B))
III. ((¬A ) → B )
Ayuda: Ver def. 1.5, Hamilton.
Ejercicio 6 Responder y justificar:
I. ¿“(p → q)” es lógicamente equivalente a “(p ∨ ¬q)” ?
II. ¿“(p ↔ q)” es lógicamente equivalente a “((p → q) ∧ (q → p))” ?
III. ¿“(¬(p ∧ q))” es lógicamente equivalente a "(¬p ∨ ¬q)” ?
IV. ¿“(¬(p ∨ q))” es lógicamente equivalente a “(p ∧ q)” ?
Ayuda: ver def. 1.7, Hamilton.
Ejercicio 7. Sea # el operador binario definido como p#q = (p ∧ ¬q) ∨ (¬p ∧ q).
I. Probar que # es asociativo, es decir, x#(y#z) es lógicamente equivalente a (x#y)#z.
II. Probar que # es conmutativo, es decir, y#z es lógicamente equivalente a z#y.
Ejercicio 8. ¿Es cierto que en el Cálculo de Enunciados pueden escribirse dos fbfs que
tengan diferentes letras de proposición y aun así ambas fbfs sean lógicamente
equivalentes?. En caso de responder positivamente, dar un ejemplo y justificar. En caso de
responder negativamente, justificar.
Ayuda: Ver sec. 1.3, Hamilton.
Ejercicio 9. Determinar cuáles de las siguientes fbfs son lógicamente implicadas por la fbf
(A ∧ B). Fundamentar.
I. A
II. A↔B
III. ¬B → ¬A
IV. A→B
Ayuda: Ver def. 1.7, Hamilton.
Ejercicio 10. Dada la siguiente tabla de verdad, encontrar tres fbfs para cada una que las
tenga por tablas de verdad:
I. una fbf (sin restricciones de conectivos).
II. una fbf en FNC (forma normal conjuntiva)
III. una fbf en FND (forma normal disyuntiva)
Página 2 de 3
p q ?
V V F
V F V
F V V
F F F
Ayuda: Ver sec. 1.4, Hamilton.
Ejercicio 11. Explicar porque el siguiente conjunto no es un conjunto adecuado de
conectivas {∧, ∨}.
Ayuda: utilizar def. en sec. 1.5, Hamilton.
Ejercicio 12.¿Es cierto que si una fbf A es satisfactible entonces A es una tautología”.
Ayuda: utilizar la técnica de demostración por contraejemplo.
Ejercicio 13. Sea A una fbf donde aparecen solo los conectivos ∧, ∨, ¬ . Sea A* la fbf que
se obtiene a partir de A reemplazando cada ∧ por ∨ y cada ∨ por ∧. Si A es una
tautología, A* ¿también lo es? Justificar.
Ayuda: utilizar la técnica de demostración por contraejemplo.
Ejercicio 14. Demostrar utilizando la técnica del absurdo que dadas A y B fbfs
cualesquiera, siempre ocurre que si A y A → B son tautologías entonces B también lo es.
Ayuda: ver prop. 1.9, Hamilton.
Ejercicio 15. Demostrar utilizando la técnica del absurdo que (p∧¬p)→q es una tautología.
Ejercicio 16. Sea A una fbf donde aparecen solo los conectivos ∧, ¬. Sea A* la fbf que se
obtiene a partir de A reemplazando cada ∧ por ∨ y cada letra de proposición por su
negación (o sea, cada p por ¬p, cada q por ¬q, etc.). Probar, utilizando la técnica de
inducción que A* es lógicamente equivalente a ¬A.
Ayuda: ver prop 1.15, Hamilton
Ejercicio 17. Demostrar utilizando la técnica de inducción que cualquier fórmula bien
formada A que contenga sólo los conectivos {∨, ∧} puede tomar el valor F.
Ayuda: ver ejercicio resuelto en clase teórica
Página 3 de 3
