El Problema de Decisión
David Baños Abril
En el artículo que dedicamos a la Teoría de la Prueba, Hilbert se preguntaba (y respondía de forma inconclusa) acerca de la consistencia de los sistemas lógicos formales, es decir, si es posible asegurarnos que no exista en ellos contradicción alguna. Este artículo lo dedicamos al Problema de Decisión, otra de las propiedades de los sistemas lógicos.
El Problema de Decisión
La primer desarrollo extenso del que llegaría a llamarse Problema de la Decisión (Entscheidungsproblem en el original alemán) la encontramos en la obra publicada en 1928 por Hilbert y Wilhelm Ackermann Grundzüge der theoretischen Logik o Principios de Lógica Matemática, la cual acoge los descubrimientos lógicos más importantes acumulados hasta principios del siglo XX.
El problema en cuestión aparece en la citada obra formulado tal que así:
-¿Es posible determinar si un enunciado dado perteneciente a un campo de conocimiento es o no consecuencia de los axiomas?-
-D. Hilbert y W. Ackermann. Grundzüge der theoretischen Logik (1928)
Dado una afirmación, como puede ser «el número de números primos es infinito» dentro de la Teoría de Números, nos preguntamos si es posible asentarla en los axiomas de una teoría, es decir, si es o no demostrable. Notar que lo que demanda el problema es decidirse por un «sí» o un «no», sin exigir la demostración en caso afirmativo.
Hilbert llegaría a afirmar que el Problema de Decisión es el principal problema a resolver de toda la Lógica Matemática.
Decibilidad 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 una cierta interpretación. Esto nos lleva al concepto de satisfacibilidad; una fórmula es satisfactible si existe una interpretación en que dicha fórmula sea cierta.
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 por ejemplo P ∧ ¬P), también tautológicas o siempre verdaderas (P ∨ ¬P) y por último satisfactibles, esto es, verdaderas en al menos alguna de las interpretaciones de las variables.
Las fórmulas de Lógica Proposicional son decidibles, esto es, es posible responder a la pregunta de si una fórmula es o no satisfactible. Existe un método semántico para poder decantarnos por un «no» o por un «sí» para cualquier fórmula de dicha lógica. Y este método es la Tabla de Verdad.
Cada una de las variables A, B y C de esta fórmula puede tomar un valor de verdad (verdero/1 o falso/0). Es posible comprobar el valor de verdad de la fórmula al completo resolviendo la tabla en cada una de las combinaciones de valores de verdad de las variables (cada una de las filas). Comprobamos que la fórmula es satisfactible pues solo una de las interpretaciones se resuelve como falsa.
Decibilidad y el Problema de Decisión
Nos hacemos la pregunta ¿Es decidible la Lógica de Primer Orden al igual que es la Lógica de Proposiciones? ¿Podemos hallar un método para resolver cuando una fórmula es satisfactible?
En la Lógica de Predicados o de Primer Orden, la resolución de la veracidad de una fórmula pasaba también por interpretar las variables, pero de forma algo más compleja. La Lógica de Primer Orden se caracteriza porque las proposiciones tienen asociadas una o varias variables. La interpretación semántica implica asignar un valor de verdad a cada instancia de la variable según el universo de referencia. Explicamos esto mucho más en detalle en el artículo dedicado en la serie de Lógica Matemática:
Si por ejemplo, una fórmula como P(x) la interpretamos como «x es un número primo» y tomamos a los números naturales como el universo de referencia, la interpretación pasa por asignar a cada caso un valor de verdad.
Satisfacibilidad y cardinalidad
No siempre es necesario comprobar interpretación por interpretación para confirmar que una fórmula sea satisfactible o no. Existen fórmulas como Ψ(x) ∨ ¬Ψ(x) que son ciertas para cualquier universo de interpretación, independientemente de si Ψ es «ser un número primo» o «ser un mamífero», así como del universo de referencia.
Pero pensemos en una fórmula como esta:
¿Hay algún caso en que esta fórmula sea verdadera? Esto realmente dependería de como se interprete. En un universo de un solo objeto la fórmula quedaría como ∃x[Ψ(x) ∧ ¬Ψ(x)] lo cual es una evidente contradicción sea lo que sea el predicado Ψ. No se cumple bajo ningún caso. En un universo de más de un objeto sí sería una fórmula satisfactible, dado que existe el caso en que x e y sean objetivos distintos y pueda ser verdadera. La siguiente fórmula
sería una verdad satisfactible en dominios de más de un objeto, pero será cierta en cualquier caso para dominios de un único elemento.
Hilbert y Ackermann destacan pues la íntima relación entre la satisfacibilidad de una fórmula y la cardinalidad del universo de referencia bajo el que se interprete. Más importante aún: dado que una fórmula satisfactible en un universo será igualmente satisfactible en otro universo cuya cardinalidad sea la misma, la anunciación de la satisfacibilidad de una fórmula es equivalente a anunciar el número de individuos que conforma el universo de interpretación.
Tablas de verdad
En el caso de ∀x[Q(x)] su equivalente proposicional sería una conjunción:
Esta operación es viable igualmente para números mayores de variables y también para universos de cualquier cantidad de elementos. Lo que nos permite esto es poder aplicar una Tabla de Verdad, y por tanto, la resolución de la satisfacibilidad de dicha fórmula. Para estos casos, las fórmulas de Primer Orden son decidibles.
El infinito en el Problema de Decisión
Cuando el universo en cuestión es infinito nos es imposible aplicar esta solución en el momento en que no sería posible expresar la fórmula en un número finito de símbolos. Pero he aquí que es posible salvar esto sabiendo que, cuando una fórmula es satisfactible en un universo de finitos elementos, es satisfactible en todos los universos de mayor cardinalidad, hasta el infinito. Podemos comprobar esto facilmente sabiendo que aumentar la cardinalidad no elimina las combinaciones de valores de verdad que satisfacen la fórmula.
Entonces… ¿Podemos concluir que la Lógica de Primer Orden es decible y solucionar así el Problema de Decisión? La respuesta es negativa.
Y es que podrían existir fórmulas que solo fuesen ser satisfactibles en un universo de infinitos elementos. He aquí un ejemplo:
Esta fórmula es satisfecha, por ejemplo, si interpretamos F(x,y) como «x es menor que y» en un universo de infinitos elementos. Dado que la fórmula dispone que siempre existe un elemento mayor a uno dado, no sería satisfactible en ningún universo de finitos elementos.
Conclusión
Para 1928, el Problema de Decisión se encontraba irresuelto. No existía un método general para resolver la decibilidad de la Lógica de Primer Orden. Hilbert y su escuela se afanaron en encontrar un método pero durante los años siguientes los resultados fueron siempre parciales. El fallo definitivo llegaría varios años después de la mano de un joven matemático y criptógrafo todavía poco conocido para ese momento: Alan Turing.
Lecturas Recomendadas
– Hilbert, D. (1900b) From mathematical problems.
– Hilbert, D. (1908) On the infinite.
– Hilbert, D. (1918) The axiomatic thought.
