Relación 2

Relación 2: 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:

(D -> C)

-C

||- -D

Pablo José Gerlach Mena

He utilizado los símbolos -> (condicional), - (negación) y ||- (por tanto).

(Observación: Sería mas conveniente en mi opinión usar el símbolo '¬' para la negación, aunque simplemente es una cuestión de notación) Emilio Martínez Rivero

(Yo opino igual, más que nada para seguir manteniendo la notación vista en clase, al igual que opino que sería conveniente usar '|=' para Por tanto, notación también vista en clase, más que nada para que no haya mucha diferencia entre la clase y los ejercicios que resolvemos por aquí) José Martín Delgado

(¿La primera linea no podría ser D <-> C ? )

---

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:

((V v P) -> (R & F))

((F v N) -> A)

||- (V -> A)

Pablo José Gerlach Mena

He utilizado los símbolos -> (condicional), - (negación), v (disyunción), & (conjunción) y ||- (por tanto).

---

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:

((T & P) -> -L)

T

||- (L -> -P)

Pablo José Gerlach Mena

He utilizado los símbolos -> (condicional), - (negación), v (disyunción), & (conjunción) y ||- (por tanto).

---

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:

((A & -B) -> M)

(A v B)

||- (-B -> M)

Pablo José Gerlach Mena

He utilizado los símbolos -> (condicional), - (negación), v (disyunción), & (conjunción) y ||- (por tanto).

Comentario: La formalización de la primera frase no es correcta.

---

Solucion2:

(A->(M<->(¬B))

(A & ¬B)v(¬A & B)

|=(¬B->M)

Emilio Martinez Rivero

---

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:

1) Vamos a definir la función nv(F) como:

nv(F) = 1 ...................... si F es atómica

nv(F) = nv(G) ................ si F es -G

nv(F) = nv(G) + nv(H) ..... si F es (G * H)

Pablo José Gerlach Mena

He utilizado los símbolos - (negación) y * (operación binaria).

2) Vamos a definir la función prof(F) como:

prof(F) = 0 ...................................... si F es atómica

prof(F) = 1 + prof(G) ........................ si F es -G

prof(F) = 1 + max{prof(G),prof(H)} ..... si F es (G * H)

Pablo José Gerlach Mena

He utilizado los símbolos - (negación) y * (operación binaria).

Demostración: (nv(F)≤2^prof(F))

      Caso base: (F atómico)

nv(F) = 1 y 2^prof(F)= 2^0 = 1 ==> nv(F)≤ 2^prof(F) [De hecho es igual]

       Hipótesis de inducción: Supongamos que nv(F)≤ 2^prof(F) y nv(G)≤ 2^prof(G).

Entonces 1) nv(¬F)= nv(F) y 2^(prof(¬F)) = 2^(1+prof(F))=2*2^(prof(F))

nv(F) ≤ 2^(prof(F) por H.I. ===> nv(¬F)=nv(F) ≤2*2^(prof(F)) = 2^(prof(¬F)

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

    Tenemos ahora dos posibles casos:

Caso1: prof(F)≤prof(G):: H1

       Entonces tenemos que nv(F)≤2^prof(F) por H.I ==> nv(F)≤2^prof(G) (por H1)

nv(G)≤2^prof(G) por H.I

Luego nv(F*G) = nv(G)+nv(F)≤2*2^(prof(G))=2^(1+max{prof(G),prof(F)}) = 2^prof(G*F) Por tanto nv(F*G)≤2^prof(F*G)

Caso2: Es análogo al Caso1.

QED.

Emilio Martínez Rivero

---

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:

Creo que sí. Bastaría tomar un conjunto S = {F_1, F_2, F_3} de modo que dos de ellas fueran insatisfacibles y la restante fuera una tautología. Obtendríamos entonces los siguientes subconjuntos:

{F_1, F_2, F_3} (no consistente por ser F_1 y F_2 insatisfacibles)

{F_1, F_2} (no consistente por ser F_1 y F_2 insatisfacibles)

{F_1, F_3} (no consistente por ser F_1 insatisfacible)

{F_2, F_3} (no consistente por ser F_2 insatisfacible)

{F_1} (no consistente por ser F_1 insatisfacible)

{F_2} (no consistente por ser F_2 insatisfacible)

{F_3} (consistente por ser F_3 una tautología)

Pablo José Gerlach Mena

Comentario: ¿El conjunto vacío es consistente?

---

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:

Construyamos el siguiente esquema de tabla de verdad donde el 0 representa que la fórmula no es satisfacible, y el 1 que sí es satisfacible:

F G | F -> G

0 0 | 0 1* 0 (I1)

0 1 | 0 1* 1 (I2)

1 0 | 1 0* 0 (I3)

1 1 | 1 1* 1 (I4)

Mediante * hemos denotado al resultado de la fórmula (F -> G). Como partimos de que (F -> G) es satisfacible, nos fijamos únicamente en los modelos I1, I2 e I4. Sin embargo, al decirnos que F es satisfacible, debemos eliminar los modelos I1 e I2, ya que en ellos F no es satisfacible. Por lo tanto, obtenemos que el modelo restante para (F -> G) y F satisfacibles es el modelo I4 en el cual G también es satisfacible. Por lo tanto, la respuesta a la pregunta es afirmativa.

Pablo José Gerlach Mena

Comentario: Mediante el razonamiento anterior se puede concluir que todo modelo de F → G y F, también es modelo de G, pero no se puede afirmar que la respuesta sea afirmativa.

Solución2:

Contraejemplo:

F=p

Q=q&-q

F->Q = p->(q&-q)

F es satsfacible si p=1, F->Q es satisfacible si p=0 pero Q es insatisfacible.

Manuel Soriano Trigueros

Comentario: La fórmula F -> Q no 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:

1) Si F es una fórmula satisfacible, entonces todas las subfórmulas de F son satisfacibles.

La respuesta es falsa. Consideremos la fórmula F dada mediante:

(p v (q & -q)) la cual es satisfacible (tomar por ejemplo el modelo (p,q)=(1,1))

Tenemos que el conjunto de subfórmulas de F viene dado a través de:

Subf(F) = { (p v (q & -q)), p, (q & -q), q, -q}

Observemos que la subfórmula (q & -q) no es satisfacible, con lo cual ya hemos encontrado un contraejemplo válido.

Pablo José Gerlach Mena

He utilizado los símbolos - (negación), v (disyunción) y & (conjunción)

2) Existen fórmulas válidas tales que todas sus subfórmulas son válidas.

Creo que la respuesta es falsa, ya que para todo fórmula F, el conjunto de subfórmulas de F contendrá a las fórmulas atómicas, las cuales nunca son válidas.

Pablo José Gerlach Mena