Resolución del razonamiento por cláusulas

Ejercicio de lógica de predicados: validez, resolución y contraejemplo mínimo

Enunciados

Premisa 1: ∃x ∀y R(x,y)

Premisa 2: ∀x (∃y R(x,y) → P(x))

Conclusión: ∀x P(x)

El objetivo es decidir si el razonamiento es correcto. Para hacerlo por resolución, añadimos la negación de la conclusión al conjunto de premisas y comprobamos si se obtiene la cláusula vacía.

Idea general del razonamiento

La primera premisa solo garantiza que existe un elemento concreto que se relaciona con todos los elementos del dominio. La segunda premisa dice que todo elemento que se relacione con alguno debe cumplir P.

Por tanto, de las premisas se puede obtener P para el elemento que aparece en la primera premisa, pero no necesariamente para todos los elementos del dominio. Esta será la causa de que el razonamiento no sea válido.

Paso a forma clausal

3.1. Premisa 1

Paso	Resultado
Fórmula inicial	∃x ∀y R(x,y)
Skolemización	El cuantificador existencial ∃x se elimina introduciendo una constante de Skolem a.
Resultado	∀y R(a,y)
Forma clausal	C1: R(a,y)

3.2. Premisa 2

Paso	Resultado
Fórmula inicial	∀x (∃y R(x,y) → P(x))
Eliminar implicación	∀x (¬∃y R(x,y) ∨ P(x))
Aplicar equivalencia de cuantificadores	∀x (∀y ¬R(x,y) ∨ P(x))
Pasar a forma universal	∀x ∀y (¬R(x,y) ∨ P(x))
Forma clausal	C2: ¬R(x,y) ∨ P(x)

3.3. Negación de la conclusión

Paso	Resultado
Conclusión	∀x P(x)
Negación de la conclusión	¬∀x P(x)
Equivalencia	∃x ¬P(x)
Skolemización	Se introduce una constante de Skolem b.
Forma clausal	C3: ¬P(b)

4. Conjunto de cláusulas

Cláusula	Fórmula	Origen
C1	R(a,y)	Premisa 1
C2	¬R(x,y) ∨ P(x)	Premisa 2
C3	¬P(b)	Negación de la conclusión

Las variables de las cláusulas están universalmente cuantificadas de forma implícita. Las constantes a y b proceden de dos Skolemizaciones distintas.

5. Resolución paso a paso

 

Cláusula troncal	Cláusula lateral
¬P(b)	¬R(x,y) ∨ P(x)   ¬R(b,y) ∨ P(b)	x sustituido por b
¬R(b,y)	R(a,y)	No se peude resolver, ya que las 2 clausulas tienen cosntantes diferentes.

 

No se puede resolver ¬R(b,y) con R(a,y) porque a y b son constantes distintas y no unifican. Por tanto, no aparece ninguna contradicción y no se obtiene la cláusula vacía.

Interpretación del resultado de la resolución

Al no obtenerse la cláusula vacía, significa que existe al menos existe un modelo en el que las premisas son verdaderas y la conclusión es falsa.

Por tanto, el razonamiento no es correcto.

Contraejemplo mínimo

Usamos un dominio con dos elementos, que es el dominio más pequeño en el que puede verse el fallo:

D = {1, 2}

Premisa 1  ∃x ∀y R(x,y)

Equivalente en dominio {1,2}: (R(1,1) ∧ R(1,2)) ∨ (R(2,1) ∧ R(2,2))

Premisa 2  ∀x (∃y R(x,y) → P(x))

Equivalente en dominio {1,2}: ((R(1,1) ∨ R(1,2)) → P(1)) ∧ ((R(2,1) ∨ R(2,2)) → P(2))

Conclusión  ∀x P(x)

Equivalente en dominio {1,2}: P(1) ∧ P(2)

Para que se de un contraejemplo debemos buscar en el dominio una interpretacion en el que las premisas son verdaderas y la conclusión es falsa.

La segunda premisa, con que los lados deben ser verdad, para que al unirse con una conjunción sea verdad.

((R(1,1) ∨ R(1,2)) → P(1)) = V

V v V -> V

((R(2,1) ∨ R(2,2)) → P(2)) = V

F v F -> F

Se cumple que es verdadera.

Para la primera premisa, alguna de las dos partes deben ser verdaderas para que sea verdad en su totalidad, ya que estan unidos sus dos pares por una disyunción:

(R(1,1) ∧ R(1,2)) ∨ (R(2,1) ∧ R(2,2))

R(1,1) y R(1,2) es verdad y  R(2,1) y R(2,2) son falsas de la 2º premisa.

Se cumple que es verdadera.

Para la conclusion, sabemos que para que sea falso al menos 1 de las partes de la conjunction debe ser falsa o las dos.

P(1) = V  y  P(2)= F ( por lo que se cumple que es falsa)

Contraejemplo obtenido: < R(1,1) = V, R(1,2) = V, R(2,1) = F, R( 2,2) = F, P(1) = V, P(2) = F, Ø>

 El razonamiento no es válido