El Problema de Decisión

El Problema de Decisión

Una de las formulaciones más influyentes de lo que llegaría a llamarse Problema de Decisión —Entscheidungsproblem en el original alemán— aparece en la obra publicada en 1928 por David Hilbert y Wilhelm Ackermann, Grundzüge der theoretischen Logik o Principios de Lógica Teórica, que recoge algunos de los descubrimientos lógicos más importantes acumulados hasta principios del siglo XX.

El término había aparecido ya en los trabajos de Heinrich Behmann durante los primeros años de la década de 1920, pero fue la formulación de Hilbert y Ackermann la que convirtió el problema en uno de los objetivos centrales de la Lógica Matemática.

El problema en cuestión puede resumirse de la siguiente manera:

Dada una fórmula de la Lógica de Primer Orden, nos preguntamos si existe un método efectivo que permita decidir en un número finito de pasos si dicha fórmula es o no lógicamente válida. El procedimiento debe terminar siempre y ofrecer una respuesta: «sí» o «no».

El problema puede formularse también sintácticamente: determinar si una fórmula es demostrable mediante los axiomas y reglas de un cálculo lógico. El Teorema de Completitud de Gödel establecería posteriormente que, para la Lógica de Primer Orden, una fórmula es válida si y solo si es demostrable. Por tanto, en un cálculo completo, las formulaciones semántica y sintáctica del problema coinciden.

Nótese que un procedimiento de decisión no tiene por qué ofrecer una demostración cuando responde afirmativamente. Lo imprescindible es que exista un algoritmo que, ante cualquier fórmula, termine y determine correctamente cuál de las dos respuestas corresponde.

Hilbert y Ackermann presentaron el Problema de Decisión como uno de los problemas principales de toda la Lógica Matemática.

Decidibilidad en la Lógica Proposicional

Centrémonos por un momento no tanto en el aspecto sintáctico —si una fórmula es o no demostrable a partir de los axiomas— como en el semántico, esto es, si una fórmula puede ser verdadera bajo cierta interpretación. Esto nos lleva al concepto de satisfacibilidad: una fórmula es satisfacible si existe al menos una interpretación bajo la cual es verdadera.

En la serie dedicada a la Lógica Matemática explicamos que las fórmulas de la Lógica Proposicional podían ser contradicciones, siempre falsas —como \(P\land\neg P\)—, o tautologías, siempre verdaderas —como \(P\lor\neg P\)—. Entre ambos extremos se encuentran las fórmulas contingentes, verdaderas bajo algunas interpretaciones y falsas bajo otras.

Tanto las tautologías como las fórmulas contingentes que resultan verdaderas bajo alguna interpretación son satisfacibles. Solo las contradicciones son insatisfacibles.

La Lógica Proposicional es decidible: es posible responder mediante un procedimiento finito a la pregunta de si una fórmula es satisfacible, válida o contradictoria. Uno de los métodos más elementales para hacerlo es la Tabla de Verdad.

Cada una de las variables \(A\), \(B\) y \(C\) de la fórmula puede tomar uno de dos valores de verdad: verdadero, representado por \(1\), o falso, representado por \(0\). Es posible comprobar el valor de verdad de la fórmula completa resolviendo la tabla para cada combinación posible de valores de las variables.

Si la fórmula es verdadera en al menos una fila, es satisfacible. Si resulta verdadera en todas las filas, es una tautología; si resulta falsa en todas, es una contradicción. Si, como en el ejemplo, solo una de las interpretaciones la hace falsa, la fórmula es satisfacible y contingente, pero no es una tautología.

Decidibilidad y el Problema de Decisión

Nos hacemos entonces la siguiente pregunta: ¿es decidible la Lógica de Primer Orden del mismo modo que lo es la Lógica Proposicional? ¿Podemos hallar un método que determine para cualquier fórmula si es válida o satisfacible?

Ambas preguntas están estrechamente relacionadas. Una fórmula \(A\) es válida cuando es verdadera bajo toda interpretación posible. Por tanto, \(A\) es válida si y solo si su negación \(\neg A\) no es satisfacible. Un procedimiento que decidiera la satisfacibilidad permitiría decidir también la validez, y viceversa.

En la Lógica de Predicados o de Primer Orden, la interpretación semántica es más compleja que en la Lógica Proposicional. Debemos seleccionar un dominio de objetos y asignar a cada símbolo de predicado una propiedad o relación definida sobre ese dominio.

Si, por ejemplo, interpretamos una fórmula \(P(x)\) como «\(x\) es un número primo» y tomamos los números naturales como dominio de referencia, el predicado \(P\) queda interpretado como el conjunto de todos los números primos. Cada instancia recibe entonces un valor de verdad:

$$P^{T}(1)=0$$

$$P^{T}(2)=1$$

$$P^{T}(3)=1$$

$$P^{T}(4)=0$$

$$P^{T}(5)=1$$

$$\vdots$$

La fórmula abierta \(P(x)\) no posee por sí sola un único valor de verdad: este depende del valor asignado a \(x\). Una fórmula cerrada como \(\exists x\,P(x)\) sí expresa una proposición verdadera o falsa dentro de una interpretación completa.

Satisfacibilidad y cardinalidad

No siempre es necesario comprobar interpretación por interpretación para confirmar que una fórmula es satisfacible. Existen fórmulas como \(\Psi(x)\lor\neg\Psi(x)\) que son verdaderas para cualquier interpretación del predicado \(\Psi\), cualquier dominio y cualquier valor asignado a \(x\).

Pero pensemos en una fórmula como esta:

$$\exists x\exists y\left[\Psi(x)\land\neg\Psi(y)\right]$$

¿Hay algún caso en el que esta fórmula sea verdadera? La respuesta depende de la interpretación. En un dominio de un único objeto, \(x\) e \(y\) necesariamente designarían el mismo individuo. La fórmula se reduciría entonces a una expresión de la forma \(\Psi(x)\land\neg\Psi(x)\), que es contradictoria.

En un dominio de dos o más objetos, en cambio, la fórmula es satisfacible: basta con interpretar \(\Psi\) de manera que algún objeto satisfaga el predicado y algún otro no lo satisfaga. La fórmula no es verdadera bajo todas las interpretaciones de esos dominios, pero sí existe al menos una interpretación que la hace verdadera.

Otras fórmulas imponen condiciones diferentes sobre el número de objetos del dominio. Por ejemplo:

$$\forall x\forall y\left[x=y\right]$$

solo puede ser verdadera en un dominio formado por un único individuo. En cambio:

$$\exists x\exists y\left[x\neq y\right]$$

exige que el dominio contenga al menos dos objetos.

Hilbert y Ackermann destacaron así la íntima relación entre la satisfacibilidad de una fórmula y la cardinalidad del dominio bajo el que se interpreta. Una fórmula puede poseer modelos de ciertas cardinalidades y carecer de ellos en otras.

Si una fórmula posee un modelo cuyo dominio tiene una determinada cardinalidad, podemos transportar la interpretación a cualquier otro dominio de la misma cardinalidad mediante una correspondencia uno a uno. Pero esto no significa que la satisfacibilidad quede determinada únicamente por un número: es necesario especificar también cómo se interpretan los predicados, las relaciones y las funciones del lenguaje.

Tablas de verdad

Ahora pensemos en una fórmula como \(\exists x\left[Q(x)\right]\), interpretada en un dominio de tres elementos: \(\{\alpha,\beta,\gamma\}\). Para determinar su valor de verdad debemos considerar las tres instancias \(Q(\alpha)\), \(Q(\beta)\) y \(Q(\gamma)\). Podemos transformar la fórmula original en una disyunción equivalente de la Lógica Proposicional:

$$Q_{\alpha}\lor Q_{\beta}\lor Q_{\gamma}$$

En el caso de \(\forall x\left[Q(x)\right]\), su equivalente proposicional sería una conjunción:

$$Q_{\alpha}\land Q_{\beta}\land Q_{\gamma}$$

Esta operación es viable para fórmulas con más variables y para dominios con cualquier número finito de elementos. Si aparecen predicados de varias variables, debemos considerar todas las posibles combinaciones de elementos del dominio.

Una vez realizada esta expansión finita, podemos aplicar una Tabla de Verdad. Por tanto, es posible decidir si una fórmula posee un modelo de una cardinalidad finita previamente fijada.

Esto resuelve determinados casos particulares, pero no todavía el Problema de Decisión general. Para resolverlo necesitaríamos un procedimiento que determinara la satisfacibilidad sin conocer de antemano el tamaño de un posible modelo.

El infinito en el Problema de Decisión

Podríamos examinar sucesivamente dominios de uno, dos, tres y más elementos, aplicando en cada caso el procedimiento anterior. Si la fórmula posee algún modelo finito, terminaríamos encontrándolo.

Sin embargo, este procedimiento no siempre termina. Si la fórmula no es satisfacible, podríamos continuar indefinidamente aumentando el tamaño del dominio sin alcanzar nunca una respuesta negativa. Tampoco terminaría si la fórmula solo tuviera modelos infinitos.

No es cierto, además, que toda fórmula satisfacible en un dominio finito sea satisfacible en todos los dominios mayores. La fórmula \(\forall x\forall y\left[x=y\right]\), por ejemplo, posee un modelo de un elemento, pero ninguno de dos o más elementos.

Existen también fórmulas que solo pueden ser satisfechas en dominios infinitos. He aquí un ejemplo:

$$\left(\forall x\exists y\,F(x,y)\right)\land\left(\forall x\,\neg F(x,x)\right)\land\left(\forall x\forall y\forall z\left[(F(x,y)\land F(y,z))\rightarrow F(x,z)\right]\right)$$

Esta fórmula es satisfecha, por ejemplo, si interpretamos \(F(x,y)\) como «\(x\) es menor que \(y\)» en el dominio de los números naturales. La primera parte afirma que para todo objeto existe otro relacionado con él; la segunda establece que ningún objeto está relacionado consigo mismo; y la tercera impone la transitividad de la relación.

La fórmula no puede satisfacerse en ningún dominio finito. Si hubiera un número finito de objetos y cada uno tuviera un sucesor según \(F\), terminaríamos repitiendo alguno de ellos. La transitividad produciría entonces un ciclo y, finalmente, una relación de la forma \(F(x,x)\), prohibida por la segunda condición.

Por tanto, las Tablas de Verdad generalizadas a dominios finitos no bastan para decidir la Lógica de Primer Orden. La existencia de modelos exclusivamente infinitos no demuestra por sí sola que el Problema de Decisión sea insoluble, pero sí muestra por qué el método utilizado para la Lógica Proposicional no puede extenderse directamente al caso general.

Conclusión

En 1928, el Problema de Decisión se encontraba irresuelto. Se conocían métodos capaces de decidir fragmentos particulares de la Lógica de Primer Orden, pero no se sabía si existía un procedimiento general que funcionara para cualquier fórmula. Behmann, Bernays, Schönfinkel, Ackermann y otros autores obtuvieron resultados positivos para determinadas clases de expresiones, sin alcanzar una solución completa.

La respuesta definitiva sería negativa. En 1936 Alonzo Church demostró que no existe un algoritmo general para determinar la demostrabilidad de todas las fórmulas de la Lógica de Primer Orden. Ese mismo año, Alan Turing llegó de manera independiente a un resultado equivalente mediante su análisis de las máquinas computadoras.

Los teoremas de incompletitud de Gödel, que estudiaremos en los próximos artículos, no deben confundirse con esta insolubilidad. El Problema de Decisión pregunta por la existencia de un único algoritmo capaz de decidir todas las fórmulas de la Lógica de Primer Orden. La incompletitud concierne, en cambio, a las limitaciones demostrativas de determinados sistemas formales suficientemente potentes para expresar la Aritmética.

Antes de que Church y Turing cerraran negativamente el Problema de Decisión, los resultados de Gödel ya habían transformado profundamente las expectativas del Programa de Hilbert.

Lecturas recomendadas

– Hilbert, D. y Ackermann, W. (1928). Grundzüge der theoretischen Logik.

– Behmann, H. (1922). Beiträge zur Algebra der Logik, insbesondere zum Entscheidungsproblem.

– Church, A. (1936). «A Note on the Entscheidungsproblem».

– Turing, A. M. (1936). «On Computable Numbers, with an Application to the Entscheidungsproblem».