Relación 2

Relación 1(b): Representación del conocimiento 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: <math>D \to C \qquad \lnot C \to \lnot D</math>

---

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: <math> (V \vee P \to R \wedge F) \quad (F \vee N \to A) \quad \vDash V\to A</math>

---

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: <math> (T \wedge P) \to \lnot L </math>
<math> T \vDash L \to \lnot P </math>

Falta un detalle en la solución

<math> ((T \wedge P) \to \lnot L) \quad T \quad \vDash L \to \lnot P </math>

---

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: <math> (A \to (M \leftrightarrow \lnot B)) \wedge (A \vee B) \quad \vDash \lnot B \to M </math>

---

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)

---

<math> nv(F)= \begin{cases} 1 \quad si \quad F Atomica \\ nv(G) \quad si \quad F= \lnot G \\ nv(G)+nv(H) \quad si \quad F=(G*H) \end{cases} </math>

<math> prof(F)= \begin{cases} 0 \quad si \quad F Atomica \\ 1+prof(G) \quad si \quad F= \lnot G \\ 1+ max(prof(G),prof(H)) \quad si \quad F=(G*H) \end{cases} </math>

Demostración por inducción:
Se comprueba para lo que consideramos nuestro caso base, cuando F es atómica
<math> F \quad atomica \to nv(F)=1 \leqslant 2^{prof(F)}=2^0 </math>
Posteriormente suponemos que la desigualdad se da para <math>nv(F) < n+1</math>, y lo comprobamos para <math>nv(F)=n+1</math>:
<math>nv(F)=n+1 \to F=(G*H) \to n(F)=nv(G)+nv(H) \quad </math> .Pero <math>(nv(G)<n+1) \wedge (nv(H)<n+1) \to nv(F)=nv(G)+nv(H) \leqslant 2^{prof(G)}+2^{prof(H)} \leqslant _{(*)} 2^{prof(F)} </math>
(*) Se toma el máximo de ambas profundidades.

Solución:

---

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: No entiendo bien la pregunta, pero doy una "posible" respuesta:
Si <math>S=\{ F_1 , F_2,F_3 \}, \quad </math> tendríamos los subconjuntos siguientes <math>\{F_1\},\{F_2\},\{F_3\},\{F_1,F_2\},\{F_1,F_3\},\{F_2,F_3\},S</math>
Luego, si tomamos <math>F_1 \quad</math> una tautología y <math>F_2,F_3 \quad</math> contradicciones, sólo el subconjunto <math>\{F_1\} \quad</math> sería consistente.
Por ejemplo: <math>F_1=(p\wedge q)\to (p\vee r), \quad F_2=(p\vee q) \leftrightarrow \lnot (p \vee q), \quad F_3=(p\to q)\wedge \lnot (p \to q)</math>

Nota: Hay que considerar el vacío, luego tomando 3 contradicciones, se cumple.

---

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: Dado que <math>F \quad</math> es satisfacible y <math>F\to F</math> también lo es, para cada una de ellas existe una interpretación para la que sean ciertas. Luego, la tabla de verdad de todas las combinaciones posibles (para las que <math>F\to G</math> es cierta) serán:
<math> \begin{array}{|c|c||c|} F & G & F\to G \\ \hline 1&1&1\\ 0&0&1\\ 0&1&1\\ \end{array} </math> Por lo tanto, no necesariamente <math>G \quad</math> es satisfacible, pues si es una contradicción, aún existen interpretaciones para las que <math>F\to G \quad </math> es cierta.
Si <math>F\quad</math> y <math>F\to G \quad</math> deben ser satisfacibles de forma simultánea, entonces sí tendríamos que <math>G \quad</math> es satisfacible.

Como contraejemplo podemos tomar las fórmulas <math>F = \neg p</math> y <math>G = (p \wedge \neg p)</math>. Tenemos que <math>F</math> es satisfacible (<math>I(p)=0</math> es modelo de <math>F</math>) y que <math>F \to G</math> también es satisfacible (<math>I(p)=1</math> es modelo de <math>\neg p \to (p \wedge \neg p)</math>) pero <math>G</math> es insatisfacible.

---

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:

1. Damos un contraejemplo para probar que no se cumple. La fórmula <math>F =\neg (p \wedge \neg p )</math> es una tautología, es decir, toda interpretación es modelo de <math>F</math>. En cambio, su subfórmula <math>G = p \wedge \neg p</math>, por la definición de interpretación (<math>I(F)=H_{\neg}(I(G))</math>) es una contradicción, o sea, que ninguna interpretación es modelo de <math>G</math> y por lo tanto es una subfórmula de <math>F</math> insatisfacible.
2. Una fórmula válida es una tautología. Luego queda probado si encontramos algun ejemplo de tautología en la que toda subfórmula sea tautología o refutado si demostramos que no es posible. La considero falsa pues en primer lugar, las fórmulas atómicas son subfórmulas y pueden tomar interpretaciones ciertas o falsas. Y en segundo lugar, las subfórmulas más simples que pueden componer la tautología (que no sean atómicas), están formadas por la combinación de fórmulas atómicas y conectivas lógicas, las cuales no son tautologías (si formamos una fórmula empleando una única conectiva).