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 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 (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 (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 (A ∧ ¬B) -> M. 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

   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

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.

---

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

 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.

---

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

  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

  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

1. Por reduccion al absurdo, supongamos que S v T es consistente.

 Significa que existe I modelo para todas sus formulas, pero el subconjunto de formulas T es inconsistent, por lo que no tiene modelo. Contradccion.

2. S ∩ T puede ser vacio cual es consistente.

  S ∩ T si no es vacio es S o un subconjunto suyo el cual es consistente por hipotesis.

---

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

 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 conjuncion 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 interpretacion I(p_t)= 1 para todos los t distintos de k y I(p_k) = 0.
 

---

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.