Posterior: Procedimientos de demostración automática Arriba: Coherencia y completitud Anterior: Teorema de coherencia

Teorema de completitud

En la subsección anterior vimos que todo teorema es una tautología. Veremos ahora que el recíproco también es cierto. Con esto tendremos un algoritmo para generar pruebas en la deducción natural. En efecto, revisar que una proposición es un teorema es un procedimiento computacionalmente ``muy sencillo'' (simplemente se evalúa su tabla de verdad), aunque es computacionalmente ``caro'' (pues con $n$ variables proposicionales hay que hacer $2^n$ evaluaciones). Sin embargo, la localización de una prueba en el esquema de la deducción natural plantea un problema ``difícil'' en el sentido de que ``es muy poco natural'', como ya lo hemos ilustrado con algunos ejemplos. Sea $\mbox{\boldmath$\epsilon$}$ una asignación. Para cada proposición $p\in\mbox{\it Pbf}(X)$ escribamos

$$p_{\mbox{\boldmath $\epsilon$}} = \left\{\begin{array}{ll} p... ...box{\boldmath $\epsilon$} , p\rangle =0$ } \end{array}\right.$$

Proposición 3.1   Con la notación introducida, para cualquier asignación $\mbox{\boldmath$\epsilon$}$ y cualquier proposición $p(x_1,\ldots,x_n)\in\mbox{\it Pbf}(X)$ se tiene:

$$\left\{\left(x_1\right)_{\mbox{\boldmath$\epsilon$}}, \ldot... ...ght\} \vdash p_{\mbox{\boldmath$\epsilon$}}(x_1,\ldots,x_n)$$ (2)

Demostración
Procedamos por inducción en el número $k$ de conectivos en $p(x_1 ,\ldots, x_n )$. Caso base. ($k=0$.) En este caso, para alguna $j$, $p=x_j$. Evidentemente, $\left\{\left(x_1\right)_{\mbox{\boldmath$\epsilon$}}, \ldots, \left(x_n\right)_... ...dmath$\epsilon$}} \right\} \vdash \left(x_j\right)_{\mbox{\boldmath$\epsilon$}}$.


Caso inductivo. ($k>0$.) Supongamos que la relación (2) se cumple para cualquier proposición $p$ con a lo sumo $k$ conectivos. Sea ahora $p$ una proposición con exactamente $k+1$ conectivos. Veremos que con ella se cumple también la relación (2). Naturalmente, los dos casos posibles a considerar corresponden a que el conectivo principal de $p$ sea la negación y a que el conectivo principal sea la implicación. Al considerar el caso de la negación, digamos $p=\neg p_1$, hemos de tratar dos casos según sea el valor de verdad de $p_1$. Al considerar el caso de la implicación, digamos $p=( p_1\rightarrow p_2)$, hemos de tratar tres casos según sean los valores de verdad de $p_1$ y $p_2$.

Caso $p=\neg p_1$ y $\langle \mbox{\boldmath$\epsilon$} , p_1\rangle =0$. Aquí $\left(p_1\right)_{\mbox{\boldmath$\epsilon$}}=\neg p_1$ y $p_{\mbox{\boldmath$\epsilon$}}= p$. Por un lado, de la relación (2), válida para $p_1$, tenemos $\left\{\left(x_1\right)_{\mbox{\boldmath$\epsilon$}}, \ldots, \left(x_n\right)_{\mbox{\boldmath$\epsilon$}} \right\} \vdash \neg p_1$. Es decir, $\left\{\left(x_1\right)_{\mbox{\boldmath$\epsilon$}}, \ldots, \left(x_n\right)_{\mbox{\boldmath$\epsilon$}} \right\} \vdash p_{\mbox{\boldmath$\epsilon$}}$ pues $p_{\mbox{\boldmath$\epsilon$}}= \neg p_1$.

Caso $p=\neg p_1$ y $\langle \mbox{\boldmath$\epsilon$} , p_1\rangle =1$. Aquí $\left(p_1\right)_{\mbox{\boldmath$\epsilon$}}=p_1$ y $p_{\mbox{\boldmath$\epsilon$}}=\neg p$. Por un lado, de la relación (2), válida para $p_1$, tenemos $\left\{\left(x_1\right)_{\mbox{\boldmath$\epsilon$}}, \ldots, \left(x_n\right)_{\mbox{\boldmath$\epsilon$}} \right\} \vdash p_1$. Y, por otro lado, por el principio de la doble negación (véase la proposición 2.2.3-$E'$), se tiene $p_1\vdash \neg \neg p_1$. Al concatenar las pruebas de estos dos hechos, se obtiene una prueba de que $\left\{\left(x_1\right)_{\mbox{\boldmath$\epsilon$}}, \ldots, \left(x_n\right)_{\mbox{\boldmath$\epsilon$}} \right\} \vdash p_{\mbox{\boldmath$\epsilon$}}$ pues $p_{\mbox{\boldmath$\epsilon$}}= \neg \neg p_1$.

Caso $p=( p_1\rightarrow p_2)$ y $\langle \mbox{\boldmath$\epsilon$} , p_1\rangle =0$. Aquí $\langle \mbox{\boldmath$\epsilon$},p \rangle = 1$, $p_{\mbox{\boldmath$\epsilon$}}=(p_1\rightarrow p_2)$ y $\left(p_1\right)_{\mbox{\boldmath$\epsilon$}}=\neg p_1$. Por un lado, de la relación (2), válida para $p_1$, tenemos $\left\{\left(x_1\right)_{\mbox{\boldmath$\epsilon$}}, \ldots, \left(x_n\right)_{\mbox{\boldmath$\epsilon$}} \right\} \vdash \neg p_1$. Por otro lado, de Contradictio ex omnia (véase la proposición 2.2.1-$B$) se tiene $\{p_1,\neg p_1\}\vdash p_2$. Aplicando dos veces el Teorema de Deducción (véase el teorema 2.2.1), se obtiene una prueba de $\vdash \neg p_1\rightarrow (p_1\rightarrow p_2)$. Al concatenar ambas pruebas y utilizar la regla Modus Ponens se obtiene una prueba de que $\left\{\left(x_1\right)_{\mbox{\boldmath$\epsilon$}}, \ldots, \left(x_n\right)_{\mbox{\boldmath$\epsilon$}} \right\} \vdash p_{\mbox{\boldmath$\epsilon$}}$ pues $p_{\mbox{\boldmath$\epsilon$}}=(p_1\rightarrow p_2)$.

Caso $p=( p_1\rightarrow p_2)$ y $\langle \mbox{\boldmath$\epsilon$} , p_2\rangle =1$. Aquí $\langle \mbox{\boldmath$\epsilon$},p \rangle = 1$, $p_{\mbox{\boldmath$\epsilon$}}=(p_1\rightarrow p_2)$ y $\left(p_2\right)_{\mbox{\boldmath$\epsilon$}}= p_2$. Por un lado, de la relación (2), válida para $p_2$, tenemos $\left\{\left(x_1\right)_{\mbox{\boldmath$\epsilon$}}, \ldots, \left(x_n\right)_{\mbox{\boldmath$\epsilon$}} \right\} \vdash \neg p_2$. Por otro lado, $p_2\rightarrow (p_1\rightarrow p_2)$ es un axioma del tipo 1. Al utilizar la regla Modus Ponens se obtiene una prueba de que $\left\{\left(x_1\right)_{\mbox{\boldmath$\epsilon$}}, \ldots, \left(x_n\right)_{\mbox{\boldmath$\epsilon$}} \right\} \vdash p_{\mbox{\boldmath$\epsilon$}}$ pues $p_{\mbox{\boldmath$\epsilon$}}=(p_1\rightarrow p_2)$.

Caso $p=( p_1\rightarrow p_2)$, $\langle \mbox{\boldmath$\epsilon$} , p_1\rangle =1$ y $\langle \mbox{\boldmath$\epsilon$} , p_2\rangle =0$. Aquí $\langle \mbox{\boldmath$\epsilon$},p\rangle=0$, $p_{\mbox{\boldmath$\epsilon$}}=\neg(p_1\rightarrow p_2)$, $\left(p_1\right)_{\mbox{\boldmath$\epsilon$}}=p_1$ y $\left(p_2\right)_{\mbox{\boldmath$\epsilon$}}= \neg p_2$. Veamos que $\{p_1,\neg p_2\}\vdash \neg(p_1\rightarrow p_2)$.

1.

$\left(\left(p_1\rightarrow p_2\right)\rightarrow \neg p_2\right) \rightarrow \... ...ht)\rightarrow p_2\right)\rightarrow \neg\left(p_1\rightarrow p_2\right)\right)$ ( $\mbox{\rm Ax}_3$)

2.

$\neg p_2\rightarrow \left(\left(p_1\rightarrow p_2\right)\rightarrow \neg p_2\right)$ ( $\mbox{\rm Ax}_1$)

3.

$\neg p_2$ ( $\mbox{\rm Hip}$)

4.

$\left(p_1\rightarrow p_2\right)\rightarrow \neg p_2$ ( $\mbox{\rm MP}\ 2,3$)

5.

$\left(\left(p_1\rightarrow p_2\right)\rightarrow p_2\right)\rightarrow \neg\left(p_1\rightarrow p_2\right)$ ( $\mbox{\rm MP}\ 1,4$)

6.

$\left(\left(p_1\rightarrow p_2\right)\rightarrow \left(p_1\rightarrow p_2\right... ...rightarrow \left(\left(p_1\rightarrow p_2\right)\rightarrow p_2\right)\right)$ ( $\mbox{\rm Ax}_2$)

7.

$\left(p_1\rightarrow p_2\right)\rightarrow \left(p_1\rightarrow p_2\right)$ ( $\mbox{\rm Teo}$)

8.

$\left(\left(p_1\rightarrow p_2\right)\rightarrow p_1\right)\rightarrow \left(\left(p_1\rightarrow p_2\right)\rightarrow p_2\right)$ ( $\mbox{\rm MP}\ 6,7$)

9.

$p_1\rightarrow (\left(p_1\rightarrow p_2\right)\rightarrow p_1)$ ( $\mbox{\rm Ax}_1$)

10.

$p_1$ ( $\mbox{\rm Hip}$)

11.

$\left(p_1\rightarrow p_2\right)\rightarrow p_1$ ( $\mbox{\rm MP}\ 9,10$)

12.

$\left(p_1\rightarrow p_2\right)\rightarrow p_2$ ( $\mbox{\rm MP}\ 8,11$)

13.

$\neg\left(p_1\rightarrow p_2\right)$ ( $\mbox{\rm MP}\ 5,12$)

Aplicando dos veces el Teorema de Deducción (véase el teorema 2.2.1), se obtiene una prueba de $\vdash p_1\rightarrow \left(\neg p_2\rightarrow \neg\left(p_1\rightarrow p_2\right)\right)$. Por la hipótesis de inducción se tiene $\left\{\left(x_1\right)_{\mbox{\boldmath$\epsilon$}}, \ldots, \left(x_n\right)_{\mbox{\boldmath$\epsilon$}} \right\} \vdash p_1$ y $\left\{\left(x_1\right)_{\mbox{\boldmath$\epsilon$}}, \ldots, \left(x_n\right)_{\mbox{\boldmath$\epsilon$}} \right\} \vdash \neg p_2$. Así pues, con Modus Ponens se sigue que, en efecto $\left\{\left(x_1\right)_{\mbox{\boldmath$\epsilon$}}, \ldots, \left(x_n\right)_{\mbox{\boldmath$\epsilon$}} \right\} \vdash p_{\mbox{\boldmath$\epsilon$}}$ pues $p_{\mbox{\boldmath$\epsilon$}}=\neg(p_1\rightarrow p_2)$. $\quad\Box$ Con este antecedente se puede demostrar el recíproco del teorema de coherencia.

Teorema 3.2 (de Completitud)   Sea $P\subset\mbox{\it Pbf}(X)$ un conjunto de proposiciones y sea $p\in\mbox{\it Pbf}(X)$ una proposición más. Entonces:

$$P\models p \ \Rightarrow\ P\vdash p$$ (3)

Demostración
Basta demostrar

$$\models p \ \Rightarrow\ \vdash p$$ (4)

pues si $P$ fuese finito, por el Teorema de Deducción, la implicación (3) se reduce inmediatamente a la implicación (4). Si $P$ fuese infinito y $P\models p$, entonces para algún conjunto finito $P_1\subset P$ se tendría $P_1\models p$ y por el Teorema de Deducción esto equivale a una tautología. Probemos entonces la implicación (4). Sea $p=p(x_1,\ldots,x_n)$ una tautología. Entonces para cualquier asignación $\mbox{\boldmath$\epsilon$}$, $p_{\mbox{\boldmath$\epsilon$}}= p$, y por la proposición anterior, $\left\{\left(x_1\right)_{\mbox{\boldmath$\epsilon$}}, \ldots, \left(x_n\right)_{\mbox{\boldmath$\epsilon$}} \right\} \vdash p$. Sean $\mbox{\boldmath$\epsilon$}_0$, $\mbox{\boldmath$\epsilon$}_1$ dos asignaciones tales que $\langle \mbox{\boldmath$\epsilon$}_0,x_n\rangle =0$, $\langle \mbox{\boldmath$\epsilon$}_1,x_n\rangle =1$ y $\langle \mbox{\boldmath$\epsilon$}_0,x_j\rangle = \langle \mbox{\boldmath$\epsilon$}_1,x_j\rangle$ para cada $j<n$. Entonces,

$$\left\{\left(x_1\right)_{\mbox{\boldmath $\epsilon$}_0}, \ldo... ...}\right)_{\mbox{\boldmath $\epsilon$}_1},x_n \right\} \vdash p.$$

Por el Teorema de Deducción:

$$\left\{\left(x_1\right)_{\mbox{\boldmath $\epsilon$}_0}, \ldo... ...box{\boldmath $\epsilon$}_0} \right\} \vdash x_n \rightarrow p.$$

Por el principio de contraposición (véase la proposición 2.2.4), $(a\rightarrow b)\rightarrow (\neg b\rightarrow \neg a)$ es un teorema. De aquí se puede ver que $\{\neg x_n \rightarrow p,x_n \rightarrow p\}\vdash p$. En efecto, una prueba es la siguiente:

1.

$(\neg p\rightarrow \neg x_n)\rightarrow((\neg p\rightarrow x_n)\rightarrow p)$ ( $\mbox{\rm Ax}_3$)

2.

$(x_n\rightarrow p)\rightarrow (\neg p\rightarrow \neg x_n)$ ( $\mbox{\rm Teo.}$)

3.

$x_n\rightarrow p$ ( $\mbox{\rm Hip}$)

4.

$\neg p\rightarrow \neg x_n$ ( $\mbox{\rm MP}\ 2,3$)

5.

$(\neg p\rightarrow x_n)\rightarrow p$ ( $\mbox{\rm MP}\ 1,4$)

6.

$(\neg x_n\rightarrow p)\rightarrow (\neg p\rightarrow x_n)$ ( $\mbox{\rm Teo}$)

7.

$\neg x_n\rightarrow p$ ( $\mbox{\rm Hip}$)

8.

$\neg p\rightarrow x_n$ ( $\mbox{\rm MP}\ 6,7$)

9.

$p$ ( $\mbox{\rm MP}\ 5,8$)

Componiendo pruebas, se tiene entonces que

$$\left\{\left(x_1\right)_{\mbox{\boldmath $\epsilon$}_0}, \ldo... ...x_{n-1}\right)_{\mbox{\boldmath $\epsilon$}_0}\right\} \vdash p$$

cualquiera que sea la asignación $\mbox{\boldmath$\epsilon$}_0$. Con esto, hemos reducido en 1 las hipótesis para probar $p$. Continuando de igual forma, suprimiremos a todas las hipótesis para obtener al final $\vdash p$. $\quad\Box$ El Teorema de Completitud afirma entonces que toda tautología en el cálculo de proposiciones es un teorema. En otras palabras, afirma que el sistema elegido de axiomas lógicos con la regla de inferencia Modus Ponens para la deducción natural es suficiente para demostrar cualquier proposición que sea verdadera. Es en este sentido que el Cálculo de Proposiciones de la Deducción Natural es un sistema completo.
Posterior: Procedimientos de demostración automática Arriba: Coherencia y completitud Anterior: Teorema de coherencia