Posterior: Silogística Arriba: Cálculo de predicados Anterior: Plano de Fano

Deducción natural en el cálculo de predicados

Sea $L$ un lenguaje apropiado para una teoría de primer orden. Sea $\mbox{\it Axiomas}$ el conjunto de axiomas lógicos, de reescritura y extralógicos. Hemos visto que éstos últimos son los que caracterizan a una teoría. El cálculo de predicados sobre $L$ consta de las fórmulas bien formadas que se pueden deducir del conjunto de axiomas. El procedimiento de deducción, al igual que en el cálculo de proposiciones, queda determinado por las reglas de inferencia.

Definición 3.1   En el cálculo de predicados se considera sólo dos REGLAS DE INFERENCIA:

Modus ponens

Para cualesquiera dos fórmulas $\phi$, $\psi$:

$$\begin{array}{cc} \begin{array}{l} \phi\rightarrow \psi \\ \phi \end{array} \\ \hline \psi \end{array}$$ (1)

Generalización

Para cualquier fórmula $\phi(x)$, donde $x$ aparece libre en $\phi$:

$$\begin{array}{cc} \phi(x) \\ \hline \forall x\, \phi(x) \end{array}$$ (2)

La primera regla de inferencia no requiere comentarios pues ya la hemos utilizado en este curso. La segunda formaliza el conocido procedimiento para demostrar una proposición cuantificada universalmente: Se considera un elemento cualquiera $x$ y se ve que vale $\phi(x)$, luego, dado que $x$ es arbitrario, se concluye que, en efecto, $\phi(x)$ vale para cualquier $x$.

Definición 3.2 (Pruebas)   Sea $H\subset \mbox{\rm Fbf}(L)$ una colección de fórmulas bien formadas sobre el lenguaje $L$, llamadas hipótesis. Una PRUEBA es una sucesión finita $D=[\phi_1,\ldots,\phi_n]$ de fórmulas bien formadas tal que $\forall i\leq n$:

• $\phi_i\in\mbox{\it Axiomas}$, o
• $\phi_i\in H$, o
• $\exists j,k<i:\ \phi_k=(\phi_j\rightarrow \phi_i)$
• $\exists j<i:\ \phi_k=\forall x\, \phi_j(x)$

En este caso la prueba $D$ se dice ser una prueba de $\phi_n$ a partir de $H$. Se escribe $H\vdash \phi$ para denotar el hecho de que $\phi$ es DEMOSTRABLE, es decir, que existe una prueba de $\phi_n$ a partir de $H$. El conjunto de fórmulas $\mbox{\it Ded}(H)=\{\phi\in \mbox{\rm Fbf}(L) \vert H\vdash \phi\}$ consta de todas las fórmulas demostrables a partir de $H$. Éste se dice ser la TEOR´iA de $H$.

Se observa inmediatamente que vale una especie de transitividad en la noción de demostrabilidad:

Proposición 3.1   Sean $H,\Phi,\Psi\subset\mbox{\rm Fbf}(L)$ tres conjuntos de fórmulas y sean $\phi, \psi\in\mbox{\rm Fbf}(L)$ otras dos fórmulas. Entonces vale la siguiente implicación:

$$\Phi\vdash\phi\ \&\ \Psi\cup\{\phi\}\vdash\psi \ \Rightarrow\ \Psi\cup\Phi\vdash\psi.$$ (3)

En consecuencia, el ``operador'' $\mbox{\it Ded}$ es un operador de cerradura: Para cualesquiera $H_1,H_2\subset\mbox{\rm Fbf}(L)$:

1. $H_1\subset\mbox{\it Ded}(H_1)$.
2. $H_1\subset H_2\ \Rightarrow\ \mbox{\it Ded}(H_1)\subset \mbox{\it Ded}(H_2)$.
3. $\mbox{\it Ded}(\mbox{\it Ded}(H_1)) = \mbox{\it Ded}(H_1)$.

Definición 3.3   El conjunto de TEOREMAS en $L$ es $\mbox{\it Ded}(\emptyset)$, es decir, es el conjunto de fórmulas demostrables partiendo únicamente de los axiomas. El conjunto de teoremas se dice ser también la TEOR´iA DE PRIMER ORDEN resultante del lenguaje $L$ con los $\mbox{\it Axiomas}$.

Ejemplo 3.1   Sea $\Phi(X_1,\ldots,X_m)$ una tautología del cálculo proposicional. Si $\phi_1,\ldots,\phi_m\in \mbox{\rm Fbf}(L)$ son $m$ fórmulas bien formadas, entonces al sustituir cada variable proposicional $X_i$ por la fórmula $\phi_i$ se obtiene la fórmula $\Phi(X_1\leftarrow\phi_1,\ldots,X_m\leftarrow\phi_m)$ que es una TAUTOLOG´iA del cálculo de predicados. Se tiene que $\Phi(X_1\leftarrow\phi_1,\ldots,X_m\leftarrow\phi_m)$ es un teorema.

En efecto, al ser $\Phi(X_1,\ldots,X_m)$ una tautología, por el Teorema de Completitud del cálculo proposicional, es también un teorema, es decir, existe una demostración de $\Phi(X_1,\ldots,X_m)$. Esta es evidentemente también una demostración de $\Phi(X_1\leftarrow\phi_1,\ldots,X_m\leftarrow\phi_m)$ en el cálculo de predicados. $\quad\Box$

Ejemplo 3.2   Para cada $\phi(x,y)\in \mbox{\rm Fbf}(L)$ se tiene

$$\vdash \left(\forall x\, \forall y\, \phi(x,y)\right)\ \rightarrow\ \left(\forall y\, \forall x\, \phi(x,y)\right)$$

es decir, cuantificadores universales consecutivos pueden intercambiarse.

Demostración
Una prueba es la siguiente:

1.

$\left(\forall x\, \forall y\, \phi(x,y)\right)\ \rightarrow\ \forall y\, \phi(x,y)$ ( $\mbox{\rm Ax}_4$)

2.

$\left(\forall y\, \phi(x,y)\right)\ \rightarrow\ \phi(x,y)$ ( $\mbox{\rm Ax}_4$)

3.

$\begin{array}[t]{l} \left(\left(\forall y\, \phi(x,y)\right)\ \rightarrow\ \ph... ...\forall y\, \phi(x,y)\right)\ \rightarrow\ \phi(x,y)\right)\right) \end{array}$ ( $\mbox{\rm Ax}_1$)

4.

$\forall x\, \forall y\, \phi(x,y)\ \rightarrow\ \left(\left(\forall y\, \phi(x,y)\right)\ \rightarrow\ \phi(x,y)\right)$ ( $\mbox{\rm MP}\ 2,3$)

5.

$\begin{array}[t]{l} \left(\forall x\, \forall y\, \phi(x,y)\ \rightarrow\ \lef... ...ll x\, \forall y\, \phi(x,y)\ \rightarrow\ \phi(x,y)\right)\right) \end{array}$ ( $\mbox{\rm Ax}_2$)

6.

$\left(\forall x\, \forall y\, \phi(x,y)\ \rightarrow\ \forall y\, \phi(x,y)\rig... ...htarrow\ \left(\forall x\, \forall y\, \phi(x,y)\ \rightarrow\ \phi(x,y)\right)$ ( $\mbox{\rm MP}\ 4,5$)

7.

$\forall x\, \forall y\, \phi(x,y)\ \rightarrow\ \phi(x,y)$ ( $\mbox{\rm MP}\ 1,6$)

8.

$\forall x\, \left(\forall x\, \forall y\, \phi(x,y)\ \rightarrow\ \phi(x,y)\right)$ ( $\mbox{\rm Gen}\ 7$)

9.

$\forall x\, \left(\forall x\, \forall y\, \phi(x,y)\ \rightarrow\ \phi(x,y)\rig... ...ft(\forall x\, \forall y\, \phi(x,y)\ \rightarrow\ \forall x\, \phi(x,y)\right)$ ( $\mbox{\rm Ax}_5$)

10.

$\forall x\, \forall y\, \phi(x,y)\ \rightarrow\ \forall x\, \phi(x,y)$ ( $\mbox{\rm MP}\ 8,9$)

11.

$\forall y\, \left(\forall x\, \forall y\, \phi(x,y)\ \rightarrow\ \forall x\, \phi(x,y)\right)$ ( $\mbox{\rm Gen}\ 10$)

12.

$\begin{array}[t]{l} \forall y\, \left(\forall x\, \forall y\, \phi(x,y)\ \righ... ..., \phi(x,y)\ \rightarrow\ \forall y\, \forall x\, \phi(x,y)\right) \end{array}$ ( $\mbox{\rm Ax}_5$)

13.

$\forall x\, \forall y\, \phi(x,y)\ \rightarrow\ \forall y\, \forall x\, \phi(x,y)$ ( $\mbox{\rm MP}\ 11,12$)

$\quad\Box$

Ejemplo 3.3   Para cada $\phi(x,y)\in \mbox{\rm Fbf}(L)$ se tiene

$$\vdash \forall x\, \forall y\, \left(\phi(x,y)\ \rightarrow\ \neg\phi(y,x)\right)\ \rightarrow\ \forall x\, \neg\phi(x,x)$$

es decir, ``un predicado que no es simétrico para ninguna pareja no puede cortar a la diagonal''.

Demostración
Escribiremos una prueba de ese teorema. Para simplificar la escritura mínimamente, abreviaremos

$$\Phi \equiv \left[\forall x\, \forall y\, \left(\phi(x,y)\ \rightarrow\ \neg\phi(y,x)\right)\right].$$

En la tabla 3.4 presentamos esa prueba.

Table 3.4: Prueba de $\forall x\, \forall y\, \left (\phi (x,y)\ \rightarrow \ \neg \phi (y,x)\right )\ \rightarrow \ \forall x\, \neg \phi (x,x)$.

$\quad\Box$ Así como en el cálculo proposicional el Teorema de la Deducción proporciona un procedimiento para simplificar demostraciones, en el cálculo de predicados se tiene también una propia versión de este teorema para facilitar pruebas. Sólo que aquí, debido al uso de variables, hay que proceder con un mayor cuidado para enunciar y demostrar ese teorema. En efecto, obsérvese que para una fórmula con una sola variable libre $\phi(x)\in\mbox{\rm Fbf}(L)$, por la regla de generalización se tiene $\phi(x)\vdash \forall x\, \phi(x)$, sin embargo, no es cierto que $\vdash \phi(x)\rightarrow \forall x\, \phi(x)$, pues en esta última fórmula, la primera aparición de $x$ se refiere a un término en particular, no a un elemento genérico. Es decir, una variable libre $x$ a la izquierda del símbolo $\vdash$ se refiere a un objeto sintáctico arbitrario que aún no se ha evaluado, en tanto que la misma variable libre $x$ a la derecha de $\vdash$ se refiere a un término que en cualquier interpretación ha de tener una correspondiente evaluación. De este ejemplo, se ve que es precisamente en la aplicación de la regla de generalización que hay que poner especial atención al enunciar el correspondiente teorema de la Deducción.

Definición 3.4   Sea $P\subset\mbox{\rm Fbf}(L)$ un conjunto de fórmulas bien formadas, $\phi_0\in P$ una fórmula en $P$ y sea $\left[\phi_1,\ldots,\phi_m\right]$ una prueba construída a partir de $P$. Se dice que $\phi_i$ DEPENDE de $\phi_0$ si se cumple alguna de las proposiciones siguientes:

1. $\phi_i=\phi_0$
2. $\phi_i$ se sigue de alguna fórmula que depende de $\phi_0$.

Resulta claro que si $\phi_i$ no depende de $\phi_0$, entonces vale la implicación:

$$P\cup\{\phi_0\} \vdash \phi_i\ \Rightarrow\ P \vdash \phi_i.$$ (4)

Teorema 3.1 (de la Deducción)   Sea $P\subset\mbox{\rm Fbf}(L)$ un conjunto de fórmulas bien formadas y sean $\phi_0,\phi\in \mbox{\rm Fbf}(L)$ dos fórmulas. Supongamos que $P\cup\{\phi_0\} \vdash \phi$ y que existe una prueba de esto en la que la regla de generalización no se haya aplicado a ninguna fórmula que dependa de $\phi_0$, respecto a una variable libre de $\phi_0$. Entonces $P \vdash \phi_0 \rightarrow \phi$.

El recíproco del Teorema de Deducción,

$$P \vdash \phi_0 \rightarrow \phi \ \ \Rightarrow \ \ P\cup\{\phi_0\} \vdash \phi$$

es válido como una consecuencia de la regla Modus Ponens. Demostración
Sea $\left[\phi_1,\ldots,\phi_n=\phi\right]$ una prueba de $\phi$ construída a partir de $P\cup\{\phi_0\}$. Probemos por inducción en $n$ que $P \vdash \phi_0 \rightarrow \phi$. Caso base. Supongamos $n=1$. Entonces $\phi\in P\cup\{\phi_0\}\cup\mbox{\it Axiomas}$. Si $\phi=\phi_0$ entonces, al ser $\phi_0 \rightarrow \phi_0$ un teorema lógico, $P \vdash \phi_0 \rightarrow \phi$. En otro caso, una prueba de $\phi_0 \rightarrow \phi$ es:

1.

$\phi\ \rightarrow\ \left(\phi_0\ \rightarrow\ \phi\right)$ ( $\mbox{\rm Ax}_1$)

2.

$\phi$ ( $P\cup\mbox{\it Axiomas}$)

3.

$\phi_0 \rightarrow \phi$ ( $\mbox{\rm MP}\ 1,2$)

Caso inductivo. Supongamos $n>1$ y que el teorema se cumple para demostraciones de longitud estrictamente menor que $n$. Ya que $P\cup\{\phi_0\} \vdash \phi$, puede ocurrir que $\phi=\phi_n\in P\cup\{\phi_0\}\cup\mbox{\it Axiomas}$ o bien que $\phi=\phi_n$ es el resultado de aplicar una de las dos reglas de inferencia a fórmulas anteriores en la prueba. En el primer caso, como ya se vió en el caso base, se tiene $P \vdash \phi_0 \rightarrow \phi$. En el segundo caso, hay que ver cuál es la regla de inferencia que le dió lugar.

Modus ponens. Para algunos índices anteriores $n_1,n_2<n$ las correspondientes fórmulas han de ser de la forma $\phi_{n_1}=(\psi\rightarrow \phi)$ y $\phi_{n_2}=\psi$. Por la hipótesis de inducción se tiene que existe una prueba $Q_1$ de que $P\vdash (\phi_0\rightarrow \phi_{n_1})$ y una prueba $Q_2$ de que $H\vdash (\phi_0\rightarrow \phi_{n_2})$, digamos que de $m_1$ y $m_2$ pasos. La concatenación de $Q_1$ y $Q_2$ con los siguientes pasos da una prueba de $\phi_0 \rightarrow \phi$ a partir de $P$:

$m_1+m_2+1$.

$(\phi_0\rightarrow (\psi\rightarrow \phi))\rightarrow ((\phi_0\rightarrow \psi)\rightarrow (\phi_0\rightarrow \phi))$ ( $\mbox{\rm Ax}_2$)

$m_1+m_2+2$.

$(\phi_0\rightarrow \psi)\rightarrow (\phi_0\rightarrow \phi)$ ( $\mbox{\rm MP}\ \scriptstyle{m_1+m_2+1,m_1}$)

$m_1+m_2+3$.

$\phi_0 \rightarrow \phi$ ( $\mbox{\rm MP}\ \scriptstyle{m_1+m_2+2,m_1+m_2}$)

Generalización. Supongamos que para algna fórmula anterior $\phi_i(x)$, $i<n$, se tiene $\phi_n=\forall x\,\phi_i(x)$. Por la hipótesis del teorema, se tiene que bien $\phi_i(x)$ no depende de $\phi_0$ o bien $x$ no aparece libre en $\phi_0$. En el primer caso, por la relación (4), se tiene $P\vdash \phi_i(x)$. Una prueba de esto último, digamos que de $m$ pasos, se extiende mediante los pasos siguientes a una prueba de $P \vdash \phi_0 \rightarrow \phi$:

$m$.

$\phi_i(x)$ ( $\mbox{\rm Teo}$)

$m+1$.

$\phi_n$ ( $\mbox{\rm Gen}\ m$)

$m+2$.

$\phi_n\rightarrow (\phi_0\rightarrow \phi_n)$ ( $\mbox{\rm Ax}_1$)

$m+3$.

$\phi_0\rightarrow \phi_n$ ( $\mbox{\rm MP}\ \scriptstyle{m+1,m+2}$)

En el segundo caso, por la hipótesis de inducción se tiene

$$P\vdash \phi_0\rightarrow \phi_i(x)$$

y una prueba de esto último, digamos que de $m$ pasos, se extiende mediante los pasos siguientes a una prueba de $P \vdash \phi_0 \rightarrow \phi$:

$m$.

$\phi_0\rightarrow \phi_i(x)$ ( $\mbox{\rm Teo}$)

$m+1$.

$\forall x\,\left(\phi_0\rightarrow \phi_i(x)\right)$ ( $\mbox{\rm Gen}\ m$)

$m+2$.

$\forall x\,\left(\phi_0\rightarrow \phi_i(x)\right)\ \rightarrow\ \left(\phi_0\rightarrow \forall x\,\phi_i(x)\right)$ ( $\mbox{\rm Ax}_5$)

$m+3$.

$\phi_0\rightarrow \phi_n$ ( $\mbox{\rm MP}\ \scriptstyle{m+1,m+2}$)

$\quad\Box$ En la siguiente subsección veremos que este cálculo de predicados contiene al clásico (en varios sentidos).

Posterior: Silogística Arriba: Cálculo de predicados Anterior: Plano de Fano