Teorema de Completitud: Método de Árboles en Lógica de Predicados

Teorema de Completitud del Método de Árboles en la Lógica de Predicados

Si una inferencia es válida, el método de árboles la clasifica como tal al obtenerse un árbol cerrado. Esto equivale a decir que: si el árbol nunca se cierra, la lista inicial es satisfacible.

Excluiremos de nuestra consideración aquellas inferencias o FBFs (Fórmulas Bien Formadas) en las que aparezcan letras proposicionales, símbolos funcionales o el signo de identidad. La prueba se basa en el razonamiento a partir de una rama abierta en un árbol completo. En el caso de árboles infinitos, se supondrá que son generados según el diagrama de flujo para la construcción de árboles.

A continuación, describiremos una interpretación I tal que todas las FBFs de la rama abierta resulten verdaderas, demostrando así que la rama es satisfacible y, por ende, la lista inicial también lo es:

Definición de la Interpretación I

1. El dominio D de I será, o bien el conjunto de todos los números enteros positivos (en caso de que aparezcan infinitas constantes en la rama), o bien el conjunto de los primeros m números enteros positivos, siendo m el número (finito) de constantes distintas que aparezcan en la rama.
2. I asigna 1 a la primera constante que aparezca en la rama, 2 a la segunda, 3 a la tercera (se entiende que son distintas), y así sucesivamente.
3. Para cada letra predicativa n-ádica P que aparezca en la rama, I(P) será el conjunto de n-tuplas correspondientes exactamente a aquellas FBFs atómicas que aparezcan como líneas independientes de la rama.

Prueba (por reducción al absurdo)

Supongamos que en la rama abierta hubiera al menos una línea falsa para I. Si hubiera varias, tomemos la más corta en longitud (en número de símbolos). Sea A una de esas líneas más cortas falsas. Comprobaremos que A no puede tener ninguna de las 9 formas posibles de las FBFs (entendiendo 'Ø' y '®' como únicas conectivas).

Casos de la Prueba

Caso 1: A es atómica

Por definición de I, la FBF A tiene que ser verdadera (V) bajo I. Esto contradice nuestra suposición inicial.

Caso 2: A es de la forma ØB, donde B es atómica

Entonces, la FBF B no puede estar en la rama (al estar abierta), luego B resulta falsa (F) bajo I por definición de I. Por tanto, ØB resulta verdadera (V) bajo I. Esto contradice nuestra suposición inicial.

Caso 3: A es de la forma ØØB

Este caso es obvio. Si A es falsa, entonces ØB debe ser verdadera, lo que implica que B debe ser falsa. Sin embargo, B es más corta que A y, por nuestra suposición, debería ser verdadera. Contradicción.

Caso 4: A es de la forma B ® C

1. Entonces, se habrá aplicado la regla para el condicional y, o bien ØB, o bien C, está en la rama.
2. Pero ØB y C son más cortas que A.
3. Luego, la que está en la rama ha de ser verdadera para I (por la suposición de que A es la línea falsa más corta).
4. Pero tanto ØB como C implican B ® C, es decir, A.
5. Luego, I(A) = V. Esto contradice nuestra suposición inicial.

Caso 5: A es de la forma Ø(B ® C)

De forma análoga al Caso 4, si A es falsa, entonces B debe ser verdadera y C debe ser falsa. Ambas son más cortas que A y, por nuestra suposición, deberían ser verdaderas. Contradicción.

Caso 6: A es de la forma ∀v P(v)

1. Entonces, se habrá aplicado a A la regla para el cuantificador universal tantas veces como constantes k haya en la rama.
2. Cada una de las conclusiones así obtenidas P(k) es más corta que A, y por tanto todas son verdaderas para I (por la suposición de que A es la línea falsa más corta).
3. Ahora bien, de acuerdo con las cláusulas (1) y (2) de la definición de I, los objetos I(k) asignados a esas constantes k agotan el dominio D.
4. Por tanto, según la regla de valoración semántica de la cuantificación universal, I(A) = V. Esto contradice nuestra suposición inicial.

Caso 7: A es de la forma ∃v P(v)

Similarmente al Caso 6, si A es falsa, entonces para cada constante k, P(k) debe ser falsa. Pero P(k) es más corta que A y debería ser verdadera. Contradicción.

Caso 8: A es de la forma Ø∀v P(v)

De forma análoga a los Casos anteriores, si A es falsa, entonces ∃v P(v) debe ser verdadera. Esto implica que existe una constante k tal que P(k) es verdadera. Pero P(k) es más corta que A y debería ser verdadera. Contradicción.

Caso 9: A es de la forma Ø∃v P(v)

Similar a los Casos anteriores, si A es falsa, entonces ∀v P(v) debe ser verdadera. Esto implica que para toda constante k, P(k) es verdadera. Pero P(k) es más corta que A y debería ser verdadera. Contradicción.

Conclusión

Como hemos demostrado, A no puede tener ninguna de las 9 formas de las FBFs de nuestro lenguaje sin generar una contradicción. Por lo tanto, nuestra suposición inicial de que existe una línea falsa en la rama abierta es incorrecta.

En consecuencia, todas las líneas de una rama abierta son satisfacibles simultáneamente, lo que completa la demostración del Teorema de Completitud para el método de árboles en la lógica de predicados.