Lógica de predicados - Intente demostrar primero la satisfabilidad o insatisfabilidad

Question

Durante mi curso de lógica me encontré con este problema:

Determine si el siguiente conjunto de sentencias es satisfacible o no. En caso negativo, utilice la deducción natural para demostrar la contradicción.

S = {x(R(x, x) yQ(x, y)), ¬x((yR(x, y)) Q(x, x))}

Desde el punto de vista teórico, sabemos que un conjunto de sentencias es satisfacible si existe una interpretación que sea un modelo de todas las sentencias del conjunto.

Ahora bien, no tengo mucha experiencia con la lógica de predicados, y me lleva bastante tiempo dar con una interpretación que satisfaga todas las sentencias, y me he dado cuenta de que pierdo demasiado tiempo intentando dar con una interpretación, a pesar de que es totalmente posible que el conjunto no sea satisfactible.

Por ejemplo, yo también pasé mucho tiempo intentando encontrar una interpretación para el siguiente conjunto de frases:

S = {xy(R(x, y) P(y)), zP(z), x(P(x) y¬R(y, x))}

Por cierto, ambos conjuntos no son satisfacibles, lo que puede demostrarse encontrando una contradicción.

¿Cómo resolvería este problema? ¿Intentarías primero hacer una interpretación, y si eso no funciona, intentarías demostrar la contradicción por deducción natural, o viceversa?

¿Existe alguna "sensación interna" cuando ven estos problemas por primera vez y se dicen a sí mismos "¡Ah, esto debe ser (in)satisfactible!"?

Answer 1

Lo que probablemente haría primero es pensar en cómo tendría que comportarse una interpretación de sus frases. Si tienes suerte, eso podría llevarte a una contradicción (tras lo cual puedes buscar una prueba sintáctica de contradicción en deducción natural si lo deseas). Si no te lleva a la contradicción, entonces puedes empezar a pensar qué elementos tienen que existir para que la interpretación funcione e intentar construir un pequeño ejemplo.

A modo de ejemplo, pensemos en tu primera serie de frases, $\{\exists x (R(x, x) \wedge \forall y Q(x, y)), \neg \exists x ((\exists y R(x, y)) \wedge Q(x, x))\}$ .

En una interpretación de ese conjunto de frases, la primera frase debe ser verdadera. Es una frase existencial, así que demos un nombre a lo que dice que existe. Para no chocar con otras variables, llamaré a esta cosa $a$ . Así que sabemos que $R(a, a)$ y sabemos que $\forall y Q(a, y)$ . Hasta ahora lo único que sabemos que podemos enchufar para $y$ hay $a$ de nuevo; quizá más adelante necesitemos hacer algo más, pero por ahora tomemos nota de que tenemos $Q(a, a)$ .

Ahora veamos la segunda frase de tu conjunto. Dice que cierto tipo de objeto no puede existir, en concreto, no hay $x$ tal que $Q(x, x)$ y para algunos $y$ $R(x, y)$ . ¡Oh, pero mira lo que ya sabemos! Ya sabemos que $R(a, a)$ et $Q(a, a)$ . En particular, sabemos que $Q(a, a)$ et $\exists y R(a, y)$ . Así que $a$ es el tipo de elemento que la segunda frase dice que no debería existir.

Hemos demostrado que si la primera frase es cierta, la segunda no puede serlo. Ahora que sabemos que el conjunto es inconsistente, podemos buscar una demostración formal en deducción natural, si nos apetece.

En un caso en el que el conjunto sea consistente, el mismo tipo de pensamiento podría llevarnos a descubrir que podemos hacer que todas las sentencias sean verdaderas con sólo unos pocos elementos, en cuyo caso podemos escribir explícitamente una interpretación.

No hay ninguna garantía de que la elaboración de consecuencias como ésta nos lleve, en un tiempo razonable, a una contradicción o a la construcción de una interpretación (¡si la hubiera, muchas matemáticas serían mucho más fáciles de lo que son!). Aun así, creo que es una buena estrategia (y muy a menudo funcionará en ejercicios introductorios).