Relación 1

Relación 1: Sintaxis y semántica de la lógica proposicional

---

Ejercicio 1. Formalizar el siguiente argumento

Siempre que un número x es divisible por 10, acaba en 0. El número x no acaba en 0. Por lo tanto, x no es divisible por 10.

Usando los símbolos D: el número es divisible por 10 y C: el número acaba en cero.

---

Solución: josrodjim2, jescammor1, inmbenber,josgarfer12,antnavcue,sarolizap,manberdel1,joslopjim4

D -> C. ¬C |= ¬D

---

Ejercicio 2. Formalizar el siguiente argumento

Si la válvula está abierta o la monitorización está preparada, entonces se envía una señal de reconocimiento y un mensaje de funcionamiento al controlador del ordenador. Si se envía un mensaje de funcionamiento al controlador del ordenador o el sistema está en estado normal, entonces se aceptan las órdenes del operador. Por lo tanto, si la válvula está abierta, entonces se aceptan las órdenes del operador.

Usando los símbolos V: La válvula está abierta, P: La monitorización está preparada, R: Envía una señal de reconocimiento, F: Envía un mensaje de funcionamiento, A: Se aceptan órdenes del operador y N: El sistema está en estado normal.

---

Solución: josrodjim2, jescammor1,josgarfer12,antnavcue,sarolizap,manberdel1

(V v P) -> (R ∧ F). (F v N) -> A. V |= A

inmbenber, joslopjim4

(V v P) -> (R ^ F), (F v N) -> A |= (V -> A)

---

Ejercicio 3. Formalizar el siguiente argumento

Cuando tanto la temperatura como la presión atmosférica permanecen contantes, no llueve. La temperatura permanece constante. Por lo tanto, en caso de que llueva, la presión atmosférica no permanece constante.

Usando los símbolos T: La temperatura permanece constante, P: La presión atmosférica permanece constante y L: Llueve

---

Solución: josrodjim2, jescammor1, inmbenber,,josgarfer12,antnavcue,sarolizap,manberdel1,joslopjim4

(T ∧ P) -> ¬L. T |= (L -> ¬P)

---

Ejercicio 4. Formalizar el siguiente argumento

En cierto experimento, cuando hemos empleado un fármaco A, el paciente ha mejorado considerablemente en el caso, y sólo en el caso, en que no se haya empleado también un fármaco B. Además, o se ha empleado el fármaco A o se ha empleado el fármaco B. En consecuencia, podemos afirmar que si no hemos empleado el fármaco B, el paciente ha mejorado considerablemente.

Usando los símbolos A: Hemos empleado el fármaco A, B: Hemos empleado el fármaco B y M: El paciente ha mejorado notablemente.

---

Solución: josrodjim2,sarolizap

(A ∧ ¬B) -> M. A v B. ¬B |= M

jescammor1

(A ∧ ¬B) -> M, (A v B) |= (¬B -> M)

inmbenber,manberdel1

A -> (M <-> ¬B), A v B |= (¬B -> M)

josgarfer12,joslopjim4 (A ∧ ¬B) <-> M, A v B-> ¬B|=M

antnavcue

A -> (M <-> ¬B) , A v B-> ¬B|=M

---

Ejercicio 5. Definir por recursión sobre fórmulas las siguientes funciones

• nv(F) que calcula el número variables proposicionales que ocurren en la fórmula F. Por ejemplo,

nv(p → p ∨ q) = 3.

• prof(F) que calcula la profundidad del árbol de análisis de la fórmula F. Por ejemplo,

prof(p → p ∨ q) = 2.

Demostrar por inducción, que para toda fórmula F,

nv(F) ≤ 2^prof(F)

---

Solución: josrodjim2, jescammor1, inmbenber,sarolizap,joslopjim4

• nv(F)= 1 si F atomica, nv(G) si F es ¬G, nv(G)+nv(H) si F es (G*H)

• prof(F)= 0 si F atomica, 1+prof(G) si F es ¬G, 1+max{prof(G),prof(H)} si F es (G*H)

• Caso base: F atomica. 1 = nv(F) <= 2^prof(F) = 2^0 = 1. Se cumple.

• Supongo que se cumple para F y G.

nv(¬F) = nv(F) <= 2^prof(F) <= 2^(1+prof(F)) = 2^prof(¬F)

nv(F*G) = nv(F) + nv(G) <= 2^prof(F) + 2^prof(G) <= 2^(1 + max{prof(F),prof(G)}) = 2^prof(F*G)

---

Ejercicio 6. ¿Existe un conjunto S de tres fórmulas tal que de todos los subconjuntos de S sólo uno es consistente?

---

Solución: josrodjim2, jescammor1

Sea S = { F1= ¬(P v ¬P), F2= P ∧ ¬P, F3= P}

F3 es sastifacible I(P) = 1.

Pero cualquiera de sus subformulas incluida ella misma, son inconsistente por construccion o usando el ejercicio 9 apartado primero.

inmbenber

Sí, basta tomar S un conjunto que tenga una fórmula satisfacible y las otras insatisfacibles, así solo el subconjunto formado por la fórmula satisfacible es consistente. Pongamos un ejemplo:

S = {F,G,H} donde F = p <-> q, G = p ^ ¬p, H = (p <-> q)^(p -> ¬q)^p. Se comprueba que F es satisfacible (un modelo es I(p)=I(q)=1) y que G y H son insatisfacibles. Se ve que de todos los subconjuntos posibles de S, el único que es consistente es S1={F}

joslopjim4

Basta tomar F=p v ¬p, G= q v ¬q, H= r v ¬r

---

Ejercicio 7. ¿Es cierto que si F → G y F son satisfacibles, entonces G es satisfacible? Si es cierto, dar una explicación. Si no es cierto, dar un contraejemplo.

---

Solución: josrodjim2, jescammor1

Si F -> G es satisfacible y F es satisfacible para el mismo modelo, entonces existe I(¬F v G) = 1, I(F)=1.

Que I(¬F v G) = 1 implica que I(¬F) = 0 o bien I(G)=1, como ya tenemos I(F) = 1. La unica posibilidad es que I(G) = 1. Por lo tanto G es satisfacible.

inmbenber, joslopjim4

G no es necesariamente satisfacible, ya que si es una contradicción (falsa en todas sus interpretaciones), existen interpretaciones para las que F->G es cierta (cuando I(F)=0). Por ejemplo, F = ¬p y G = p ^ ¬p. Al hacer su tabla de verdad, notamos que F y F->G son satisfacibles, en cambio, G es insatisfacible (es una contradicción).

Si F y F->G son safistacibles a la vez, es decir, existe una interpretación I tal que I(F)=I(F->G)=1, entonces sí tendríamos que G es satisfacible, ya que sabiendo que I(F)=I(F->G)=1, la única opción que tenemos es que I(G)=1.

---

Ejercicio 8. Demostrar o refutar las siguientes proposiciones:

1. Si F es una fórmula satisfacible, entonces todas las subfórmulas de F son satisfacibles.
2. Existen fórmulas válidas tales que todas sus subfórmulas son válidas.

---

Solución:

javdelcru, jescammor1

• 1) Falso. (p -> ¬p) -> p es satisfacible, pero la subformula p -> ¬p no lo es
• 2) Falso. Todas las formulas tienen al menos una subformula que es atómica y no es válida ya que puede ser falsa.

josrodjim2, inmbenber,joslopjim4

• 1) Falso. (P ∧ ¬P) es insatisfacible, cual es una subformula de la tautologia ¬(P ∧ ¬P).

---

Ejercicio 9. Sean S y T conjuntos de fórmulas. Demostrar o refutar las siguientes afirmaciones:

• Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
• Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.
• Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
• Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.

---

Solución: josrodjim2, inmbenber, joslopjim4

• 1. Por reducción al absurdo, supongamos que S v T es consistente.

Significa que existe I modelo para todas sus fórmulas, pero el subconjunto de formulas T es inconsistente, por lo que no tiene modelo. Contradcción.

• 2. S ∩ T puede ser vacío cual es consistente.

S ∩ T si no es vacío es S o un subconjunto suyo el cual es consistente por hipótesis.

inmbenber

• 1. Sean S={F1, F2,..., Fn} consistente y T={G1, G2,..., Gm} inconsistente. Por ser S consistente, existe I modelo de S, entonces I(F1^F2^...^Fn)=1. Como T es inconsistente, entonces no tiene ningún modelo, es decir, I(G1^G2^...^Gm)=0 para cualquier interpretación I. Se tiene entonces que (F1^...^Fn^G1^...^Gm)=(F1^...^Fn)^(G1^...^Gm). Por tanto no existe modelo para (F1^...^Fn)^(G1^...^Gm). Lo que implica que S ∪ T es inconsistente.

---

Ejercicio 10. Da un ejemplo de tres fórmulas F₁ , F₂ , y F₃ tales que F₁ ∧ F₂ ∧ F₃ sea insatisfactible y donde cualquier conjunción de todas ellas menos una sea satisfactible. Generalízalo a n fórmulas.

---

Solución:

javdelcru, josrodjim2, jescammor1, joslopjim4

F_1 = p; F_2 = q; F_3 = ¬(p ∧ q) F_1 ∧ F_2 ∧ F_3 es insatisfacible pero dos a dos si son satisfacible.

Generalizamos a n formulas F_1 = p_1, F_2=p_2 ... F_(n-1) = p_(n-1), F_n = ¬(p_1 ∧ p_2 ∧ .... ∧ p_(n-1)) Igual que en el caso de 3 formulas, la conjunción de todas en insatisfacible ya que F_n es verdadera solo si las anteriores son falsas y las conjunciones de todas menos una (k) son satisfacibles con la interpretación I(p_t)= 1 para todos los t distintos de k y I(p_k) = 0.

inmbenber

<math>F_{1}</math> = ¬p, <math>F_{2}</math> = ¬q, <math>F_{3}</math> = p v q

Generalizamos a n formulas: <math>F_{1}</math> = ¬<math>p_{1}</math>, <math>F_{2}</math> = ¬<math>p_{2}</math>,..., <math>F_{n-1}</math> = ¬<math>p_{n-1}</math>, <math>F_{n}</math> = <math>p_{1}</math> v <math>p_{2}</math> v ... v <math>p_{n-1}</math>

---

Ejercicio 11.

• Probar que la fórmula (((p → q) → p) → p) es una tautología
• Si definimos recursivamente A(0) = (p → q) y A(n+1) = (A(n) → p), ¿para qué valores de n es A es una tautología?

---

Solución: josrodjim2

• 1. Se puede escribir la formula como ¬(¬(¬P v Q) v P) v P

Aplico tabla de verdad

Para I(P)=1 y I(Q) cualquiera, se ve que siempre es verdad.

Veamos los demas casos.

I(P)=0,I(Q)=0 se tiene ¬(¬(1 v 0)) v 0 ----> ¬(¬1) v 0 ---->1 v 0 ---->1 es verdad

I(P)=0,I(Q)=1 se tiene ¬(¬(1 v 1)) v 0 ----> ¬(¬1) v 0 ---->1 v 0 ---->1 es verdad

Entonces la formula es tautologia.

• 2. Para n >= 2 A(n)=p, teniendose ¬P v P cual es tautologia.

jescammor1

• 2. Estudiando los casos básicos podemos generalizar fácilmente. Como ya se ha dicho si I(P)=1 siempre es válida de n=1 en adelante así que nos ocupamos del caso I(P)=0. En A(1) esta interpretación nos da 1->0 independientemente del valor de Q (es decir, no es tautología). Por otro lado, A(2) nos da 0->1 en la misma interpretación, lo que nos da la tautología.

Está claro que si seguimos el proceso tenemos que A(3) no es tautología (1->0), A(4) si (0->1),... Luego es tautología para los n pares.

inmbenber, joslopjim4

• 1. Haciendo su tabla de verdad tenemos que (((p → q) → p) → p) es una tautología, ya que para cualquier interpretación se tiene que I(F) = 1 con F = (((p → q) → p) → p)
• 2. A partir de su tabla de verdad, es fácil comprobar que es tautología para n par