3.7.3 Compleción y decidibilidad

3.7.3. Compleción y decidibilidad

Hemos dicho que un sistema deductivo completo puede demostrar cualquier conclusión que esté implicada por las premisas, es decir, tal que ₀C. Pero ¿qué ocurre si ₀ /C?

En la teoría de la computación se define un problema de decisión como aquél que tiene dos respuestas posibles: «sí» o «no» . Cualquier problema puede reducirse a un conjunto de problemas de decisión. Se dice que un problema de decisión es decidible si existe un algoritmo (es decir, un procedimiento que acabe en un tiempo finito) que lo resuelva.

Un sistema deductivo es decidible si ante la consulta ¿₀C? termina en un tiempo finito respondiendo «sí» o «no» .

Pero las cuestiones de compleción y decidibilidad se pueden plantear en términos más generales: dados ₀ y C,

el problema de la compleción es: si ₀C, ¿existe algún algoritmo que demuestre C?;
el problema de la decidibilidad es: ¿existe algún algoritmo que responda «sí» en el caso de que ₀C y «no» en el caso de que ₀ /C?

En lógica de proposiciones ambas cuestiones tienen una respuesta positiva (algoritmos obvios son los basados en las tablas de verdad).

DIT-ETSIT-UPM

Portada