Sobre el teorema de la prueba de longitud en el cálculo proposicional

Question

En PC(cálculo proposicional) del sistema, en cuanto tiempo una fórmula de la prueba?

Es decir, si existe una función computable $f$ tal que para cualquier fórmula $A$ si $\vdash_{\mathrm{PC}}A$ $A$ tiene una prueba con una longitud de menos de $f(A)$.

Answer 1

Que el sistema formal de la proposición de cálculo que está en cuestión?

Hay un familiar, perfectamente bien formal deductivo, sistema de $S$ a que cada tautología, como un axioma, por lo que en este sistema, si $\vdash_S A$, entonces no es una línea de prueba de $A$!

Hay otros familiares, perfectamente bien, formal deductivo sistemas-por ejemplo, cuadros de sistemas, en el que la noción de la "longitud" de una prueba no puede ser, por supuesto sin ningún tipo de explicación (estamos hablando de la profundidad del árbol, el número de nodos, o qué?).

Pero supongamos que usted tiene en mente, por ejemplo, un estándar de Hilbert-sistema de estilo (por ejemplo, como en Mendelson texto clásico), por lo que las pruebas tienen longitudes en un sencillo sentido, y no es no trivial de la pregunta acerca de la duración de las pruebas. A continuación, echar un vistazo a cómo probar la integridad de un sistema de Kalmar del método (como en Mendelson). Este método da, en efecto, un algoritmo para la toma de una tautología $\varphi$ y la producción de una prueba de $\varphi$ -- y si nos fijamos en los detalles que usted puede, evidentemente, en principio, leer un computable límite superior para la longitud de la prueba de la complejidad de $\varphi$ (a pesar de que los datos de llegar es aburrido sucio).

Answer 2

En lógica proposicional, una fórmula es comprobable si y sólo si es una tautología, y el conjunto de tautologías es decidable. Además, para cualquier completa y efectiva de prueba del sistema, si sabemos que una fórmula es una tautología, simplemente podemos enumerar las pruebas hasta encontrar una prueba de la fórmula. Por lo tanto, dada una fórmula $\phi$, se puede calcular de la siguiente función: si $\phi$ no es una tautología, regresar $1$. De lo contrario, la búsqueda de la primera prueba de $\phi$ que se encuentre, y devolver la longitud de la prueba. Esta función será computable y dar una respuesta afirmativa a la pregunta. Aviso de que esta respuesta es independiente de cómo la "longitud" de una prueba se define; la respuesta funciona para cualquier definición de "longitud" tan largo como la longitud de la prueba es computable a partir de la prueba en sí.

La situación sería muy diferente de la lógica de primer orden. En ese contexto, el conjunto de los comprobable fórmulas ya no decidable, y la definición de "longitud", se vuelve muy importante.